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. 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.
    2. 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.
    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. 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.
    5. 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.
    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. 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.
    4. 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.
    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. 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.
    7. Inna G. Drobouchevitch, 2021. "Three-machine open shop with a bottleneck machine revisited," Journal of Scheduling, Springer, vol. 24(2), pages 197-208, April.
    8. 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.
    9. 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.
    10. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    11. 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.
    12. Drobouchevitch, I. G. & Strusevich, V. A., 2000. "Heuristics for the two-stage job shop scheduling problem with a bottleneck machine," European Journal of Operational Research, Elsevier, vol. 123(2), pages 229-240, June.
    13. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    14. Jansen, Klaus & Mastrolilli, Monaldo & Solis-Oba, Roberto, 2005. "Approximation schemes for job shop scheduling problems with controllable processing times," European Journal of Operational Research, Elsevier, vol. 167(2), pages 297-319, December.
    15. E. Dhouib & J. Teghem & T. Loukil, 2018. "Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic," Annals of Operations Research, Springer, vol. 267(1), pages 101-134, August.
    16. Ward Passchyn & Frits C. R. Spieksma, 2019. "Scheduling parallel batching machines in a sequence," Journal of Scheduling, Springer, vol. 22(3), pages 335-357, June.
    17. Min, Yun-Hong & Park, Myoung-Ju & Hong, Sung-Pil & Hong, Soon-Heum, 2011. "An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 409-429, February.
    18. Yong Chen & Yinhui Cai & Longcheng Liu & Guangting Chen & Randy Goebel & Guohui Lin & Bing Su & An Zhang, 2022. "Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 571-588, April.
    19. Olivier Ploton & Vincent T’kindt, 2023. "Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using Inclusion–Exclusion," Journal of Scheduling, Springer, vol. 26(2), pages 137-145, April.
    20. Nikhil Bansal & Tracy Kimbrel & Maxim Sviridenko, 2006. "Job Shop Scheduling with Unit Processing Times," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 381-389, May.

    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.