Just-in-time scheduling with controllable processing times on parallel machines
Just-in-time scheduling with controllable processing times on parallel machines
复制标题
DOI：
10.1007/s10878-009-9270-5
复制
发表时间：
2010-04
影响因子：
1
通讯作者：
Yaron Leyvand;D. Shabtay;G. Steiner;Liron Yedidsion
中科院分区：
文献类型：
--
作者：
Yaron Leyvand;D. Shabtay;G. Steiner;Liron Yedidsion
我们研究并行机器上具有可控处理时间的调度问题。我们的目标是最大限度地增加在到期日准确完成的工作的加权数量，并最大限度地减少总资源分配成本。我们考虑四种不同的模型来处理这两个标准。我们证明了其中三个问题即使在单台机器上也很困难，但有些令人惊讶的是，即使对于固定数量的不相关并行机器的一般情况，最大化集成目标函数的问题也可以在多项式时间内解决。对于问题的三难版本，具有固定数量的机器和离散资源类型，我们提供了伪多项式时间优化算法，将其转换为完全多项式时间近似方案。
We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are-hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three-hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.