×

A generalized constructive algorithm using insertion-based heuristics. (English) Zbl 1349.90335

Summary: In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

PERMGEN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Campbell, A. M.; Savelsbergh, M., Efficient insertion heuristics for vehicle routing and scheduling problems, Transp Sci, 38, 3, 369-370 (2004)
[2] Burdett, R. L.; Kozan, E., An integrated approach for earthwork allocation, sequencing and routing, Eur J Oper Res, 238, 741-759 (2014) · Zbl 1338.90228
[3] Fleszar, K., Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts, Comput Oper Res, 40, 463-474 (2013) · Zbl 1349.90856
[4] Garcia-Villoria, A.; Salhi, S.; Corominas, A.; Pastor, R., Hyper-heuristic approaches for the response time variability problem, Eur J Oper Res, 211, 160-169 (2011) · Zbl 1218.90224
[5] Kirlik, G.; Sipahiogly, A., Capacitated arc routing problem with deadheading demands, Comput Oper Res, 39, 2380-2394 (2012) · Zbl 1251.90053
[6] McKendall, A. R.; Hakobyan, A., Heuristics for the dynamic facility layout problem with unequal-area departments, Eur J Oper Res, 201, 171-182 (2010) · Zbl 1177.90259
[7] Lust, T.; Roux, O.; Riane, F., Exact and heuristic methods for the selective maintenance problem, Eur J Oper Res, 197, 1166-1177 (2009) · Zbl 1176.90506
[8] Lan, G.; DePuy, G. W.; Whitehouse, G. E., An effective and simple heuristic for the set covering problem, Eur J Oper Res, 176, 1387-1403 (2007) · Zbl 1102.90048
[9] Lu, Q.; Dessouky, M. M., A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows, Eur J Oper Res, 175, 672-687 (2006) · Zbl 1142.90477
[10] Ghiani, G.; Lagana, D.; Musmanno, R., A constructive heuristic for the Undirected Rural Postman Problem, Comput Oper Res, 33, 3450-3457 (2006) · Zbl 1094.90040
[11] Glover, F.; Gutin, G.; Yeo, A.; Zverovich, A., Construction heuristics for the asymmetric TSP, Eur J Oper Res, 129, 555-568 (2001) · Zbl 1125.90402
[12] Wex, F.; Schryen, G.; Feuerriegel, S.; Dirk, Neumann, Emergency response in natural disaster management: allocation and scheduling of rescue units, Eur J Oper Res, 235, 697-708 (2014) · Zbl 1305.90264
[13] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega - Int J Manag Sci, 11, 1, 91-95 (1983)
[14] Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 278-285 (1993) · Zbl 0769.90052
[17] Knuth, D. E., The art of computer programming. Vol. 3, sorting and searching, 12-13 (1973), Addison-Wesley · Zbl 0302.68010
[18] Pinedo, M., Scheduling: theory, algorithms and systems (2010), Springer: Springer New York
[19] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Nav Res Logist Q, 1, 61-68 (1954) · Zbl 1349.90359
[20] Watson, J. P.; Barbulescu, L.; Whitley, L. D.; Howe, A. E., Contrasting structured and random permutation flowshop scheduling problems: search space topology and algorithm performance, ORSA J Comput, 14, 2, 98-123 (2002) · Zbl 1238.90072
[21] Framinan, J. M.; Gupta, J. N.D.; Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, J Oper Res Soc, 55, 1243-1255 (2004) · Zbl 1088.90022
[22] Gupta, Y. N.D.; Stafford, E. F.S., Flowshop scheduling research after five decades, Eur J Oper Res, 169, 699-711 (2006) · Zbl 1079.90001
[23] Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, Eur J Oper Res, 165, 2, 479-494 (2005) · Zbl 1066.90038
[24] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Comparison of heuristics for flowtime minimization in permutation flowshops, Comput Oper Res, 32, 1237-1254 (2005) · Zbl 1074.90017
[25] Hejazi, S.; Saghafian, S., Flowshop-scheduling problems with makespan criterion: a review, Int J Prod Res, 43, 14, 2895-2929 (2005) · Zbl 1068.90059
[26] Kalczynski, P. J.; Kamburowski, J., On the NEH heuristic for minimizing the makespan in permutation flowshops, Omega - Int J Manag Sci, 35, 53-60 (2007)
[27] Framinan, J. M.; Leisten, R.; Rajendran, C., Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem, Int J Prod Res, 41, 1, 121-148 (2003) · Zbl 1038.90027
[28] Kalczynski, P. J.; Kamburowski, J., An improved NEH heuristic to minimize makespan in permutation flow shops, Comput Oper Res, 35, 3001-3008 (2008) · Zbl 1144.90499
[29] Fernandez-Vigas, V.; Framinan, J. M., On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Comput Oper Res, 45, 60-67 (2014) · Zbl 1348.90256
[30] Dong, X.; Huang, H.; Chen, P., An improved NEH-based heuristic for the permutation flow shop problem, Comput Oper Res, 35, 12, 3962-3968 (2008) · Zbl 1278.90150
[31] Ruiz, R.; Stutzle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur J Oper Res, 177, 2033-2049 (2007) · Zbl 1110.90042
[32] Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, Eur J Oper Res, 47, 1, 67-74 (1990) · Zbl 0702.90043
[33] Grabowski, J.; Pempera, J., New block properties for the permutation flow shop problem with application in tabu search, J Oper Res Soc, 52, 2, 210-220 (2001) · Zbl 1131.90359
[35] Rad, S. F.; Ruiz, R.; Boroojerdian, N., New high performing heuristics for minimizing makespan in permutation flowshops, Omega, 37, 331-345 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.