Single machine scheduling with a restricted rate‐modifying activity
Single machine scheduling with a restricted rate‐modifying activity
复制标题
DOI：
10.1002/nav.20083
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Yong He;Min Ji;T. Cheng
中科院分区：
文献类型：
--
作者：
Yong He;Min Ji;T. Cheng
在本文中，我们考虑的问题，调度一组工作在一台机器上的速度修改活动可以执行。速率修改活动是改变机器的生产速率的活动。因此，作业的处理时间是一个变量，这取决于它是在费率修改活动之前还是之后调度的。我们假设速率调整活动只能在某些预定的时间点发生，这是文献中讨论的类似问题的约束情况。正在考虑的决策是是否以及何时安排费率修改活动，以及如何对作业进行排序以最大限度地减少某些目标。研究了最小化完工时间和总完工时间的问题。我们首先分析了这两个问题的计算复杂性的大多数可能的版本。分析表明，即使在某些特殊情况下，该问题也是NP-困难的。此外，对于最大完工时间问题的NP-困难情形，我们给出了一个伪多项式时间最优算法和一个完全多项式时间近似方案。对于总完工时间问题，我们提供了一个伪多项式时间最优算法的情况下，具有一致的修改率。© 2005 Wiley Periodicals，Inc.海军研究后勤，2005年
In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005