摘要
首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题。证明了问题1|B≥n,rej|Tmax+TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法。
In this paper, the authors consider the single unbounded parallel batch scbeduling problem which minimizes the objective function for the maximum delay and the workpiece is rejected and the penalty costs for the first time. The authors show that this problem is NP-hard and provide a pseudo-polynomial-time algorithm based on dynamic programming.
出处
《洛阳理工学院学报（自然科学版）》
2011年第4期68-72,93,共6页
Journal of Luoyang Institute of Science and Technology：Natural Science Edition
基金
国家自然科学基金(11071142)
山东省自然科学基金(ZR2010AM034))
关键词
可拒绝排序
分批排序
最大延误
动态规划
rejection scheduling
batch scheduling
maxinmm tardiness
dynamic programming
