Skip to main content
SpringerLink
Log in

On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

Abstract

We use genetic programming to find variants of the well-known Nawaz, En-score and Ham (NEH) heuristic for the permutation flow shop problem. Each variant uses a different ranking function to prioritize operations during schedule construction. We have tested our ideas on problems where jobs have release times, due dates, and weights and have considered five objective functions: makespan, sum of tardiness, sum of weighted tardiness, sum of completion times and sum of weighted completion times. The implemented genetic programming system has been carefully tuned and used to generate one variant of NEH for each objective function. The new NEHs, obtained with genetic programming, have been compared with the original NEH and randomized NEH versions on a large set of benchmark problems. Our results indicate that the NEH variants discovered by genetic programming are superior to the original NEH and its stochastic version on most of the problems investigated.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6

References

  • Aickelin U and Li J (2007). An estimation of distribution algorithm for nurse scheduling. Ann Opns Res 155: 289–309.

    Article  Google Scholar 

  • Bader-El-Den M and Poli R (2008). Generating sat local-search heuristics using a gp hyperheuristic framework. In: Monmarché N et al. (eds). Proceedings of Evolution Artificielle, Vol. 4926, of Lecture Notes in Computer Science, Springer-Verlag: Berlin, pp 37–49.

    Google Scholar 

  • Bai R and Kendall G (2005). An investigation of automated planograms using a simulated annealing based hyper-heuristic. In: Ibaraki T, Nonobe K and Yagiura M (eds). Metaheuristics: Progress as Real Problem Solvers—(Operations Research/Computer Science Interfaces Series, Vol. 32), Springer: Berlin, Heidelberg, New York, pp 87–108.

    Chapter  Google Scholar 

  • Bai R, Burke EK and Kendall G (2008). Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation. J Opl Res Soc 59: 1387–1397.

    Article  Google Scholar 

  • Banzhaf W, Nordin P, Keller R and Francone F (eds). (1998). Genetic Programming—An Introduction. Morgan Kaufmann: San Francisco, CA.

    Book  Google Scholar 

  • Bartz-Beielstein T (2006). Experimental Research in Evolutionary Computation. Natural Computing Series. Springer: Berlin.

    Google Scholar 

  • Burke E, Hart E, Kendall G, Newall J, Ross P and Schulenburg S (2003a). Hyper-heuristics: An emerging direction in modern search technology. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Springer: Berlin, pp 457–474.

    Chapter  Google Scholar 

  • Burke EK, Kendall G and Soubeiga E (2003b). A tabu-search hyper-heuristic for timetabling and rostering. J Heuristics 9: 451–470.

    Article  Google Scholar 

  • Burke EK, Hyde M and Kendall G (2006a). Evolving bin packing heuristics with genetic programming. In: Runarsson TP et al. (eds). Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN 2006), Vol. 4193 of Lecture Notes in Computer Science. Springer: Berlin, pp 860–869.

    Google Scholar 

  • Burke EK, MacCarthy BL, Petrovic S and Qu R (2006b). Multiple-retrieval case based reasoning for course timetabling problems. J Opl Res Soc 57: 148–162.

    Article  Google Scholar 

  • Burke EK, Petrovic S and Qu R (2006c). Case-based heuristic selection for timetabling problems. J Sched 9: 115–132.

    Article  Google Scholar 

  • Burke EK, Hyde MR, Kendall G and Woodward JR (2007a). The scalability of evolved on line bin packing heuristics. In: Srinivasan D and Wang L (eds). 2007 IEEE Congress on Evolutionary Computation. IEEE Computational Intelligence Society, IEEE Press: Singapore, pp 2530–2537.

    Chapter  Google Scholar 

  • Burke EK, McCollum B, Meisels A, Petrovic S. and Qu R (2007b). A graph-based hyper-heuristic for educational timetabling problems. Eur J Opl Res 176: 177–192.

    Article  Google Scholar 

  • Burke K, Hyde MR, Kendall G and Woodward J (2007c). Automatic heuristic generation with genetic programming: Evolving a jack-of-all-trades or a master of one. In: Thierens D et al. (eds). Proceedings of the 9th annual conference on Genetic and evolutionary computation, Vol. 2. ACM: New York, pp 1559–1565.

    Chapter  Google Scholar 

  • Burke K, Hyde MR, Kendall G, Ochoa G, Ozcan E and Woodward J (2009). Handbook of Metaheuristics. Chap. A Classification of Hyper-heuristic Approaches. International Series in Operations Research & Management Science. Springer: Berlin.

  • Cowling P, Kendall G and Soubeiga E (2000). A hyperheuristic approach to scheduling a sales summit. In: Burke EK and Erben W (eds). LNCS 2079, Practice and Theory of Automated Timetabling III: Third International Conference PATAT 2000. Springer-Verlag: Berlin, pp 176–190.

    Google Scholar 

  • Cowling P, Kendall G and Han L (2002). An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Fogel DB et al. (eds). Proceedings of Congress on Evolutionary Computation (CEC2002). IEEE: Portland, USA, pp 1185–1190.

    Google Scholar 

  • Denzinger J, Fuchs M and Fuchs M (1997). High performance ATP systems by combining several ai methods. In: Furukawa K (ed). Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI ’97). IJCAI: Nagoya, Japan, pp 102–107.

    Google Scholar 

  • Dimopoulos C and Zalzala AMS (1999). A genetic programming heuristic for the one-machine total tardiness problem. In: Angeline J et al. (eds). Proceedings of the 1999 Congress on Evolutionary Computation (CEC ’99). IEEE: Portland, USA, pp 2207–2214.

    Google Scholar 

  • Dimopoulos C and Zalzala AMS (2001). Investigating the use of genetic programming for a classic one-machine scheduling problem. Adv Eng Software 32: 489–498.

    Article  Google Scholar 

  • Fisher H and Thompson GL (1961). Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF (ed). In Factory Scheduling Conference, Carnegie Institute of Technology: Pittsburgh, USA, pp 225–251.

    Google Scholar 

  • Framinan JM, Gupta JND and Leisten R (2004). A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Int Prod Res Soc 55: 1243–1255.

    Google Scholar 

  • Framinan JM, Leisten R and Rajendran C (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or fiowtime in the static permutation flowshop sequencing problem. Int Prod Res 41: 121–148.

    Article  Google Scholar 

  • Fukunaga A (2002). Automated discovery of composite SAT variable selection heuristics. In: Dechter R and Sutton R (eds). Proceedings of the National Conference on Artificial Intelligence (AAAI). AAAI press: Edmonton, Canada, pp 641–648.

    Google Scholar 

  • Fukunaga AS (2004). Evolving local search heuristics for SAT using genetic programming. In: Deb K et al. (eds). Genetic and Evolutionary Computation—GECCO-2004, Part-II, Lecture Notes in Computer Science, Springer-Verlag: Berlin, pp 483–494.

    Chapter  Google Scholar 

  • Fukunaga AS (2008). Automated discovery of local search heuristics for satisfiability testing. Evol Comput 16 (1): 31–61.

    Article  Google Scholar 

  • García RR and Maroto C (2006). A genetic algorithm for hybrid flow shops with sequence dependent setup times and machine elegibility. Eur J Opl Res 169: 781–800.

    Article  Google Scholar 

  • Geiger CD, Uzsoy R and Aytuğ H (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. J Sched 9: 7–34.

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequence and scheduling: A survey. Ann Discrete Math 5: 287–326.

    Article  Google Scholar 

  • Kalczynski PJ and Kamburowski J (2007). On the NEH heuristic for minimizing the makespan in permutation flowshops. OMEGA-Int J Mngt Sci 35: 53–60.

    Article  Google Scholar 

  • Keller RE and Poli R (2007a). Linear genetic programming of parsimonious metaheuristics. In: Srinivasan D and Wang L (eds). Proceedings of IEEE Congress on Evolutionary Computation (CEC 2007). IEEE: Portland, USA, pp 4508–4515.

    Chapter  Google Scholar 

  • Keller RE and Poli R (2007b). Cost-benefit investigation of a genetic-programming hyperheuristic. In: Monmarché N et al. (eds). Proceedings of Evolution Artificielle, Vol. 4926 of Lecture Notes in Computer Science. Springer-Verlag: Berlin, pp 13–24.

    Google Scholar 

  • Kendall G and Mohamad M (2004). Channel assignment optimisation using a hyper-heuristic. In: Proceedings of the 2004 IEEE Conference on Cybernetic and Intelligent Systems (CIS2004), IEEE: Portland, USA, pp 790–795.

    Google Scholar 

  • Kibria RH and Li Y (2006). Optimizing the initialization of dynamic decision heuristics in DPLL SAT solvers using genetic programming. In: Collet P et al. (eds). Proceedings of the 9th European Conference on Genetic Programming, Vol. 3905 of Lecture Notes in Computer Science. Springer-Verlag: Berlin, pp 331–340.

    Google Scholar 

  • Koza JR (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press: Cambridge, MA, USA.

    Google Scholar 

  • Koza JR (1994). Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press: Cambridge, MA, USA.

    Google Scholar 

  • Koza JR, Bennett FH, Andre D and Keane KA (1999). Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann: Cambridge, MA, USA.

    Google Scholar 

  • Koza JR, Keane KA, Streeter MJ, Mydlowec W, Yu J and Lanza H (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Springer: Berlin.

    Google Scholar 

  • Koza JR and Poli R (2005). Genetic programming. In: Burke EK and Kendall G (eds). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Chap. 5, Springer: Berlin, pp 127–164.

    Chapter  Google Scholar 

  • Oltean M (2003). Evolving evolutionary algorithms for function optimization. In: Chen K et al. (eds). Proceedings of the 5th International Workshop on Frontiers in Evolutionary Algorithms. The Research Triangle Park: N Carolina, USA, pp 295–298.

    Google Scholar 

  • Oltean M (2005). Evolving evolutionary algorithms using linear genetic programming. Evol Comput 13: 387–410.

    Article  Google Scholar 

  • Montgomery DC (2005). Design and Analysis of Experiments. 6th edn, J. Wiley & Sons, Inc: New Jersey.

    Google Scholar 

  • Nawaz M, Enscore-Jr. E and Ham I (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA-Int J Mngt Sci 11 (1): 91–95.

    Article  Google Scholar 

  • Petrovic S, Fayad C, Petrovic D, Burke E and Kendall G (2008). Fuzzy job shop scheduling with lot-sizing. Ann Opns Res 159: 275–292.

    Article  Google Scholar 

  • Pinedo M (2002). Scheduling Theory, Algorithms and Systems. Prentice Hall: New Jersey.

    Google Scholar 

  • Poli R, Di Chio C and Langdon WB (2005). Exploring extended particle swarms: A genetic programming approach. In: Beyer HG et al. (eds). GECCO 2005: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, ACM Press: NY, pp 169–176.

    Google Scholar 

  • Poli R, Langdon WB and McPhee NF (2008). A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk. With contributions by J. R. Koza.

  • Rodríguez JAV, Petrovic S and Salhi A (2007). A combined meta-heuristic with hyper-heuristic approach to the scheduling of the hybrid flow shop with sequence dependent setup times and uniform machines. In: Baptiste P, Kendall G, Munier-Kordon A and Sourd F (eds). Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications. MISTA: Paris, France, pp 506–513.

    Google Scholar 

  • Ross P (2005). Hyper-heuristics. In: Burke EK and Kendall G (eds). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Chap. 17, Springer: Berlin, pp 529–556.

    Chapter  Google Scholar 

  • Ross P, Schulenburg S, Marín-Blázquez JG and Hart E (2002). Hyper-heuristics: Learning to combine simple heuristics in bin-packing problems. In: Langdon WB et al. (eds). Genetic and Evolutionary Computation Conference (GECCO 2002). Morgan Kaufmann: NJ.

    Google Scholar 

  • Ruiz R and Maroto C (2005). A comprehensive review and evaluation of permutation flowshop heuristics. Eur Opl Res 165: 479–494.

    Article  Google Scholar 

  • Ruiz R and Stützle TG (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur Opl Res 177: 2033–2049.

    Article  Google Scholar 

  • Ruiz-Torres AJ and Centeno G (2008). Minimizing the number of late jobs for the permutation flowshop problem with secondary resources. Comput Opns Res 35: 1227–1249.

    Article  Google Scholar 

  • Taillard E (1990). Some efficient heuristic methods for the flow shop sequencing problem. Eur Opl Res 47: 65–74.

    Article  Google Scholar 

  • Taillard E (1993). Benchmarks for basic scheduling problems. Eur J Op Res 64: 278–285.

    Article  Google Scholar 

  • Tay JC and Ho NB (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54: 453–473.

    Article  Google Scholar 

  • Terashima-Marín H, Zárate CJF, Ross P and Valenzuela-Rendón M (2006). A ga-based method to produce generalized hyper-heuristics for the 2d-regular cutting stock problem. In: Cattolico M et al. (eds). Proceedings of the 8th annual conference on Genetic and evolutionary computation (GECCO 2006), ACM press: New York.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Nottingham, Nottingham, UK

    J A Vázquez-Rodríguez & G Ochoa

Authors
  1. J A Vázquez-Rodríguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G Ochoa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J A Vázquez-Rodríguez.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vázquez-Rodríguez, J., Ochoa, G. On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming. J Oper Res Soc 62, 381–396 (2011). https://doi.org/10.1057/jors.2010.132

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2010.132

Keywords

Search

Navigation