Automatic generation of iterated greedy algorithms for the non-permutation flow shop scheduling problem with total completion time minimization. (January 2022)

• Record Type: Journal Article
• Authors: Brum, Artur; Ruiz, Rubén; Ritt, Marcus
• Is Part Of: Computers & industrial engineering. Volume 163(2022)
• Publication Date: 2022-01
• Subjects: Non-permutation flow shop -- Total completion time -- Iterated greedy -- Automatic algorithm configuration; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107843
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Non-permutation schedules allow shorter total completion times. We combine individual components to generate algorithms. We use an automatic approach to generate eleven iterated greedy algorithms. Experiments show that all the generated algorithms improve the state of the art. Abstract: In this paper we address the non-permutation flow shop scheduling problem, a more general variant of the flow shop problem in which the machines can have different sequences of jobs. We aim to minimize the total completion time. We propose a template to generate iterated greedy algorithms, and use an automatic algorithm configuration to obtain efficient methods. This is the first automated approach in the literature for the non-permutation flow shop scheduling problem. The algorithms start by building a high-quality permutation solution, which is then improved during a second phase that generates non-permutation solutions by changing the job order on some machines. The obtained algorithms are evaluated against two well-known benchmarks from the literature. The results show that they can find better schedules than the state-of-the-art methods for both the permutation and non-permutation flow shop scheduling problems in comparable experimental conditions, as evidenced by comprehensive computational and statistical testing. We conclude that using non-permutation schedules is a viable alternative to reduce the total completion time that production managers should consider.