IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v211y2013i1p333-35610.1007-s10479-013-1446-9.html
   My bibliography  Save this article

Scheduling the two-machine open shop problem under resource constraints for setting the jobs

Author

Listed:
  • Ammar Oulamara
  • Djamal Rebaine
  • Mehdi Serairi

Abstract

This paper addresses the problem of open shop scheduling on two machines with resources constraints. In the context of our study, in order to be executed, a job requires first, for its preparation for a given period of time, a number of resources which cannot exceed a given resource capacity. Then, it goes onto its execution while the resources allocated to it become available again. We seek a schedule that minimizes the makespan. We first prove the $\mathcal{N}\mathcal{P}$ -hardness of several versions of this problem. Then, we present a well solvable case, lower bounds, and heuristic algorithms along with an experimental study. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Ammar Oulamara & Djamal Rebaine & Mehdi Serairi, 2013. "Scheduling the two-machine open shop problem under resource constraints for setting the jobs," Annals of Operations Research, Springer, vol. 211(1), pages 333-356, December.
    • Handle: RePEc:spr:annopr:v:211:y:2013:i:1:p:333-356:10.1007/s10479-013-1446-9
    DOI: 10.1007/s10479-013-1446-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-013-1446-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-013-1446-9?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. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    2. Celia A. Glass & Yakov M. Shafransky & Vitaly A. Strusevich, 2000. "Scheduling for parallel dedicated machines with a single server," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(4), pages 304-328, June.
    3. Bernd Jurisch & Wieslaw Kubiak, 1997. "Two-Machine Open Shops with Renewable Resources," Operations Research, INFORMS, vol. 45(4), pages 544-552, August.
    4. Kellerer, H. & Strusevich, V. A., 2003. "Scheduling parallel dedicated machines under a single non-shared resource," European Journal of Operational Research, Elsevier, vol. 147(2), pages 345-364, June.
    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. Baptiste, Pierre & Rebaine, Djamal & Zouba, Mohammed, 2017. "FPTAS for the two identical parallel machine problem with a single operator under the free changing mode," European Journal of Operational Research, Elsevier, vol. 256(1), pages 55-61.
    2. Victor Fernandez-Viagas & Luis Sanchez-Mediano & Alvaro Angulo-Cortes & David Gomez-Medina & Jose Manuel Molina-Pariente, 2022. "The Permutation Flow Shop Scheduling Problem with Human Resources: MILP Models, Decoding Procedures, NEH-Based Heuristics, and an Iterated Greedy Algorithm," Mathematics, MDPI, vol. 10(19), pages 1-32, September.
    3. 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.
    4. Nadia Babou & Djamal Rebaine & Mourad Boudhar, 2024. "Solving the two-machine open shop problem with a single server with respect to the makespan," Annals of Operations Research, Springer, vol. 338(2), pages 857-877, July.

    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. Wafaa Labbi & Mourad Boudhar & Ammar Oulamara, 2017. "Scheduling two identical parallel machines with preparation constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1531-1548, March.
    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. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    4. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    5. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    6. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    7. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    8. Dorndorf, Ulrich & Drexl, Andreas & Nikulin, Yury & Pesch, Erwin, 2005. "Flight gate scheduling: State-of-the-art and recent developments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 584, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre (Ed.), 2000. "Jahresbericht 1999," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 522, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Drexl, Andreas & Nikulin, Yury, 2006. "Fuzzy multicriteria flight gate assignment," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 605, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. Dmitri Viattchenin, 2015. "Reducing the number of paths in a minimized project-network with given bounds on the durations of activities," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 25(4), pages 71-87.
    12. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2021. "Scheduling Human-Robot Teams in collaborative working cells," International Journal of Production Economics, Elsevier, vol. 235(C).
    13. Artigues, Christian & Michelon, Philippe & Reusser, Stephane, 2003. "Insertion techniques for static and dynamic resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 149(2), pages 249-267, September.
    14. Andrea Sironi & Cristiano Zazzara, 2003. "The Basel Committee proposals for a new capital accord: implications for Italian banks," Review of Financial Economics, John Wiley & Sons, vol. 12(1), pages 99-126.
    15. C-C Chang & R-S Chen, 2007. "Project advancement and its applications to multi-air-route quality budget allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(8), pages 1008-1020, August.
    16. Lova, Antonio & Tormos, Pilar & Cervantes, Mariamar & Barber, Federico, 2009. "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes," International Journal of Production Economics, Elsevier, vol. 117(2), pages 302-316, February.
    17. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    18. Kemmoé Tchomté, Sylverin & Gourgand, Michel, 2009. "Particle swarm optimization: A study of particle displacement for solving continuous and combinatorial optimization problems," International Journal of Production Economics, Elsevier, vol. 121(1), pages 57-67, September.
    19. Bowen Guo & Wei Zhan, 2023. "Research on Integrated Scheduling of Multi-Mode Emergency Rescue for Flooding in Chemical Parks," Sustainability, MDPI, vol. 15(4), pages 1-18, February.
    20. Boysen, Nils & Briskorn, Dirk & Schwerdfeger, Stefan, 2019. "Matching supply and demand in a sharing economy: Classification, computational complexity, and application," European Journal of Operational Research, Elsevier, vol. 278(2), pages 578-595.

    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:211:y:2013:i:1:p:333-356:10.1007/s10479-013-1446-9. 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.