A Computational Study of Representations in Genetic Programming to Evolve Dispatching Rules for the Job Shop Scheduling Problem

Designing effective dispatching rules is an important factor for many manufacturing systems. However, this time-consuming process has been performed manually for a very long time. Recently, some machine learning approaches have been proposed to support this task. In this paper, we investigate the us...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2013-10, Vol.17 (5), p.621-639
Main Authors: Su Nguyen, Mengjie Zhang, Johnston, Mark, Kay Chen Tan
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Dispatching
Dispatching rule
Exact sciences and technology
Genetic algorithms
Genetic programming
Grammar
hyper-heuristic
Job shop scheduling
job shop scheduling (JSP)
Learning and adaptive systems
Operational research and scientific management
Operational research. Management science
Processor scheduling
Schedules
Scheduling, sequencing
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Designing effective dispatching rules is an important factor for many manufacturing systems. However, this time-consuming process has been performed manually for a very long time. Recently, some machine learning approaches have been proposed to support this task. In this paper, we investigate the use of genetic programming for automatically discovering new dispatching rules for the single objective job shop scheduling problem (JSP). Different representations of the dispatching rules in the literature are newly proposed in this paper and are compared and analysed. Experimental results show that the representation that integrates system and machine attributes can improve the quality of the evolved rules. Analysis of the evolved rules also provides useful knowledge about how these rules can effectively solve JSP.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2012.2227326