TY - JOUR AU - Benavides, Alexander AU - Ritt, Marcus PY - 2015/04/08 Y2 - 2024/03/29 TI - Iterated Local Search Heuristics for Minimizing Total Completion Time in Permutation and Non-permutation Flow Shops JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 25 IS - 1 SE - Technical Papers DO - 10.1609/icaps.v25i1.13710 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/13710 SP - 34-41 AB - <p> We study the improvement of non-permutation over permutation schedules in flow shops when minimizing the total completion time. We solve both problems by a two-phase heuristic. The first phase uses an iterated local search to find a good permutation schedule. The second phase explores non-permutation schedules using an effective insertion neighborhood, that permits to anticipate or delay a job when passing from one machine to the next. In computational experiments we show that both phases yield state-of-the-art results. We find that allowing non-permutation schedules can reduce the total completion considerably with a moderate extra effort, and without increasing the buffer size needed during processing. We conclude that non-permutation schedules can be viable alternative to permutation schedules in flow shops. </p> ER -