具有学习效应和退化效应的单机排序问题

Single-machine scheduling problem with learning effect and aging effect

讨论同时具有截断控制参数学习效应和退化效应并带有公共交货期窗口的单机调度问题,其中工件任务的加工时间不仅依赖资源分配,而且依赖于截断控制参数和工件任务的起始加工时间。全部工件任务共同拥有同一个交货期窗口,假设工件任务若在交货期窗口期限之内完成,则不产生费用;否则,提前或延后交货都要产生一部分费用。目标是确定最优排序以及资源分配最优方案,分别考虑如下2种情况:1)限制资源总成本费用,极小化带有提前、延后、公共交货期起始时间、交货期窗口规模、总完工时间绝对差、完工时间总和值的问题;2)在限制窗口规模、完工时间总和等费用成本的情况下,极小化总资源量。将上述2种问题进一步转化为指派问题,研究并证明所述2种问题可在多项式时间内解决,并分别给出2个最优算法。

We consider a single machine scheduling problem with truncated learning effect,aging effect and a common due-window.The processing time of a job is dependent on resource allocation,the truncated control parameter and the starting time of the job.And all jobs have a common duewindow.If the job is completed within the due window,it will not be penalty.Otherwise the job completed before the starting time of the due window or after the ending time of it will have earliness or tardiness costs.The objective is to determine the optimal sequence of jobs and the optimal resource allocation.We consider two models.For the first we constrain the total resource amount to minimize the weighted costs of earliness,tardiness,the the starting time of the common due-window,the size of the due-window,the total absolute completion difference,the total completion time.For the second,we are subject to the constraint that the total cost with due window size and the total completion time cost is less than or equal to a fixed amount to minimize the total resource.We show that the problems are polynomial solvable by transforming them into assignment problems.Two optimal algorithms are given.