Uniform parallel machine scheduling problems with fixed machine cost
Uniform parallel machine scheduling problems with fixed machine cost
复制标题
DOI：
10.1007/s11590-016-1096-3
复制
发表时间：
2016-11
影响因子：
1.6
通讯作者：
Kai Li;Hui-juan Zhang;B. Cheng;P. Pardalos
中科院分区：
文献类型：
--
作者：
Kai Li;Hui-juan Zhang;B. Cheng;P. Pardalos
在云制造的背景下，研究了两个机器费用固定的均匀平行机调度问题。目标是在总费用预算给定的情况下，最小化最大完工时间。所有的工作都是同质的，即，作业的处理时间相同。研究了非抢占和抢占问题。对于非抢占式问题，给出了一个近似算法，其中第一次不能被选择的机器的个数为。对于抢占式问题，我们给出了一个算法，其最坏情况界等于。初步的实验结果表明，所提出的算法是合理的准确性相比，下限。
This paper considers two uniform parallel machine scheduling problems with fixed machine cost under the background of cloud manufacturing. The goal is to minimize the makespan with a given budget of total cost,. All the jobs are homogeneous, i.e., the processing times of the jobs are identical. Non-preemptive and preemptive problems are studied. For the non-preemptive problem, we give a-approximation algorithm, wherehis the number of the machine which can not be selected the first time. For the preemptive problem, we give an algorithm whose worst-case bound equals to. Preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.