带有交货期窗口和加工时间可控的排序问题

Single machine due-window assignment and scheduling with controllable processing times

讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。

In this paper,we consider a kind of single-machine scheduling problem with duewindow assignment and scheduling with controllable job processing times.The processing time of each job is the convex resource function.If the job is completed outside the due-window,it would be penalized according to its earliness or tardiness value.We consider two models.In the first model,each job has its own due-window.In the second model,all the jobs have the common duewindow.The objective is to determine the optimal sequence,the optimal processing times and to minimize the total resource consumption cost under the constraint that the scheduling cost is related to earliness,tardiness,the starting time of due-window,the size of due-window and the makespan.By converting the two scheduling problems into assignment problems,we prove that the scheduling problems can both be solved in polynomial time and the complexities of the two problems are both O（n^3）.