Online supplement to:
Benavides, A. J., & Ritt, M. (2016). Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops. Computers & Operations Research, 66, 160-169. doi:10.1016/j.cor.2015.08.001.
Mirror: http://inf.ufrgs.br/algopt/npfs/
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.
@article{benavides2016twoSEH,
title={Two simple and effective heuristics for minimizing
the makespan in non-permutation flow shops},
author={Benavides, Alexander J and Ritt, Marcus},
journal={Computers \& Operations Research},
year={2016},
volume={66},
pages={160--169},
publisher={Elsevier},
doi={10.1016/j.cor.2015.08.001}
}
Alexander J. Benavides, Marcus Ritt.
Below you can download the following data files containing the results presented in the article:
Detailed results on the comparison of variants of the proposed iterated greedy algorithm on the instances of Taillard in Table 2: IGA , NPS+IGA , IGA(LS) , NPS+IGA(LS) .
Detailed results on the comparison of constructive heuristics on the instances of Taillard in Table 3: NEH, KK2, KM, FF, NFS.
Detailed results on the comparison to Lin and Ying (2009) and Rossi and Lanzetta (2013) on the instances of Demirkon et al. (1998) in Table 5: Time LY/6, Time 30nm², results from the literature.
Detailed results on the comparison to Yagmahan and Yenisey (2010) and Rossi and Lanzetta (2013) on the first 28 instances of Taillard (1993) in Table 6: Time 30nm , Time 30nm², results from the literature.
Detailed results on the instances of Taillard (1993) in Table 7: Time 30nm, Time 30nm².
Detailed results on the comparison to state-of-the-art heuristics from the literature for permutation schedules on the instances of Taillard (1993) in Table 8: Time 30nm, Time 30nm², our implementation of HGA, results from the literature: FF, NGV.
Detailed results on the comparison of buffer sizes for permutation and non-permutation solutions on the instances of Taillard (1993) in Table 9: permutation schedules, non-permutation schedules.
Source code (deprecated, please review this paper with better results).