Automatic Design of Dispatching Rules for Job Shop Scheduling with Genetic Programming

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

  author =       "Su Nguyen",
  title =        "Automatic Design of Dispatching Rules for Job Shop
                 Scheduling with Genetic Programming",
  school =       "School of Engineering and Computer Science, Victoria
                 University of Wellington",
  year =         "2013",
  address =      "New Zealand",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  URL =          "",
  size =         "294 pages",
  abstract =     "Scheduling is an important planning activity in
                 manufacturing systems to help optimise the usage of
                 scarce resources and improve the customer satisfaction.
                 In the job shop manufacturing environment, scheduling
                 problems are challenging due to the complexity of
                 production flows and practical requirements such as
                 dynamic changes, uncertainty, multiple objectives, and
                 multiple scheduling decisions. Also, job shop
                 scheduling (JSS) is very common in small manufacturing
                 businesses and JSS is considered one of the most
                 popular research topics in this domain due to its
                 potential to dramatically decrease the costs and
                 increase the throughput. Practitioners and researchers
                 have applied different computational techniques, from
                 different fields such as operations research and
                 computer science, to deal with JSS problems. Although
                 optimisation methods usually show their dominance in
                 the literature, applying optimisation techniques in
                 practical situations is not straightforward because of
                 the practical constraints and conditions in the shop.
                 Dispatching rules are a very useful approach to dealing
                 with these environments because they are easy to
                 implement(by computers and shop floor operators) and
                 can cope with dynamic changes. However, designing an
                 effective dispatching rule is not a trivial task and
                 requires extensive knowledge about the scheduling
                 problem. The overall goal of this thesis is to develop
                 a genetic programming based hyper-heuristic (GPHH)
                 approach for automatic heuristic design of reusable and
                 competitive dispatching rules in job shop scheduling
                 environments. This thesis focuses on incorporating
                 special features of JSS in the representations and
                 evolutionary search mechanisms of genetic
                 programming(GP) to help enhance the quality of
                 dispatching rules obtained. This thesis shows that
                 representations and evaluation schemes are the
                 important factors that significantly influence the
                 performance of GP for evolving dispatching rules. The
                 thesis demonstrates that evolved rules which are
                 trained to adapt their decisions based on the changes
                 in shops are better than conventional rules. Moreover,
                 by applying a new evaluation scheme, the evolved rules
                 can effectively learn from the mistakes made in
                 previous completed schedules to construct better
                 scheduling decisions. The GP method using the new
                 proposed evaluation scheme shows better performance
                 than the GP method using the conventional scheme. This
                 thesis proposes a new multi-objective GPHH to evolve a
                 Pareto front of non-dominated dispatching rules.
                 Instead of evolving a single rule with assumed
                 preferences over different objectives, the advantage of
                 this GPHH method is to allow GP to evolve rules to
                 handle multiple conflicting objectives simultaneously.
                 The Pareto fronts obtained by the GPHH method can be
                 used as an effective tool to help decision makers
                 select appropriate rules based on their knowledge
                 regarding possible trade-offs. The thesis shows that
                 evolved rules can dominate well-known dispatching rules
                 when a single objective and multiple objectives are
                 considered. Also, the obtained Pareto fronts show that
                 many evolved rules can lead to favourable trade-offs,
                 which have not been explored in the literature. This
                 thesis tackles one of the most challenging issues in
                 job shop scheduling, the interactions between different
                 scheduling decisions. New GPHH methods have been
                 proposed to help evolve scheduling policies containing
                 multiple scheduling rules for multiple scheduling
                 decisions. The two decisions examined in this thesis
                 are sequencing and due date assignment. The
                 experimental results show that the evolved scheduling
                 rules are significantly better than scheduling policies
                 in the literature. A cooperative coevolution approach
                 has also been developed to reduce the complexity of
                 evolving sophisticated scheduling policies. A new
                 evolutionary search mechanisms and customised genetic
                 operations are proposed in this approach to improve the
                 diversity of the obtained Pareto fronts.",
  notes =        "Supervisors Mengjie Zhang and Mark Johnston
        Nguyen Phan Bach

Genetic Programming entries for Su Nguyen