IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v238y2014i2p471-475.html
   My bibliography  Save this article

The two-machine no-wait general and proportionate open shop makespan problem

Author

Listed:
  • Panwalkar, S.S.
  • Koulamas, Christos

Abstract

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(nlogn) time. We then propose an optimal O(nlogn) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(nlogn) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.

Suggested Citation

  • Panwalkar, S.S. & Koulamas, Christos, 2014. "The two-machine no-wait general and proportionate open shop makespan problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 471-475.
    • Handle: RePEc:eee:ejores:v:238:y:2014:i:2:p:471-475
    DOI: 10.1016/j.ejor.2014.04.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714003725
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.04.030?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. Sartaj Sahni & Yookun Cho, 1979. "Complexity of Scheduling Shops with No Wait in Process," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 448-457, November.
    2. P. C. Gilmore & R. E. Gomory, 1964. "Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem," Operations Research, INFORMS, vol. 12(5), pages 655-679, October.
    3. Teofilo Gonzalez, 1982. "Unit Execution Time Shop Problems," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 57-66, February.
    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. Panwalkar, S.S., 2016. "The proportionate two-machine no-wait job shop scheduling problemAuthor-Name: Koulamas, Christos," European Journal of Operational Research, Elsevier, vol. 252(1), pages 131-135.
    2. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    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.

    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. Kravchenko, Svetlana A., 1998. "A polynomial algorithm for a two-machine no-wait job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 106(1), pages 101-107, April.
    3. Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2020. "Coupled task scheduling with exact delays: Literature review and models," European Journal of Operational Research, Elsevier, vol. 282(1), pages 19-39.
    4. Burkard, Rainer E., 2007. "Monge properties, discrete convexity and applications," European Journal of Operational Research, Elsevier, vol. 176(1), pages 1-14, January.
    5. 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.
    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. Waldherr, Stefan & Knust, Sigrid, 2017. "Decomposition algorithms for synchronous flow shop problems with additional resources and setup times," European Journal of Operational Research, Elsevier, vol. 259(3), pages 847-863.
    8. A. Ozolins, 2020. "A new exact algorithm for no-wait job shop problem to minimize makespan," Operational Research, Springer, vol. 20(4), pages 2333-2363, December.
    9. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    10. 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.
    11. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    12. Smutnicki, Czeslaw & Pempera, Jaroslaw & Bocewicz, Grzegorz & Banaszak, Zbigniew, 2022. "Cyclic flow-shop scheduling with no-wait constraints and missing operations," European Journal of Operational Research, Elsevier, vol. 302(1), pages 39-49.
    13. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    14. Batur, G. Didem & Karasan, Oya Ekin & Akturk, M. Selim, 2012. "Multiple part-type scheduling in flexible robotic cells," International Journal of Production Economics, Elsevier, vol. 135(2), pages 726-740.
    15. Nikhil Bansal & Mohammad Mahdian & Maxim Sviridenko, 2005. "Minimizing Makespan in No-Wait Job Shops," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 817-831, November.
    16. Christoph Schuster, 2006. "No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(3), pages 473-491, July.
    17. Raaymakers, W. H. M. & Hoogeveen, J. A., 2000. "Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing," European Journal of Operational Research, Elsevier, vol. 126(1), pages 131-151, October.
    18. Delorme, Xavier & Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y., 2019. "Minimizing the number of workers in a paced mixed-model assembly line," European Journal of Operational Research, Elsevier, vol. 272(1), pages 188-194.
    19. Giaro, Krzysztof, 2001. "NP-hardness of compact scheduling in simplified open and flow shops," European Journal of Operational Research, Elsevier, vol. 130(1), pages 90-98, April.
    20. Zhu, Jie & Li, Xiaoping & Wang, Qian, 2009. "Complete local search with limited memory algorithm for no-wait job shops to minimize makespan," European Journal of Operational Research, Elsevier, vol. 198(2), pages 378-386, October.

    More about this item

    Keywords

    Scheduling; Open shop; No wait;
    All these keywords.

    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:eee:ejores:v:238:y:2014:i:2:p:471-475. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.