Victoria University

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

ResearchArchive/Manakin Repository

Show simple item record

dc.contributor.advisor Zhang, Mengjie
dc.contributor.advisor Johnston, Mark Nguyen, Su 2013-10-22T23:43:34Z 2013-10-22T23:43:34Z 2013 2013
dc.description.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 newproposed 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 themost 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. en_NZ
dc.language.iso en_NZ
dc.publisher Victoria University of Wellington en_NZ
dc.subject Genetic programming en_NZ
dc.subject Scheduling en_NZ
dc.subject Heuristic en_NZ
dc.title Automatic Design of Dispatching Rules for Job Shop Scheduling with Genetic Programming en_NZ
dc.type Text en_NZ
vuwschema.contributor.unit School of Engineering and Computer Science en_NZ
vuwschema.type.vuw Awarded Doctoral Thesis en_NZ Computer Science en_NZ Victoria University of Wellington en_NZ Doctoral en_NZ Doctor of Philosophy en_NZ
vuwschema.subject.anzsrcfor 080605 Decision Support and Group Support Systems en_NZ
vuwschema.subject.anzsrcseo 861601 Computer and Electronic Office Equipment en_NZ
vuwschema.subject.anzsrcseo 890205 Information Processing Services (incl. Data Entry and Capture) en_NZ

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ResearchArchive

Advanced Search


My Account