IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v229y2015i1p743-75810.1007-s10479-015-1855-z.html
   My bibliography  Save this article

OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises

Author

Listed:
  • Shahaboddin Shamshirband
  • Mohammad Shojafar
  • A. Hosseinabadi
  • Maryam Kardgar
  • M. Nasir
  • Rodina Ahmad

Abstract

The problem of open-shop scheduling includes a set of activities which must be performed on a limited set of machines. The goal of scheduling in open-shop is the presentation of a scheduled program for performance of the whole operation, so that the ending performance time of all job operations will be minimised. The open-shop scheduling problem can be solved in polynomial time when all nonzero processing times are equal, becoming equivalent to edge coloring that has the jobs and workstations as its vertices and that has an edge for every job-workstation pair with a nonzero processing time. For three or more workstations, or three or more jobs, with varying processing times, open-shop scheduling is NP-hard. Different algorithms have been presented for open-shop scheduling so far. However, most of these algorithms have not considered the machine maintenance problem. Whilst in production level, each machine needs maintenance, and this directly influences the assurance reliability of the system. In this paper, a new genetic-based algorithm to solve the open-shop scheduling problem, namely OSGA, is developed. OSGA considers machine maintenance. To confirm the performance of OSGA, it is compared with DGA, SAGA and TSGA algorithms. It is observed that OSGA performs quite well in terms of solution quality and efficiency in small and medium enterprises (SMEs). The results support the efficiency of the proposed method for solving the open-shop scheduling problem, particularly considering machine maintenance especially in SMEs’. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:229:y:2015:i:1:p:743-758:10.1007/s10479-015-1855-z
    DOI: 10.1007/s10479-015-1855-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-015-1855-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-015-1855-z?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. Munier-Kordon, Alix & Rebaine, Djamal, 2010. "The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 203(1), pages 42-49, May.
    2. Ali Hosseinabadi & Hajar Siar & Shahaboddin Shamshirband & Mohammad Shojafar & Mohd Nasir, 2015. "Using the gravitational emulation local search algorithm to solve the multi-objective flexible dynamic job shop scheduling problem in Small and Medium Enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 451-474, June.
    3. David Alcaide & Joaquín Sicilia & Daniele Vigo, 1997. "A tabu search algorithm for the Open Shop problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 5(2), pages 283-296, December.
    4. 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.
    5. 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.
    6. Lin, Hung-Tso & Lee, Hong-Tau & Pan, Wen-Jung, 2008. "Heuristics for scheduling in a no-wait open shop with movable dedicated machines," International Journal of Production Economics, Elsevier, vol. 111(2), pages 368-377, February.
    7. 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.
    8. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    9. 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.
    10. Yu, Wei & Liu, Zhaohui & Wang, Leiyang & Fan, Tijun, 2011. "Routing open shop and flow shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 213(1), pages 24-36, August.
    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. Xin Yang & Zhenxiang Zeng & Ruidong Wang & Xueshan Sun, 2016. "Bi-Objective Flexible Job-Shop Scheduling Problem Considering Energy Consumption under Stochastic Processing Times," PLOS ONE, Public Library of Science, vol. 11(12), pages 1-13, December.

    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Pempera, Jaroslaw & Smutnicki, Czeslaw, 2018. "Open shop cyclic scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 773-781.
    11. 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.
    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. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Kumar, Akhilesh & Prakash & Tiwari, M.K. & Shankar, Ravi & Baveja, Alok, 2006. "Solving machine-loading problem of a flexible manufacturing system with constraint-based genetic algorithm," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1043-1069, December.
    18. Shahvari, Omid & Logendran, Rasaratnam, 2016. "Hybrid flow shop batching and scheduling with a bi-criteria objective," International Journal of Production Economics, Elsevier, vol. 179(C), pages 239-258.
    19. Lin, Hung-Tso & Lee, Hong-Tau & Pan, Wen-Jung, 2008. "Heuristics for scheduling in a no-wait open shop with movable dedicated machines," International Journal of Production Economics, Elsevier, vol. 111(2), pages 368-377, February.
    20. Fleming, Christopher L. & Griffis, Stanley E. & Bell, John E., 2013. "The effects of triangle inequality on the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 1-7.

    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:annopr:v:229:y:2015:i:1:p:743-758:10.1007/s10479-015-1855-z. 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.