Isomorphic scheduling problems
Isomorphic scheduling problems
复制标题
DOI：
10.1007/s10479-012-1222-2
复制
发表时间：
2014-02
影响因子：
4.8
通讯作者：
Stanisław Gawiejnowicz;A. Kononov
中科院分区：
文献类型：
--
作者：
Stanisław Gawiejnowicz;A. Kononov
我们考虑了构成一类新的相互关联的调度问题对的同构调度问题的一般性质。任何这样的对都由具有固定作业加工时间的调度问题和加工时间是作业开始时间的比例线性函数的时间相关的调度问题组成。为了形式化地引入这一类，我们首先建立了一个具有固定作业处理时间的一般调度问题，并通过将一般问题的实例一对一地转换为具有比例线性作业处理时间的时变调度问题实例来定义同构问题。其次，我们证明了同构调度问题的基本性质，并说明了如何将具有固定作业处理时间的调度问题的多项式算法转化为原问题的比例线性对应的多项式算法。最后，我们展示了同构问题的相关近似算法。应用这些结果，我们建立了时间相关并行机调度问题的新的最坏结果，并证明了许多具有比例线性作业处理时间的单机和专用机器时间相关调度问题是多项式可解的。
We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.