Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect
Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect
复制标题
DOI：
10.1016/j.cie.2010.04.008
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Dariusz Okolowski;Stanisław Gawiejnowicz
中科院分区：
文献类型：
--
作者：
Dariusz Okolowski;Stanisław Gawiejnowicz
本文考虑了一个具有学习效应和最大完工时间目标的并行机排序问题。学习效果对作业处理时间的影响是由一般DeJong的学习曲线建模。对于这个NP难问题，我们提出了两个精确算法：一个顺序的分支定界算法和一个并行的分支定界算法。我们还提出了这些算法的计算集群上的实验评估结果。最后，我们使用精确的算法来估计两个贪婪启发式调度算法的性能。
We consider a parallel-machine scheduling problem with a learning effect and the makespan objective. The impact of the learning effect on job processing times is modelled by the general DeJong’s learning curve. For this NP-hard problem we propose two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. We also present the results of experimental evaluation of these algorithms on a computational cluster. Finally, we use the exact algorithms to estimate the performance of two greedy heuristic scheduling algorithms for the problem.