Enhanced Iterated Local Search Algorithms for the Permutation Flow Shop Problem Minimizing Total Flow Time

Xingye Dong, Maciek Nowak, Ping Chen, Houkuan Huang

2013

Abstract

Flow shop scheduling minimizing total flow time is a famous combinatorial optimization problem. Many algorithms have been proposed to solve it. Among them, iterated local search (ILS) is a simple, efficient and effective one. However, in existing ILS, one basic insertion neighborhood is generally used, greatly limiting the search space. In this work, an enhanced iterated local search (EILS) is proposed, using a hybrid of insertion and swap neighborhoods. The perturbation method also plays an important role in ILS. Two perturbation methods, the insertion method and a destruction and construction heuristic are tested in this paper. Both perform significantly better in comparison to three state of the art algorithms, indicating that the hybrid use of insertion and swap neighborhoods is effective for the discussed problem. However, there is no significant difference between the destruction and construction and the insertion perturbation methods.

Paper Citation

in Harvard Style

Dong X., Nowak M., Chen P. and Huang H. (2013). Enhanced Iterated Local Search Algorithms for the Permutation Flow Shop Problem Minimizing Total Flow Time . In Proceedings of the 10th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 978-989-8565-70-9, pages 58-65. DOI: 10.5220/0004410100580065

in Bibtex Style

@conference{icinco13,
author={Xingye Dong and Maciek Nowak and Ping Chen and Houkuan Huang},
title={Enhanced Iterated Local Search Algorithms for the Permutation Flow Shop Problem Minimizing Total Flow Time},
booktitle={Proceedings of the 10th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2013},
pages={58-65},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004410100580065},
isbn={978-989-8565-70-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 10th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - Enhanced Iterated Local Search Algorithms for the Permutation Flow Shop Problem Minimizing Total Flow Time
SN - 978-989-8565-70-9
AU - Dong X.
AU - Nowak M.
AU - Chen P.
AU - Huang H.
PY - 2013
SP - 58
EP - 65
DO - 10.5220/0004410100580065