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

Created by W.Langdon from gp-bibliography.bib Revision:1.4549

  author =       "Jose Antonio Vazquez Rodriguez and Gabriela Ochoa",
  title =        "On the automatic discovery of variants of the {NEH}
                 procedure for flow shop scheduling using genetic
  journal =      "Journal of the Operational Research Society",
  year =         "2011",
  number =       "2",
  volume =       "62",
  pages =        "381--396",
  keywords =     "genetic algorithms, genetic programming, heuristics,
                 production, hyper-heuristics",
  URL =          "http://www.cs.stir.ac.uk/~goc/papers/NEHGP_JORS.pdf",
  URL =          "http://www.palgrave-journals.com/jors/journal/v62/n2/full/jors2010132a.html",
  DOI =          "doi:10.1057/jors.2010.132",
  URL =          "http://results.ref.ac.uk/Submissions/Output/944105",
  size =         "16 pages",
  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 prioritise 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 randomised 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
  bibdate =      "2011-01-25",
  bibsource =    "DBLP,
  uk_research_excellence_2014 = "This paper presents an automatic
                 genetic programming approach to design specialised
                 variants of the most successful constructive heuristic
                 for the well studied flow shop scheduling problem. The
                 proposed methodology significantly outperforms the
                 original heuristic on the benchmarks studied. Once a
                 variant of the heuristic, targeted to a class of
                 instances, is discovered, it can be applied to quickly
                 solve a new instance. The exploration of genetic
                 programming to generate new heuristics plays a key role
                 in a new major EPSRC programme grant (EP/J017515/1) of
                 pounds6.8M between UCL, Stirling, York and Birmingham,
                 which started in 2012.",

Genetic Programming entries for Jose Antonio Vazquez Rodriguez Gabriela Ochoa