IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v27y2019i1d10.1007_s11750-018-00494-x.html
   My bibliography  Save this article

MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints

Author

Listed:
  • Emine Akyol Ozer

    (Eskisehir Technical University)

  • Tugba Sarac

    (Osmangazi University)

Abstract

If parallel machines use shared resources during production, jobs on machines must wait until the required resources are available. If the shared resource is single, only one job can use it at a time, but if there are multiple copies of this resource, multiple jobs can be scheduled up to the number of copies at a time. For this reason, it is crucial to consider resource usage when scheduling this type of machine. In recent years, various studies have been carried out to address identical parallel machine scheduling problems. However, although shared resources in parallel machines are an important aspect of this problem, resources are rarely considered in these studies and, in fact, have not been studied for this particular aspect. In this study, an identical parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and multiple copies of shared resources (IPMS-SMS) is considered. Mixed-integer programming (MIP) models and a model-based genetic algorithm (matheuristic) are proposed, and the objective function of the problem seeks to minimize the total weighted completion time. Randomly generated instances are solved using the proposed models and the matheuristic. Optimal schedules are obtained for almost all small problems using a mixed-integer programming model. However, better solutions are obtained for medium and large instances using the proposed matheuristic.

Suggested Citation

  • Emine Akyol Ozer & Tugba Sarac, 2019. "MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 94-124, April.
    • Handle: RePEc:spr:topjnl:v:27:y:2019:i:1:d:10.1007_s11750-018-00494-x
    DOI: 10.1007/s11750-018-00494-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-018-00494-x
    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/s11750-018-00494-x?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. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2013. "Pricing, relaxing and fixing under lot sizing and scheduling," European Journal of Operational Research, Elsevier, vol. 230(2), pages 399-411.
    2. Alagoz, Oguzhan & Azizoglu, Meral, 2003. "Rescheduling of identical parallel machines under machine eligibility constraints," European Journal of Operational Research, Elsevier, vol. 149(3), pages 523-532, September.
    3. Fanjul-Peyro, Luis & Perea, Federico & Ruiz, Rubén, 2017. "Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources," European Journal of Operational Research, Elsevier, vol. 260(2), pages 482-493.
    4. Nait Tahar, Djamel & Yalaoui, Farouk & Chu, Chengbin & Amodeo, Lionel, 2006. "A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 63-73, February.
    5. Billaut, Jean-Charles & Della Croce, Federico & Grosso, Andrea, 2015. "A single machine scheduling problem with two-dimensional vector packing constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 75-81.
    6. Kangbok Lee & Joseph Leung & Michael Pinedo, 2013. "Makespan minimization in online scheduling with machine eligibility," Annals of Operations Research, Springer, vol. 204(1), pages 189-222, April.
    7. Gedik, Ridvan & Rainwater, Chase & Nachtmann, Heather & Pohl, Ed A., 2016. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals," European Journal of Operational Research, Elsevier, vol. 251(2), pages 640-650.
    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. Mohammad Mahdi Ahmadian & Amir Salehipour, 2021. "The just-in-time job-shop scheduling problem with distinct due-dates for operations," Journal of Heuristics, Springer, vol. 27(1), pages 175-204, April.
    2. Kennedy A. G. Araújo & Tibérius O. Bonates & Bruno A. Prata & Anselmo R. Pitombeira-Neto, 2021. "Heterogeneous prestressed precast beams multiperiod production planning problem: modeling and solution methods," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 660-693, October.
    3. Geurtsen, M. & Didden, Jeroen B.H.C. & Adan, J. & Atan, Z. & Adan, I., 2023. "Production, maintenance and resource scheduling: A review," European Journal of Operational Research, Elsevier, vol. 305(2), pages 501-529.
    4. Bentao Su & Naiming Xie & Yingjie Yang, 2021. "Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 32(4), pages 957-969, April.

    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. Framinan, Jose M. & Perez-Gonzalez, Paz, 2018. "Order scheduling with tardiness objective: Improved approximate solutions," European Journal of Operational Research, Elsevier, vol. 266(3), pages 840-850.
    2. Marco Ghirardi & Fabio Salassa, 2022. "A simple and effective algorithm for the maximum happy vertices problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 181-193, April.
    3. Bentao Su & Naiming Xie, 2020. "Single workgroup scheduling problem with variable processing personnel," 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. 28(2), pages 671-684, June.
    4. Nascimento, Paulo Jorge & Silva, Cristóvão & Antunes, Carlos Henggeler & Moniz, Samuel, 2024. "Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 92-110.
    5. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.
    6. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    7. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    8. Jun-Ho Lee & Hyun-Jung Kim, 2021. "A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 992-1026, December.
    9. Boonmee, Atiwat & Sethanan, Kanchana, 2016. "A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry," European Journal of Operational Research, Elsevier, vol. 250(2), pages 652-665.
    10. Norelhouda Sekkal & Fayçal Belkaid, 0. "A multi-objective simulated annealing to solve an identical parallel machine scheduling problem with deterioration effect and resources consumption constraints," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-37.
    11. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.
    12. Yepes-Borrero, Juan C. & Perea, Federico & Ruiz, Rubén & Villa, Fulgencia, 2021. "Bi-objective parallel machine scheduling with additional resources during setups," European Journal of Operational Research, Elsevier, vol. 292(2), pages 443-455.
    13. Lorenzo Ros-McDonnell & M. de-la-Fuente-Aragon & Marija Bogataj, 2012. "An approximate algorithm for optimal logistics of heavy and variable size items," 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. 20(1), pages 1-17, March.
    14. Chuleeporn Kusoncum & Kanchana Sethanan & Richard F. Hartl & Thitipong Jamrus, 2022. "Modified differential evolution and heuristic algorithms for dump tippler machine allocation in a typical sugar mill in Thailand," Operational Research, Springer, vol. 22(5), pages 5863-5895, November.
    15. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    16. Perea, Federico & Yepes-Borrero, Juan C. & Menezes, Mozart B.C., 2023. "Acceptance Ordering Scheduling Problem: The impact of an order-portfolio on a make-to-order firm’s profitability," International Journal of Production Economics, Elsevier, vol. 264(C).
    17. Boccia, Maurizio & Masone, Adriano & Sterle, Claudio & Murino, Teresa, 2023. "The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach," European Journal of Operational Research, Elsevier, vol. 307(2), pages 590-603.
    18. Bentao Su & Naiming Xie & Yingjie Yang, 2021. "Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 32(4), pages 957-969, April.
    19. Carvalho, Desiree M. & Nascimento, Mariá C.V., 2022. "Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup," European Journal of Operational Research, Elsevier, vol. 296(1), pages 158-173.
    20. Mina Roohnavazfar & Seyed Hamid Reza Pasandideh, 2022. "Decomposition algorithm for the multi-trip single vehicle routing problem with AND-type precedence constraints," Operational Research, Springer, vol. 22(4), pages 4253-4285, September.

    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:topjnl:v:27:y:2019:i:1:d:10.1007_s11750-018-00494-x. 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.