Machine scheduling with a rate-modifying activity
Machine scheduling with a rate-modifying activity
复制标题
DOI：
10.1016/s0377-2217(99)00066-1
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
C.Y.C.Y. Lee;V. Leon
中科院分区：
文献类型：
--
作者：
C.Y.C.Y. Lee;V. Leon
受电子装配线中常见问题的启发，本文研究了单机上的作业调度和速率修改活动问题。速率修改活动是改变所考虑的设备的生产速率的活动。因此，作业的处理时间取决于作业是安排在费率修改活动之前还是之后。所考虑的决策是什么时候安排的利率修改活动和顺序的工作，以优化一些性能指标。在本文中，我们开发多项式算法求解问题的最小化完工时间，和总完工时间分别。我们还开发了伪多项式算法求解问题的总加权完工时间的同意比假设下。我们证明了最小化最大延迟问题是NP-困难的，并给出了一个伪多项式时间算法来最优地解决它。
Motivated by a problem commonly found in electronic assembly lines, this paper deals with the problem of scheduling jobs and a rate-modifying activity on a single machine. A rate-modifying activity is an activity that changes the production rate of the equipment under consideration. Hence the processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. The decisions under consideration are when to schedule the rate-modifying activity and the sequence of jobs to optimize some performance measure. In this paper, we develop polynomial algorithms for solving problems of minimizing makespan, and total completion time respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally.