Fast heuristics for minimizing the makespan in non-permutation flow shops. (December 2018)

• Record Type: Journal Article
• Authors: Benavides, Alexander J.; Ritt, Marcus
• Is Part Of: Computers & operations research. Volume 100(2018)
• Page Start: 230
• Page End: 243
• Publication Date: 2018-12
• Subjects: Scheduling -- Metaheuristics -- Flow shop -- Non-permutation schedules -- Makespan -- Iterated greedy algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.07.017
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We introduce a new permutation representation for non-permutation schedules. We extend the acceleration technique of Taillard (1990) to the new representation. We propose new, fast construction, improvement, and iterated greedy heuristics. The proposed heuristics dominate previous permutation and non-permutation heuristics. Most non-permutation schedules are shorter than the optimal permutation schedule. Abstract: We introduce a new permutation representation for non-permutation schedules, and show how the acceleration technique of Taillard can be extended to it. We propose three new heuristics for the non-permutation flow shop scheduling problem with makespan minimization: a constructive heuristic with the same time complexity as the well-known NEH heuristic, a non-permutation insertion local search with a time complexity O ( n 2 m ) for evaluating a neighbourhood on n jobs and m machines, the same as for the permutation insertion local search, and a reduced-neighbourhood best-improvement non-permutation local search with a time complexity of O ( nm ) per neighbourhood. These heuristics are combined into iterated greedy algorithms for the permutation and non-permutation flow shop scheduling problem. In extensive computational experiments we find that our iterated greedy algorithms produce better non-permutation schedules than other methods for the permutation and non-permutation flow shop scheduling problem, in the same computational time.