期刊
COMPUTERS & OPERATIONS RESEARCH
卷 117, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2019.104839
关键词
Flowshop scheduling; No-idle permutation; NEH; IGA
With the no-idle constraint, a machine has to process a job after finishing the previous one without any interruption. The start time of the first job on each machine must thus be delayed to meet this condition. In this paper, a new Iterated Greedy Algorithm (IGA) is presented for no-idle flowshop scheduling with the objective of minimizing the total tardiness. For the initialization phase, a variant of the NEH procedure is developed. Then, we propose a new variable local search based on an insert move with two different job selection mechanisms. A tardiness-guided job selection procedure, a job-dependent parameter and an insert-swap based method are further introduced in the destruction-construction phases. While most of the related studies have used a fixed probability for accepting new or non-improving solutions, we propose a time-dependent probability that allows our algorithm to focus on exploration in early iterations and exploitation in later iterations. Comprehensive computational experiments show that the proposed IGA is superior in terms of solution quality than state-of-the-art algorithms for the problem at hand. As a result, more than 50% of the existing best solutions for the benchmark instances tested have been updated. (C) 2019 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据