A Self-adaptive Iterated Local Search Algorithm on the Permutation Flow Shop Scheduling Problem

Xingye Dong, Maciek Nowak, Ping Chen, Youfang Lin

2014

Abstract

Iterated local search (ILS) is a simple, effective and efficient metaheuristic, displaying strong performance on the permutation flow shop scheduling problem minimizing total flow time. Its perturbation method plays an important role in practice. However, in ILS, current methodology does not use an evaluation of the search status to adjust the perturbation strength. In this work, a method is proposed that evaluates the neighborhoods around the local optimum and adjusts the perturbation strength according to this evaluation using a technique derived from simulated-annealing. Basically, if the neighboring solutions are considerably worse than the best solution found so far, indicating that it is hard to escape from the local optimum, then the perturbation strength is likely to increase. A self-adaptive ILS named SAILS is proposed by incorporating this perturbation strategy. Experimental results on benchmark instances show that the proposed perturbation strategy is effective and SAILS performs better than three state of the art algorithms.

Paper Citation

in Harvard Style

Dong X., Nowak M., Chen P. and Lin Y. (2014). A Self-adaptive Iterated Local Search Algorithm on the Permutation Flow Shop Scheduling Problem . In Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 978-989-758-039-0, pages 378-384. DOI: 10.5220/0005092003780384

in Bibtex Style

@conference{icinco14,
author={Xingye Dong and Maciek Nowak and Ping Chen and Youfang Lin},
title={A Self-adaptive Iterated Local Search Algorithm on the Permutation Flow Shop Scheduling Problem},
booktitle={Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2014},
pages={378-384},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005092003780384},
isbn={978-989-758-039-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - A Self-adaptive Iterated Local Search Algorithm on the Permutation Flow Shop Scheduling Problem
SN - 978-989-758-039-0
AU - Dong X.
AU - Nowak M.
AU - Chen P.
AU - Lin Y.
PY - 2014
SP - 378
EP - 384
DO - 10.5220/0005092003780384