具有CON/SLK交货期指派的一类单机排序问题

Scheduling Problems with CON/SLK Due Date Assignment

研究工件的实际加工时间既具有指数学习效应,又依赖所消耗资源的准时制排序问题.在模型中,探讨了共同交货期(CON)和松弛交货期(SLK)两种情形.管理者的目标是确定最优序、最优资源分配方案和最佳工期(共同交货期或松弛交货期)以便极小化工件的总延误、总提前、总工期和资源消耗费用的总和.对于工件的实际加工时间是资源消耗量的线性函数的排序问题,通过将其转化为指派模型,给出了时间复杂性为O(n^3)的算法,从而证明该类排序问题是多项式时间可求解的.针对工件的实际加工时间是资源消耗量的凸函数的排序问题,也给出了多项式算法.

This paper discusses single machine JIT scheduling problems in which the actual processing time is exponential learning effect and resource-dependent. In the model, we study common due date （CON） and slack due date（SLK） cases respectively. Managers＇s aim is to decide the optimal sequence, the optimal resource allocation and the optimal due date（CON or SLK） to minimize the sum of the total tardiness, the total earliness, the total due date and the total resource cost. For the actual processing time of each job is linear resource-dependent, we give algorithms of O（n^3） time by converting them to assignment problems, thus we prove that these scheduling problems are polynomial time solvable. For the actual processing time of each job is convex resource-dependent, we present polynomial time solvable algorithms for each problem.