IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v212y2011i1p22-32.html
   My bibliography  Save this article

Evolutionary search for difficult problem instances to support the design of job shop dispatching rules

Author

Listed:
  • Branke, Juergen
  • Pickardt, Christoph W.

Abstract

Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop. An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:212:y:2011:i:1:p:22-32
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(11)00098-1
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Huyet, A.L., 2006. "Optimization and analysis aid via data-mining for simulated production systems," European Journal of Operational Research, Elsevier, vol. 173(3), pages 827-838, September.
    2. Robert H. Storer & S. David Wu & Renzo Vaccari, 1995. "Problem and Heuristic Space Search Strategies for Job Shop Scheduling," INFORMS Journal on Computing, INFORMS, vol. 7(4), pages 453-467, November.
    3. S. S. Panwalkar & Wafik Iskander, 1977. "A Survey of Scheduling Rules," Operations Research, INFORMS, vol. 25(1), pages 45-61, February.
    4. Chiang, Tsung-Che & Fu, Li-Chen, 2009. "Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 196(1), pages 78-92, July.
    5. 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.
    6. Ramasesh, R, 1990. "Dynamic job shop scheduling: A survey of simulation research," Omega, Elsevier, vol. 18(1), pages 43-57.
    7. Robert H. Storer & S. David Wu & Renzo Vaccari, 1992. "New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling," Management Science, INFORMS, vol. 38(10), pages 1495-1509, October.
    8. 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.
    9. 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. Matías Núñez-Muñoz & Rodrigo Linfati & John Willmer Escobar, 2023. "Two-stage optimization scheme of routing scheduling from a single distribution center to multiple customers," Operational Research, Springer, vol. 23(2), pages 1-29, June.
    2. Cruz-Ramı´rez, Manuel & Hervás-Martı´nez, César & Fernández, Juan Carlos & Briceño, Javier & de la Mata, Manuel, 2012. "Multi-objective evolutionary algorithm for donor–recipient decision system in liver transplants," European Journal of Operational Research, Elsevier, vol. 222(2), pages 317-327.
    3. 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.
    4. Kasper, T.A. Arno & Land, Martin J. & Teunter, Ruud H., 2023. "Towards System State Dispatching in High‐Variety Manufacturing," Omega, Elsevier, vol. 114(C).
    5. 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.

    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. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    2. Kasper, T.A. Arno & Land, Martin J. & Teunter, Ruud H., 2023. "Towards System State Dispatching in High‐Variety Manufacturing," Omega, Elsevier, vol. 114(C).
    3. 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.
    4. 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.
    5. 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).
    6. 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.
    7. El-Bouri, Ahmed & Balakrishnan, Subramaniam & Popplewell, Neil, 2008. "Cooperative dispatching for minimizing mean flowtime in a dynamic flowshop," International Journal of Production Economics, Elsevier, vol. 113(2), pages 819-833, June.
    8. 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.
    9. Anurag Agarwal & Varghese S. Jacob & Hasan Pirkul, 2006. "An Improved Augmented Neural-Network Approach for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 119-128, February.
    10. 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.
    11. Guinet, Alain & Legrand, Marie, 1998. "Reduction of job-shop problems to flow-shop problems with precedence constraints," European Journal of Operational Research, Elsevier, vol. 109(1), pages 96-110, August.
    12. Land, Martin & Gaalman, Gerard, 1996. "Workload control concepts in job shops A critical assessment," International Journal of Production Economics, Elsevier, vol. 46(1), pages 535-548, December.
    13. Drexl, Andreas & Salewski, Frank, 1996. "Distribution Requirements and Compactness Constraints in School Timetabling. Part II: Methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 384, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. 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.
    15. Vinod, V. & Sridharan, R., 2011. "Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system," International Journal of Production Economics, Elsevier, vol. 129(1), pages 127-146, January.
    16. Zhou, Hong & Cheung, Waiman & Leung, Lawrence C., 2009. "Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm," European Journal of Operational Research, Elsevier, vol. 194(3), pages 637-649, May.
    17. Reményi, Christoph & Staudacher, Stephan, 2014. "Systematic simulation based approach for the identification and implementation of a scheduling rule in the aircraft engine maintenance," International Journal of Production Economics, Elsevier, vol. 147(PA), pages 94-107.
    18. Beemsterboer, Bart & Land, Martin & Teunter, Ruud & Bokhorst, Jos, 2017. "Integrating make-to-order and make-to-stock in job shop control," International Journal of Production Economics, Elsevier, vol. 185(C), pages 1-10.
    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. Franz Rothlauf, 2009. "An Encoding in Metaheuristics for the Minimum Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 575-584, November.

    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:ejores:v:212:y:2011:i:1:p:22-32. 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/eor .

    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.