research-article

Towards improved dispatching rules for complex shop floor scenarios: a genetic programming approach

Authors:

Torsten Hildebrandt,

Bernd Scholz-ReiterAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 257 - 264

https://doi.org/10.1145/1830483.1830530

Published: 07 July 2010 Publication History

Abstract

Developing dispatching rules for manufacturing systems is a process, which is time- and cost-consuming. Since there is no good general rule for different scenarios and objectives automatic rule search mechanism are investigated. In this paper an approach using Genetic Programming (GP) is presented. The priority rules generated by GP are evaluated on dynamic job shop scenarios from literature and compared with manually developed rules yielding very promising results also interesting for Simulation Optimization in general.

References

[1]

L. Atlan, J. Bonnet, and M. Naillon. Learning distributed reactive strategies by genetic programming for the general job shop problem. May 1994.

[2]

J. H. Blackstone, D. T. Phillips, and G. L. Hogg. A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1):27--45, 1982.

[3]

J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, and J. Weglarz. Scheduling Computer and Manufacturing Processes. Springer, Berlin et al., 2nd edition, 2001.

Digital Library

[4]

J. Boesel, B. L. Nelson, and S.-H. Kim. Using ranking and selection to "clean up" after simulation optimization. Operations Research, 51(5):814--825, 2003.

Digital Library

[5]

E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. Woodward. A classification of hyper-heuristics approaches. In M. Gendreau and J.-Y. Potvin, editors, Handbook of Meta-heuristics. Springer, 2nd edition. Forthcoming.

[6]

C. H. Chen, D. He, M. Fu, and L. H. Lee. Efficient simulation budget allocation for selecting an optimal subset. Informs Journal on Computing, 20(4):579--595, 2008.

[7]

C.-C. Chern and Y.-L. Liu. Family-based scheduling rules of a sequence-dependent wafer fabrication system. IEEE Transactions on Semiconductor Manufacturing, 16(1):15--25, 2003.

[8]

T. C. Chiang, Y. S. Shen, and L. C. Fu. A new paradigm for rule-based scheduling in the wafer probe centre. International Journal of Production Research, 46(15):4111--4133, 2008.

[9]

R. W. Conway. Priority dispatching and job lateness in a job shop. Journal of Industrial Engineering, 16:228--237, 1965.

[10]

C. Dimopoulos and A. M. S. Zalzala. Investigating the use of genetic programming for a classic one-machine scheduling problem. Advances in Engineering Software, 32(6):489--498, 2001.

[11]

ECJ. A Java-based Evolutionary Computation Research System, project homepage, 2009. http://cs.gmu.edu/~eclab/projects/ecj/, last accessed 15th January 2010.

[12]

H. Fisher, G. L. Thompson. Probabilistic learning combinations of local job-shop scheduling rules. In J. F. Muth and G. L. Thompson, editors, Industrial Scheduling; pages 225 -- 251, Prentiss-Hall, 1963.

[13]

C. Geiger, R. Uzsoy, and H. Aytug. Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. Journal of Scheduling, 9(1):7--34, 2006.

Digital Library

[14]

C. D. Geiger and R. Uzsoy. Learning effective dispatching rules for batch processor scheduling. International Journal of Production Research, 46(6):1431--1454, 2008.

[15]

E. Hart, P. Ross, and D. Corne. Evolutionary scheduling: A review. Genetic Programming and Evolvable Machines, 6(2):191--220, 2005.

Digital Library

[16]

R. Haupt. A survey of priority rule-based scheduling. OR Spektrum, 11(1):3--16, 1989.

[17]

O. Holthaus and C. Rajendran. Efficient jobshop dispatching rules: further developments. Production Planning & Control, 11(2):171--178, 2000.

[18]

B. J. Huffman. An object-oriented version of SIMLIB (a simple simulation package). INFORMS Transactions on Education, 2(1):1--15, 2001.

Digital Library

[19]

D. Jakobović and L. Budin. Dynamic scheduling with genetic programming. In P. Collet, M. Tomassini, M. Ebner, S. Gustafson, and A. Ekárt, editors, Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, pages 73--84, Budapest, Hungary, 10 - 12 Apr. 2006. Springer.

Digital Library

[20]

D. JakoboviĈ, L. Jelenković, and L. Budin. Genetic programming heuristics for multiple machine scheduling. In M. Ebner, M. O'Neill, A. Ek&3225;rt, L. Vanneschi, and A. I. Esparcia-Alcázar, editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 321--330, Valencia, Spain, 11 - 13 Apr. 2007. Springer.

Digital Library

[21]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[22]

A. M. Law. Simulation modeling and analysis. McGraw-Hill, Boston, USA et al., 4. edition, 2007.

Digital Library

[23]

S. S. Panwalkar and W. Iskander. A survey of scheduling rules. Operations Research, 25(1):45--61, 1977.

Digital Library

[24]

M. Pinedo. Scheduling - Theory, Algorithms and Systems. Prentice Hall, Upper Saddle River, New Jersey, USA, 2nd edition, 2002.

Digital Library

[25]

C. Rajendran and O. Holthaus. A comparative study of dispatching rules in dynamic owshops and jobshops. European Journal of Operational Research, 116(1):156--170, July 1999.

[26]

C. Schmidt, J. Branke, and S. E. Chick. Integrating techniques from statistical ranking into evolutionary algorithms. Springer Berlin / Heidelberg, 3907:752--763, 2006.

Digital Library

[27]

J. C. Tay and N. B. Ho. Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54(3):453--473, 2008.

Digital Library

Cited By

Zhang FMei YNguyen SZhang M(2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3255246
Xu MMei YZhang FZhang M(2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3244607
Xu MMei YZhang FZhang M(2024)Genetic Programming and Reinforcement Learning on Learning Heuristics for Dynamic Scheduling: A Preliminary ComparisonIEEE Computational Intelligence Magazine10.1109/MCI.2024.336397019:2(18-33)Online publication date: 5-Apr-2024
https://dl.acm.org/doi/10.1109/MCI.2024.3363970
Show More Cited By

Index Terms

Towards improved dispatching rules for complex shop floor scenarios: a genetic programming approach
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling

Recommendations

Feature Selection in Evolving Job Shop Dispatching Rules with Genetic Programming
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Genetic Programming (GP) has been successfully used to automatically design dispatching rules in job shop scheduling. The goal of GP is to evolve a priority function that will be used to order the waiting jobs at each decision point, and decide the next ...
Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling
Abstract
Dispatching rules represent a simple heuristic for finding good solutions for job shop scheduling problems. Due to their fast applicability and easy handling, they are often used in manufacturing companies to create appropriate production ...
Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation
Abstract
In production planning and scheduling, data mining methods can be applied to transform the scheduling data into useful knowledge that can be used to improve planning/scheduling by enabling real-time decision-making. In this paper, a novel approach ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

116
Total Citations
View Citations
384
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)6

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang FMei YNguyen SZhang M(2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3255246
Xu MMei YZhang FZhang M(2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3244607
Xu MMei YZhang FZhang M(2024)Genetic Programming and Reinforcement Learning on Learning Heuristics for Dynamic Scheduling: A Preliminary ComparisonIEEE Computational Intelligence Magazine10.1109/MCI.2024.336397019:2(18-33)Online publication date: 5-Apr-2024
https://dl.acm.org/doi/10.1109/MCI.2024.3363970
Cai SYe Q(2024)Variable-length Evolutionary Optimization for Multi-objectiveWorker Transfer Scheduling in Complex Product Assembly Line2024 16th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)10.1109/IHMSC62065.2024.00019(51-55)Online publication date: 24-Aug-2024
https://doi.org/10.1109/IHMSC62065.2024.00019
Pang JMei YZhang M(2024)Multi-Objective Genetic-Programming Hyper-Heuristic for Evolving Interpretable Flexible Job Shop Scheduling Rules2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612158(01-08)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612158
Guo HLiu JWang YZhuang C(2024)An improved genetic programming hyper-heuristic for the dynamic flexible job shop scheduling problem with reconfigurable manufacturing cellsJournal of Manufacturing Systems10.1016/j.jmsy.2024.03.00974(252-263)Online publication date: Jun-2024
https://doi.org/10.1016/j.jmsy.2024.03.009
Yang YChen GMa HHartmann SZhang M(2024)Enhancing Generalization in Genetic Programming Hyper-heuristics through Mini-batch Sampling Strategies for Dynamic Workflow SchedulingInformation Sciences10.1016/j.ins.2024.120975(120975)Online publication date: Jun-2024
https://doi.org/10.1016/j.ins.2024.120975
Liu RLv HYang PWang R(2024)A multi-task genetic programming approach for online multi-objective container placement in heterogeneous clusterComplex & Intelligent Systems10.1007/s40747-024-01605-x11:1Online publication date: 13-Nov-2024
https://doi.org/10.1007/s40747-024-01605-x
Huang ZMei YZhang FZhang MBanzhaf W(2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
https://doi.org/10.1007/s10710-023-09478-8
Masood A(2023)Many-Objective Genetic Programming for Job-Shop SchedulingACM SIGEVOlution10.1145/3584367.358437015:4(1-4)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3584367.3584370
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents