IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v24y2021i4d10.1007_s10951-021-00694-7.html
   My bibliography  Save this article

A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

Author

Listed:
  • Antonina P. Khramova

    (Sobolev Institute of Mathematics)

  • Ilya Chernykh

    (Sobolev Institute of Mathematics)

Abstract

The two-machine open shop problem was proved to be solvable in linear time by Teofilo Gonzalez and Sartaj Sahni in 1976. Several algorithms for solving that problem have been proposed since that time. We introduce another optimal algorithm for that classical problem with an interesting property: it allows to process jobs in almost arbitrary order, unlike the Gohzalez–Sahni algorithm where jobs have to be partitioned into two specific subsets. This new algorithm in turn helps us to solve a much more general problem: the easy-TSP version of the routing open shop with a variable depot, in which unmovable jobs are located in the nodes of a transportation network (with optimal route known), and mobile machines have to travel between the nodes to process jobs in the open shop environment. The common initial location of the machines is not fixed but has to be chosen, and all machines have to return to that location—the depot—to minimize finish time. We also consider the generalization of this problem in which travel times are individual for each machine. This contributes to the discussion on the differences between different scheduling models with transportation delays: classic transportation delays (in our terms, with no depot at all), with a variable depot, and with a fixed depot. It turns out that the depot makes the difference and makes the problem harder to solve.

Suggested Citation

  • Antonina P. Khramova & Ilya Chernykh, 2021. "A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing," Journal of Scheduling, Springer, vol. 24(4), pages 405-412, August.
    • Handle: RePEc:spr:jsched:v:24:y:2021:i:4:d:10.1007_s10951-021-00694-7
    DOI: 10.1007/s10951-021-00694-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-021-00694-7
    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/s10951-021-00694-7?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. Esswein, Carl & Billaut, Jean-Charles & Strusevich, Vitaly A., 2005. "Two-machine shop scheduling: Compromise between flexibility and makespan value," European Journal of Operational Research, Elsevier, vol. 167(3), pages 796-809, December.
    2. D. P. Williamson & L. A. Hall & J. A. Hoogeveen & C. A. J. Hurkens & J. K. Lenstra & S. V. Sevast'janov & D. B. Shmoys, 1997. "Short Shop Schedules," Operations Research, INFORMS, vol. 45(2), pages 288-294, April.
    3. Peter Brucker & Sigrid Knust & T.C. Cheng & Natalia Shakhlevich, 2004. "Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays," Annals of Operations Research, Springer, vol. 129(1), pages 81-106, July.
    4. Averbakh, Igor & Berman, Oded & Chernykh, Ilya, 2006. "The routing open-shop problem on a network: Complexity and approximation," European Journal of Operational Research, Elsevier, vol. 173(2), pages 531-539, September.
    5. Igor Averbakh & Oded Berman, 1999. "A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems," Operations Research, INFORMS, vol. 47(1), pages 165-170, February.
    6. Averbakh, Igor & Berman, Oded & Chernykh, Ilya, 2005. "A -approximation algorithm for the two-machine routing open-shop problem on a two-node network," European Journal of Operational Research, Elsevier, vol. 166(1), pages 3-24, October.
    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. 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. 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.
    3. 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.
    4. Averbakh, Igor & Berman, Oded & Chernykh, Ilya, 2006. "The routing open-shop problem on a network: Complexity and approximation," European Journal of Operational Research, Elsevier, vol. 173(2), pages 531-539, September.
    5. Gupta, Jatinder N.D. & Koulamas, Christos & Kyparisis, George J., 2006. "Performance guarantees for flowshop heuristics to minimize makespan," European Journal of Operational Research, Elsevier, vol. 169(3), pages 865-872, March.
    6. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    7. Wiesław Kubiak, 2023. "On the complexity of open shop scheduling with time lags," Journal of Scheduling, Springer, vol. 26(3), pages 331-334, June.
    8. Hans Kellerer & Alan J. Soper & Vitaly A. Strusevich, 2013. "Preemptive scheduling on two identical parallel machines with a single transporter," Journal of Combinatorial Optimization, Springer, vol. 25(2), pages 279-307, February.
    9. Kubale, Marek & Nadolski, Adam, 2005. "Chromatic scheduling in a cyclic open shop," European Journal of Operational Research, Elsevier, vol. 164(3), pages 585-591, August.
    10. Han Hoogeveen & Petra Schuurman & Gerhard J. Woeginger, 2001. "Non-Approximability Results for Scheduling Problems with Minsum Criteria," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 157-168, May.
    11. D Bai & L Tang, 2010. "New heuristics for flow shop problem to minimize makespan," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(6), pages 1032-1040, June.
    12. Inna G. Drobouchevitch, 2021. "Three-machine open shop with a bottleneck machine revisited," Journal of Scheduling, Springer, vol. 24(2), pages 197-208, April.
    13. 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.
    14. Drobouchevitch, Inna G. & Strusevich, Vitaly A., 2001. "Two-stage open shop scheduling with a bottleneck machine," European Journal of Operational Research, Elsevier, vol. 128(1), pages 159-174, January.
    15. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    16. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    17. Choi, Byung-Cheon & Yoon, Suk-Hun & Chung, Sung-Jin, 2007. "Minimizing maximum completion time in a proportionate flow shop with one machine of different speed," European Journal of Operational Research, Elsevier, vol. 176(2), pages 964-974, January.
    18. 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.
    19. Hadda, Hatem & Dridi, Najoua & Hajji, Mohamed Karim, 2018. "On the optimality conditions of the two-machine flow shop problem," European Journal of Operational Research, Elsevier, vol. 266(2), pages 426-435.
    20. Yuri N. Sotskov, 2020. "Mixed Graph Colorings: A Historical Review," Mathematics, MDPI, vol. 8(3), pages 1-24, March.

    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:jsched:v:24:y:2021:i:4:d:10.1007_s10951-021-00694-7. 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.