Online supplement to:
Benavides, A. J., & Ritt, M. (2018). Fast heuristics for minimizing the makespan in non‑permutation flow shops. Computers & Operations Research, 100, 230-243. doi:10.1016/j.cor.2018.07.017.
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²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.
@article{benavides2018fast,
title={Fast heuristics for minimizing the makespan
in non-permutation flow shops},
author={Benavides, Alexander J and Ritt, Marcus},
journal={Computers \& Operations Research},
year={2018},
volume={100},
pages={230--243},
publisher={Elsevier},
doi={10.1016/j.cor.2018.07.017}
}
Alexander J. Benavides, Marcus Ritt.
Below you can download the following data files containing the results presented in the article:
Performance of variants of the constructive BR heuristic in Table 6.
Performance of constructive heuristics on the instances of Taillard in Table 7.
Performance of constructive heuristics on all instances in Table 8: Taillard, VRF-small, VRF-large.
Performance of permutation IG heuristics on the instances of Taillard in Table 9.
Performance of the non-permutation IG heuristics on the instances of Taillard in Table 10.
Comparison of state-of-the-art methods for the permutation and non-permutation FSSP on the instances of Taillard in Table 12: contained in data files of items 5 and 6.
Comparison of state-of-the-art methods for the permutation and non-permutation FSSP on all instances in Table 13: additionally to above tables for the non-permutation flow shop VRF-small, VRF-large, and for the non-permutation flow shop VRF-small, VRF-large.
Number of iterations in Table 14: see time and number of iterations in the above data files.