期刊
KNOWLEDGE-BASED SYSTEMS
卷 172, 期 -, 页码 15-32出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.knosys.2019.02.005
关键词
Symbiotic organisms search algorithm; Unrelated parallel machine scheduling; Local search improvement strategy; Simulated annealing; Sequence dependent setup times
This paper deliberates on the non-pre-emptive unrelated parallel machine scheduling problem with the objective of minimizing makespan. Machine and job sequence dependent set-up times are considered for the proposed scheduling methods, which are NP-hard, even without set-up times. The addition of sequence dependent setup times introduces additional complexity to the problem, which makes it very difficult to find optimal solutions, especially for large scale problems. Due to the NP-hard nature of the problem at hand, three different approaches are proposed to solve the problem including: An Enhanced Symbiotic Organisms Search (ESOS) algorithm, a Hybrid Symbiotic Organisms Search with Simulated Annealing (HSOSSA) algorithm, and an Enhanced Simulated Annealing (ESA) algorithm. A local search procedure is incorporated into each of the three algorithms as an improvement strategy to enhance their solution qualities. The computational experiments carried out showed that ESOS and HSOSSA performed better than the other methods on large problem instances with 12 machines and 120 jobs. The performance of each method is measured by comparing the quality of its solutions to the optimal solutions for the varying problem combinations. The results of the proposed methods are also compared with other techniques from the literature. Moreover, a comprehensive statistical analysis was performed and the results obtained show that the proposed algorithms significantly outperform the compared methods in terms of generality, quality of solutions, and robustness for all problem instances. (C) 2019 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据