IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v43y2022i4d10.1007_s10878-021-00798-y.html
   My bibliography  Save this article

An ant colony optimization approach for the proportionate multiprocessor open shop

Author

Listed:
  • Zeynep Adak

    (Gebze Technical University)

  • Mahmure Övül Arıoğlu

    (Marmara University)

  • Serol Bulkan

    (Marmara University)

Abstract

Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time.

Suggested Citation

  • Zeynep Adak & Mahmure Övül Arıoğlu & Serol Bulkan, 2022. "An ant colony optimization approach for the proportionate multiprocessor open shop," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 785-817, May.
    • Handle: RePEc:spr:jcomop:v:43:y:2022:i:4:d:10.1007_s10878-021-00798-y
    DOI: 10.1007/s10878-021-00798-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00798-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-021-00798-y?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. Matta, Marie E. & Elmaghraby, Salah E., 2010. "Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop," European Journal of Operational Research, Elsevier, vol. 201(3), pages 720-728, March.
    2. 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.
    3. Jiawei Zhang & Ling Wang & Lining Xing, 2019. "Large-scale medical examination scheduling technology based on intelligent optimization," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 385-404, January.
    4. 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.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Jiawei Zhang & Ling Wang & Lining Xing, 2019. "Large-scale medical examination scheduling technology based on intelligent optimization," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 385-404, January.
    4. 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.
    5. Xu Tan & Lining Xing & Zhaoquan Cai & Gaige Wang, 2020. "Analysis of production cycle-time distribution with a big-data approach," Journal of Intelligent Manufacturing, Springer, vol. 31(8), pages 1889-1897, December.
    6. Deepak Gupta & Sonia Goel & Neeraj Mangla, 2022. "Optimization of production scheduling in two stage Flow Shop Scheduling problem with m equipotential machines at first stage," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 13(3), pages 1162-1169, June.
    7. He, Xinxin & Wang, Zhijian & Li, Yanfeng & Khazhina, Svetlana & Du, Wenhua & Wang, Junyuan & Wang, Wenzhao, 2022. "Joint decision-making of parallel machine scheduling restricted in job-machine release time and preventive maintenance with remaining useful life constraints," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    8. 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.
    9. 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.

    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:spr:jcomop:v:43:y:2022:i:4:d:10.1007_s10878-021-00798-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.