IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v52y2005i7p631-644.html
   My bibliography  Save this article

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

Author

Listed:
  • Selcuk Colak
  • Anurag Agarwal

Abstract

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.

Suggested Citation

  • Selcuk Colak & Anurag Agarwal, 2005. "Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(7), pages 631-644, October.
    • Handle: RePEc:wly:navres:v:52:y:2005:i:7:p:631-644
    DOI: 10.1002/nav.20102
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20102
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20102?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
    ---><---

    References listed on IDEAS

    as
    1. Agarwal, Anurag & Pirkul, Hasan & Jacob, Varghese S., 2003. "Augmented neural networks for task scheduling," European Journal of Operational Research, Elsevier, vol. 151(3), pages 481-502, December.
    2. Gueret, Christelle & Prins, Christian, 1998. "Classical and new heuristics for the open-shop problem: A computational evaluation," European Journal of Operational Research, Elsevier, vol. 107(2), pages 306-314, June.
    3. Liaw, Ching-Fang, 2000. "A hybrid genetic algorithm for the open shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 124(1), pages 28-42, July.
    4. Liaw, Ching-Fang, 1998. "An iterative improvement approach for the nonpreemptive open shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 111(3), pages 509-517, December.
    5. Sabuncuoglu, Ihsan & Gurgun, Burckaan, 1996. "A neural network model for scheduling problems," European Journal of Operational Research, Elsevier, vol. 93(2), pages 288-299, September.
    6. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    7. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    8. Christian Prins, 2000. "Competitive genetic algorithms for the open-shop scheduling problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 52(3), pages 389-411, December.
    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. Anurag Agarwal, 2009. "Theoretical insights into the augmented-neural-network approach for combinatorial optimization," Annals of Operations Research, Springer, vol. 168(1), pages 101-117, April.
    2. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    3. Anurag Agarwal & Selcuk Colak & Jason Deane, 2010. "NeuroGenetic approach for combinatorial optimization: an exploratory analysis," Annals of Operations Research, Springer, vol. 174(1), pages 185-199, February.

    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. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    2. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    3. Mejía, Gonzalo & Yuraszeck, Francisco, 2020. "A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times," European Journal of Operational Research, Elsevier, vol. 285(2), pages 484-496.
    4. Guillermo Campos Ciro & Frédéric Dugardin & Farouk Yalaoui & Russell Kelly, 2016. "Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4854-4881, August.
    5. Liaw, Ching-Fang, 2000. "A hybrid genetic algorithm for the open shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 124(1), pages 28-42, July.
    6. Arnaud Malapert & Hadrien Cambazard & Christelle Guéret & Narendra Jussien & André Langevin & Louis-Martin Rousseau, 2012. "An Optimal Constraint Programming Approach to the Open-Shop Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 228-244, May.
    7. Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.
    8. Ansis Ozolins, 2021. "Dynamic programming approach for solving the open shop problem," 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. 29(1), pages 291-306, 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. Pempera, Jaroslaw & Smutnicki, Czeslaw, 2018. "Open shop cyclic scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 773-781.
    11. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 0. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    12. Lizhong Zhao & Chen-Fu Chien & Mitsuo Gen, 2018. "A bi-objective genetic algorithm for intelligent rehabilitation scheduling considering therapy precedence constraints," Journal of Intelligent Manufacturing, Springer, vol. 29(5), pages 973-988, June.
    13. 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.
    14. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 2020. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 547-569, August.
    15. Berghman, Lotte & Kergosien, Yannick & Billaut, Jean-Charles, 2023. "A review on integrated scheduling and outbound vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 1-23.
    16. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    17. Agarwal, Anurag & Colak, Selcuk & Jacob, Varghese S. & Pirkul, Hasan, 2006. "Heuristics and augmented neural networks for task scheduling with non-identical machines," European Journal of Operational Research, Elsevier, vol. 175(1), pages 296-317, November.
    18. Tamer Abdelmaguid & Mohamed Shalaby & Mohamed Awwad, 2014. "A tabu search approach for proportionate multiprocessor open shop scheduling," Computational Optimization and Applications, Springer, vol. 58(1), pages 187-203, May.
    19. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    20. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:52:y:2005:i:7:p:631-644. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.