Single-machine scheduling problems with past-sequence-dependent setup times
Single-machine scheduling problems with past-sequence-dependent setup times
复制标题
DOI：
10.1016/j.ejor.2006.03.066
复制
发表时间：
2008-06-16
影响因子：
6.4
通讯作者：
Kyparisis, George J.
中科院分区：
文献类型：
--
作者：
Koulamas, Christos;Kyparisis, George J.
本文研究了单机调度问题，该问题的设置时间与已调度作业的长度成正比，即与过去序列相关或p-s-d设置时间。考虑以下目标函数：最大完成时间（makespan），总完成时间，完成时间的总绝对差值以及后两个目标函数的双标准组合。结果表明，具有p-s-d设置时间和任意上述目标函数的标准单机调度问题可在O（nlogn）时间内（其中n为作业数）通过排序过程得到解决。还表明，我们所有的结果都扩展到“学习”环境中，其中p-s-d设置时间不再是由于学习效应而已经经过的处理时间的线性函数。(C) 2006 Elsevier B.V.版权所有
This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlogn) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a "learning" environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects. (C) 2006 Elsevier B.V. All rights reserved.