Parallel machine scheduling with a convex resource consumption function
Parallel machine scheduling with a convex resource consumption function
复制标题
DOI：
10.1016/j.ejor.2004.12.008
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
D. Shabtay;Moshe Kaspi
中科院分区：
文献类型：
--
作者：
D. Shabtay;Moshe Kaspi
本文研究了一类相同并行机上的工件调度问题，其中工件的加工时间是通过分配一个不可更新的公共有限资源来控制的。其目标是将工件分配到机器上，对每台机器上的工件进行排序，并分配资源，使最大完工时间或完工时间之和最小。对抢占式作业和非抢占式作业都进行了优化。对于工件不可抢占的最大完工时间问题，我们应用等效负荷法来分配资源，从而将问题转化为一个组合问题。简化的问题被证明是NP-困难的。如果允许抢占作业，则最大完工时间问题在O（n2）时间内可解。这个问题的优先约束的一些特殊情况下，最小化的完成时间的总和的问题是在O（nlogn）时间内可解的。
We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n2) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(nlogn) time.