A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems
A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems
复制标题
DOI：
10.1007/s00170-009-2419-7
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Chiuh-Cheng Chyu;Wei-Shung Chang
中科院分区：
文献类型：
--
作者：
Chiuh-Cheng Chyu;Wei-Shung Chang
本文研究了与作业顺序和机器相关的设置时间不相关的并行机器调度问题。不允许抢占作业，优化准则为同时最小化总加权流时间和总加权延迟时间。该问题适用于TFT-LCD、汽车、纺织等行业。本文提出了一种Pareto进化方法来解决双目标调度问题。通过文献中方法生成的一组实例，评估了该方法使用不同编码和解码方案的性能，并与两种多目标模拟退火算法的性能进行了比较。实验结果表明，基于随机密钥表示和加权二部匹配优化方法的Pareto进化方法在计算次数相似的情况下，在接近度度量方面优于其他算法。此外，虽然该方法在多样性度量方面没有提供最佳分布，但它找到了大多数参考解。
This paper addresses the unrelated parallel machine scheduling problem with job sequence- and machine-dependent setup times. The preemption of jobs is not permitted, and the optimization criteria are to simultaneously minimize total weighted flow time and total weighted tardiness. The problem has applications in industries such as TFT-LCD, automobile, and textile manufactures. In this study, a Pareto evolutionary approach is proposed to solve the bi-objective scheduling problem. The performance of this approach using different encoding and decoding schemes is evaluated and is compared with that of two multi-objective simulated annealing algorithms via a set of instances generated by a method in the literature. The experimental results indicate that the Pareto evolutionary approach using random key representation and weighted bipartite matching optimization method outperforms the other algorithms in terms of closeness metric, based on similar computation times. Additionally, although the proposed method does not provide the best distribution in terms of diversity metric, it found most of the reference solutions.