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

On-line two-machine open shop scheduling with time lags

Author

Listed:
  • Zhang, Xiandong
  • van de Velde, Steef

Abstract

We analyze the performance of the greedy algorithm for the on-line two-machine open shop scheduling problem of minimizing makespan, in which time lags exist between the completion time of the first and the start time of the second operation of any job. The competitive ratio for the greedy algorithm is 2, and it can be reduced to 5/3 if the maximum time lag is less than the minimum positive processing time of any operation. These ratios are tight. We also prove that no on-line non-delay algorithm can have a better competitive ratio. As far as delay algorithms are concerned, no algorithm can do better than the greedy algorithm for the non-clairvoyant variant of the problem. For the clairvoyant variant, no on-line delay algorithm has a competitive ratio better than .

Suggested Citation

  • Zhang, Xiandong & van de Velde, Steef, 2010. "On-line two-machine open shop scheduling with time lags," European Journal of Operational Research, Elsevier, vol. 204(1), pages 14-19, July.
    • Handle: RePEc:eee:ejores:v:204:y:2010:i:1:p:14-19
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00638-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Kanet, John J., 1986. "Tactically delayed versus non-delay scheduling: An experimental investigation," European Journal of Operational Research, Elsevier, vol. 24(1), pages 99-105, January.
    2. Bo Chen & Arjen P.A. Vestjens & Gerhard J. Woeginger, 1998. "On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time," Journal of Combinatorial Optimization, Springer, vol. 1(4), pages 355-365, December.
    3. John J. Kanet & V. Sridharan, 2000. "Scheduling with Inserted Idle Time: Problem Taxonomy and Literature Review," Operations Research, INFORMS, vol. 48(1), pages 99-110, February.
    4. D Rebaine & V A Strusevich, 1999. "Two-machine open shop scheduling with special transportation times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 756-764, July.
    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. Courtad, Brenda & Baker, Kenneth & Magazine, Michael & Polak, George, 2017. "Minimizing flowtime for paired tasks," European Journal of Operational Research, Elsevier, vol. 259(3), pages 818-828.
    2. Madiha Harrabi & Olfa Belkahla Driss & Khaled Ghedira, 2021. "A hybrid evolutionary approach to job-shop scheduling with generic time lags," Journal of Scheduling, Springer, vol. 24(3), pages 329-346, June.
    3. 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.
    4. 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. Jaeseok Huh & Inbeom Park & Seongmin Lim & Bohyung Paeng & Jonghun Park & Kwanho Kim, 2018. "Learning to Dispatch Operations with Intentional Delay for Re-Entrant Multiple-Chip Product Assembly Lines," Sustainability, MDPI, vol. 10(11), pages 1-21, November.
    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. Haiyan Wang & Chung‐Yee Lee, 2005. "Production and transport logistics scheduling with two transport mode choices," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(8), pages 796-809, December.
    4. 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.
    5. Waldherr, Stefan & Knust, Sigrid & Briskorn, Dirk, 2017. "Synchronous flow shop problems: How much can we gain by leaving machines idle?," Omega, Elsevier, vol. 72(C), pages 15-24.
    6. Jorge M. S. Valente, 2007. "Beam search heuristics for the single machine scheduling problem with linear earliness and quadratic tardiness costs," FEP Working Papers 250, Universidade do Porto, Faculdade de Economia do Porto.
    7. Kerem Bülbül & Safia Kedad-Sidhoum & Halil Şen, 2019. "Single-machine common due date total earliness/tardiness scheduling with machine unavailability," Journal of Scheduling, Springer, vol. 22(5), pages 543-565, October.
    8. Jorge M. S. Valente, 2008. "Beam search heuristics for quadratic earliness and tardiness scheduling," FEP Working Papers 279, Universidade do Porto, Faculdade de Economia do Porto.
    9. Munier-Kordon, Alix & Rebaine, Djamal, 2010. "The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 203(1), pages 42-49, May.
    10. Akturk, M. Selim & Ozdemir, Deniz, 2001. "A new dominance rule to minimize total weighted tardiness with unequal release dates," European Journal of Operational Research, Elsevier, vol. 135(2), pages 394-412, December.
    11. Black, Gary W. & McKay, Kenneth N. & Morton, Thomas E., 2006. "Aversion scheduling in the presence of risky jobs," European Journal of Operational Research, Elsevier, vol. 175(1), pages 338-361, November.
    12. F. Hwang & M. Kovalyov & B. Lin, 2014. "Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence," Annals of Operations Research, Springer, vol. 217(1), pages 263-279, June.
    13. Guang Feng & Hoong Lau, 2008. "Efficient algorithms for machine scheduling problems with earliness and tardiness penalties," Annals of Operations Research, Springer, vol. 159(1), pages 83-95, March.
    14. N Nekoiemehr & G Moslehi, 2011. "Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1403-1412, July.
    15. Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    16. Karen A. Brown & Thomas G. Schmitt & Richard J. Schonberger & Stephen Dennis, 2004. "Quadrant Homes Applies Lean Concepts in a Project Environment," Interfaces, INFORMS, vol. 34(6), pages 442-450, December.
    17. Shen, Liji & Dauzère-Pérès, Stéphane & Maecker, Söhnke, 2023. "Energy cost efficient scheduling in flexible job-shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 310(3), pages 992-1016.
    18. Jorge M. S. Valente & Maria R. A. Moreira & Alok Singh & Rui A. F. S. Alves, 2009. "Genetic algorithms for single machine scheduling with quadratic earliness and tardiness costs," FEP Working Papers 312, Universidade do Porto, Faculdade de Economia do Porto.
    19. Alidaee, Bahram & Li, Haitao & Wang, Haibo & Womer, Keith, 2021. "Integer programming formulations in sequencing with total earliness and tardiness penalties, arbitrary due dates, and no idle time: A concise review and extension," Omega, Elsevier, vol. 103(C).
    20. 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.

    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:204:y:2010:i:1:p:14-19. 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.