带有学习与恶化效应的共同工期指派问题

Common Due Date Assignment Problem with Learning and Deterioration Effects

【目的】研究在共同工期指派模型下,工件的实际加工时间既有学习效应(与所排位置有关)又有恶化效应(与开工时间有关)的排序问题,其中机器限定为一台。【方法】为求得最优排序,使得工件的提前、延误和工期成本的线性加权和最小,其中权重为位置权重,工件的共同工期为决策变量,此问题可转化为经典的运筹学方法求解,即求解指派问题。【结果】这个问题在位置权重、学习与恶化效应下依然是多项式时间可解的。【结论】算法分析和实例表明给出的求解算法是非常有效的。

[Purposes]Under the common due date assignment,it studies a scheduling problem in which the actual processing time of ajob is related to the learning effect(its position)and the deterioration effect(its starting time),where the machine number is limited to single machine.[Methods]To find an optimal schedule such that the weighted sum of the earliness and tardiness and the common due date costs is minimized,where the weights are the position-dependent weights and the common due date is a decision variable,the problem can be solved by using the classical operations research method,i.e.,by using the assignment problem method.[Findings]It is showed that the problem remains polynomial time solvable under the position-dependent weights,learning the deterioration effect.[Conclusions]Analysis of algorithm and an example show that the optimal schedule can be obtained quickly by the corresponding algorithm.