New high performing heuristics for minimizing makespan in permutation flowshops☆ Export

@article{citeulike:5013327, abstract = {The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.}, author = {Rad, S. and Ruiz, R. and Boroojerdian, N.}, citeulike-article-id = {5013327}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.omega.2007.02.002}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0305048307000217}, doi = {10.1016/j.omega.2007.02.002}, issn = {03050483}, journal = {Omega}, keywords = {heuristics, phd, scheduling}, month = {April}, number = {2}, pages = {331--345}, posted-at = {2009-06-29 16:05:28}, priority = {2}, title = {New high performing heuristics for minimizing makespan in permutation flowshops☆}, url = {http://dx.doi.org/10.1016/j.omega.2007.02.002}, volume = {37}, year = {2009} }

TY - JOUR ID - citeulike:5013327 L3 - citeulike-article-id:5013327 N2 - The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison. IS - 2 JF - Omega SN - 03050483 EP - 345 TI - New high performing heuristics for minimizing makespan in permutation flowshops☆ VL - 37 SP - 331 KW - heuristics KW - phd KW - scheduling AU - Rad, S AU - Ruiz, R AU - Boroojerdian, N PY - 2009/04// UR - http://dx.doi.org/10.1016/j.omega.2007.02.002 ER -