IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v145y2013i1p67-77.html
   My bibliography  Save this article

Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems

Author

Listed:
  • Pickardt, Christoph W.
  • Hildebrandt, Torsten
  • Branke, Jürgen
  • Heger, Jens
  • Scholz-Reiter, Bernd

Abstract

We propose a two-stage hyper-heuristic for the generation of a set of work centre-specific dispatching rules. The approach combines a genetic programming (GP) algorithm that evolves a composite rule from basic job attributes with an evolutionary algorithm (EA) that searches for a good assignment of rules to work centres. The hyper-heuristic is tested against its two components and rules from the literature on a complex dynamic job shop problem from semiconductor manufacturing. Results show that all three hyper-heuristics are able to generate (sets of) rules that achieve a significantly lower mean weighted tardiness than any of the benckmark rules. Moreover, the two-stage approach proves to outperform the GP and EA hyper-heuristic as it optimises on two different heuristic search spaces that appear to tap different optimisation potentials. The resulting rule sets are also robust to most changes in the operating conditions.

Suggested Citation

  • Pickardt, Christoph W. & Hildebrandt, Torsten & Branke, Jürgen & Heger, Jens & Scholz-Reiter, Bernd, 2013. "Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems," International Journal of Production Economics, Elsevier, vol. 145(1), pages 67-77.
    • Handle: RePEc:eee:proeco:v:145:y:2013:i:1:p:67-77
    DOI: 10.1016/j.ijpe.2012.10.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527312004574
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2012.10.016?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Edmund K. Burke & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & John R. Woodward, 2010. "A Classification of Hyper-heuristic Approaches," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 449-468, Springer.
    2. Ari P. J. Vepsalainen & Thomas E. Morton, 1987. "Priority Rules for Job Shops with Weighted Tardiness Costs," Management Science, INFORMS, vol. 33(8), pages 1035-1047, August.
    3. Aytug, Haldun & Lawley, Mark A. & McKay, Kenneth & Mohan, Shantha & Uzsoy, Reha, 2005. "Executing production schedules in the face of uncertainties: A review and some future directions," European Journal of Operational Research, Elsevier, vol. 161(1), pages 86-110, February.
    4. Michele E. Pfund & Scott J. Mason & John W. Fowler, 2006. "Semiconductor Manufacturing Scheduling and Dispatching," International Series in Operations Research & Management Science, in: Jeffrey W. Herrmann (ed.), Handbook of Production Scheduling, pages 213-241, Springer.
    5. Brian J. Huffman, 2001. "An Object-Oriented Version of SIMLIB (A Simple Simulation Package)," INFORMS Transactions on Education, INFORMS, vol. 2(1), pages 1-15, September.
    6. Yang, Taho & Kuo, Yiyo & Cho, Chiwoon, 2007. "A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1859-1873, February.
    7. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    8. Olafsson, Sigurdur & Li, Xiaonan, 2010. "Learning effective new single machine dispatching rules from optimal scheduling data," International Journal of Production Economics, Elsevier, vol. 128(1), pages 118-126, November.
    9. Wu, Muh-Cherng & Jiang, Jr-Hsiung & Chang, Wen-Jen, 2008. "Scheduling a hybrid MTO/MTS semiconductor fab with machine-dedication features," International Journal of Production Economics, Elsevier, vol. 112(1), pages 416-426, March.
    10. J A Vázquez-Rodríguez & G Ochoa, 2011. "On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 381-396, February.
    11. Holthaus, Oliver & Rajendran, Chandrasekharan, 1997. "Efficient dispatching rules for scheduling in a job shop," International Journal of Production Economics, Elsevier, vol. 48(1), pages 87-105, January.
    12. James C. Hershauer & Ronald J. Ebert, 1975. "Search and Simulation Selection of a Job-Shop Sequencing Rule," Management Science, INFORMS, vol. 21(7), pages 833-843, March.
    13. Rajendran, Chandrasekharan & Holthaus, Oliver, 1999. "A comparative study of dispatching rules in dynamic flowshops and jobshops," European Journal of Operational Research, Elsevier, vol. 116(1), pages 156-170, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sungwook Yoon & Jihyun Kim & Sukjae Jeong, 2017. "RETRACTED: The Optimal Decision Combination in Semiconductor Manufacturing," Sustainability, MDPI, vol. 9(10), pages 1, October.
    2. Marko Ɖurasević & Domagoj Jakobović, 2019. "Creating dispatching rules by simple ensemble combination," Journal of Heuristics, Springer, vol. 25(6), pages 959-1013, December.
    3. Yannik Zeiträg & José Rui Figueira, 2023. "Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling," Journal of Scheduling, Springer, vol. 26(3), pages 289-314, June.
    4. Braune, Roland & Benda, Frank & Doerner, Karl F. & Hartl, Richard F., 2022. "A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems," International Journal of Production Economics, Elsevier, vol. 243(C).
    5. Shijin Wang & Ming Liu, 2016. "Two-machine flow shop scheduling integrated with preventive maintenance planning," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(3), pages 672-690, February.
    6. Jing, Hao & Sheng, Lijuan & Luo, Chaorui & Kwak, Choonjong, 2021. "Statistical analysis of family based dispatching rules and preemption," International Journal of Production Economics, Elsevier, vol. 240(C).
    7. Romero-Silva, Rodrigo & Shaaban, Sabry & Marsillac, Erika & Hurtado, Margarita, 2018. "Exploiting the characteristics of serial queues to reduce the mean and variance of flow time using combined priority rules," International Journal of Production Economics, Elsevier, vol. 196(C), pages 211-225.
    8. Lingxuan Liu & Leyuan Shi, 2019. "Simulation Optimization on Complex Job Shop Scheduling with Non-Identical Job Sizes," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(05), pages 1-26, October.
    9. Helga Ingimundardottir & Thomas Philip Runarsson, 2018. "Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem," Journal of Scheduling, Springer, vol. 21(4), pages 413-428, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Branke, Juergen & Pickardt, Christoph W., 2011. "Evolutionary search for difficult problem instances to support the design of job shop dispatching rules," European Journal of Operational Research, Elsevier, vol. 212(1), pages 22-32, July.
    2. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2022. "Effective and interpretable dispatching rules for dynamic job shops via guided empirical learning," Omega, Elsevier, vol. 111(C).
    3. Alvarez-Valdes, R. & Fuertes, A. & Tamarit, J. M. & Gimenez, G. & Ramos, R., 2005. "A heuristic to schedule flexible job-shop in a glass factory," European Journal of Operational Research, Elsevier, vol. 165(2), pages 525-534, September.
    4. Xiong, Hegen & Fan, Huali & Jiang, Guozhang & Li, Gongfa, 2017. "A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints," European Journal of Operational Research, Elsevier, vol. 257(1), pages 13-24.
    5. Jayamohan, M. S. & Rajendran, Chandrasekharan, 2004. "Development and analysis of cost-based dispatching rules for job shop scheduling," European Journal of Operational Research, Elsevier, vol. 157(2), pages 307-321, September.
    6. Jens Heger & Torsten Hildebrandt & Bernd Scholz-Reiter, 2015. "Dispatching rule selection with Gaussian processes," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(1), pages 235-249, March.
    7. Selcuk Goren & Ihsan Sabuncuoglu & Utku Koc, 2012. "Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(1), pages 26-38, February.
    8. Azaron, Amir & Katagiri, Hideki & Kato, Kosuke & Sakawa, Masatoshi, 2006. "Longest path analysis in networks of queues: Dynamic scheduling problems," European Journal of Operational Research, Elsevier, vol. 174(1), pages 132-149, October.
    9. Rajendran, Chandrasekharan & Ziegler, Hans, 2001. "A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs," European Journal of Operational Research, Elsevier, vol. 131(3), pages 622-634, June.
    10. A. S. Xanthopoulos & D. E. Koulouriotis, 2018. "Cluster analysis and neural network-based metamodeling of priority rules for dynamic sequencing," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 69-91, January.
    11. Petroni, Alberto & Rizzi, Antonio, 2002. "A fuzzy logic based methodology to rank shop floor dispatching rules," International Journal of Production Economics, Elsevier, vol. 76(1), pages 99-108, March.
    12. Black, Gary W. & McKay, Kenneth N. & Morton, Thomas E., 2006. "Aversion scheduling in the presence of risky jobs," European Journal of Operational Research, Elsevier, vol. 175(1), pages 338-361, November.
    13. Helga Ingimundardottir & Thomas Philip Runarsson, 2018. "Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem," Journal of Scheduling, Springer, vol. 21(4), pages 413-428, August.
    14. Yao, Shiqing & Jiang, Zhibin & Li, Na & Zhang, Huai & Geng, Na, 2011. "A multi-objective dynamic scheduling approach using multiple attribute decision making in semiconductor manufacturing," International Journal of Production Economics, Elsevier, vol. 130(1), pages 125-133, March.
    15. Yannik Zeiträg & José Rui Figueira, 2023. "Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling," Journal of Scheduling, Springer, vol. 26(3), pages 289-314, June.
    16. Kuo, Yiyo & Yang, Taho & Cho, Chiwoon & Tseng, Yao-Ching, 2008. "Using simulation and multi-criteria methods to provide robust solutions to dispatching problems in a flow shop with multiple processors," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 78(1), pages 40-56.
    17. Yunna Tian & Dongni Li & Pengyu Zhou & Rongtao Guo & Zhaohe Liu, 2018. "An ACO-based hyperheuristic with dynamic decision blocks for intercell scheduling," Journal of Intelligent Manufacturing, Springer, vol. 29(8), pages 1905-1921, December.
    18. Jianjun Liu & Martin J. Land & Jos A. C. Bokhorst & Qingxin Chen, 2023. "Improving coordination in assembly job shops: redesigning order release and dispatching," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 669-697, September.
    19. Lodree, Emmett & Jang, Wooseung & Klein, Cerry M., 2004. "A new rule for minimizing the number of tardy jobs in dynamic flow shops," European Journal of Operational Research, Elsevier, vol. 159(1), pages 258-263, November.
    20. Sweeney, Kevin D. & Sweeney, Donald C. & Campbell, James F., 2019. "The performance of priority dispatching rules in a complex job shop: A study on the Upper Mississippi River," International Journal of Production Economics, Elsevier, vol. 216(C), pages 154-172.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:proeco:v:145:y:2013:i:1:p:67-77. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.