An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects

Abstract

[EN] This paper addresses a sequence dependent setup times no-wait flowshop with learning and forgetting effects to minimize total flowtime. This problem is NP-hard and has never been considered before. A position-based learning and forgetting effects model is constructed. Processing times of operations change with the positions of corresponding jobs in a schedule. Objective increment properties are deduced and based on them three accelerated neighbourhood construction heuristics are presented. Because of the simplicity and excellent performance shown in flowshop scheduling problems, an iterated greedy heuristic is proposed. The proposed iterated greedy algorithm is compared with some existing algorithms for related problems on benchmark instances. Comprehensive computational and statistical tests show that the presented method obtains the best performance among the compared methods. (C) 2018 Elsevier Inc. All rights reserved.