Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops |
| |
Affiliation: | 1. State Key Lab of Digital Manufacturing Equipment &Technology, Huazhong University of Science and Technology, Wuhan, China;2. School of Management, Wuhan University of Science and Technology, Wuhan, China;3. Walmart Technology, Bentonville, USA |
| |
Abstract: | We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules. |
| |
Keywords: | Scheduling Metaheuristics Flow shop Non-permutation schedules |
本文献已被 ScienceDirect 等数据库收录! |
|