IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v36y2018i2d10.1007_s10878-018-0309-3.html
   My bibliography  Save this article

Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

Author

Listed:
  • Xing Chai

    (Zhengzhou University)

  • Wenhua Li

    (Zhengzhou University
    Hennan Key Laboratory of Financial Engineering)

Abstract

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case $$m=2$$ m = 2 . But the problem is unaddressed for $$m\ge 3$$ m ≥ 3 . In this paper, we present a best possible online algorithm for the problem with $$m\ge 3$$ m ≥ 3 , where the algorithm has a competitive ratio of 1.3028 for $$3\le m\le 5$$ 3 ≤ m ≤ 5 and 1.3146 for $$m\ge 6$$ m ≥ 6 .

Suggested Citation

  • Xing Chai & Wenhua Li, 2018. "Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan," Journal of Combinatorial Optimization, Springer, vol. 36(2), pages 472-492, August.
    • Handle: RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-018-0309-3
    DOI: 10.1007/s10878-018-0309-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-018-0309-3
    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/s10878-018-0309-3?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. T. C. Hu, 1961. "Parallel Sequencing and Assembly Line Problems," Operations Research, INFORMS, vol. 9(6), pages 841-848, December.
    2. Peter Brucker & Johann Hurink & Wieslaw Kubiak, 1999. "Scheduling identical jobs with chain precedence constraints on two uniform machines," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(2), pages 211-219, April.
    3. Agnetis, Alessandro & Flamini, Marta & Nicosia, Gaia & Pacifici, Andrea, 2010. "Scheduling three chains on two parallel machines," European Journal of Operational Research, Elsevier, vol. 202(3), pages 669-674, May.
    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. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.

    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. Jiang, Xiaojuan & Lee, Kangbok & Pinedo, Michael L., 2021. "Ideal schedules in parallel machine settings," European Journal of Operational Research, Elsevier, vol. 290(2), pages 422-434.
    2. D. Prot & O. Bellenguez-Morineau, 2018. "A survey on how the structure of precedence constraints may change the complexity class of scheduling problems," Journal of Scheduling, Springer, vol. 21(1), pages 3-16, February.
    3. Anurag Agarwal & Varghese S. Jacob & Hasan Pirkul, 2006. "An Improved Augmented Neural-Network Approach for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 119-128, February.
    4. Nodari Vakhania, 2001. "Tight Performance Bounds of CP-Scheduling on Out-Trees," Journal of Combinatorial Optimization, Springer, vol. 5(4), pages 445-464, December.
    5. Agnetis, Alessandro & Kellerer, Hans & Nicosia, Gaia & Pacifici, Andrea, 2012. "Parallel dedicated machines scheduling with chain precedence constraints," European Journal of Operational Research, Elsevier, vol. 221(2), pages 296-305.
    6. Ramachandra, Girish & Elmaghraby, Salah E., 2006. "Sequencing precedence-related jobs on two machines to minimize the weighted completion time," International Journal of Production Economics, Elsevier, vol. 100(1), pages 44-58, March.
    7. Ecker, Klaus H., 1999. "Scheduling of resource tasks," European Journal of Operational Research, Elsevier, vol. 115(2), pages 314-327, June.
    8. Faramroze G. Engineer & Pınar Keskinocak & Larry K. Pickering, 2009. "OR Practice---Catch-Up Scheduling for Childhood Vaccination," Operations Research, INFORMS, vol. 57(6), pages 1307-1319, December.
    9. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "An Introduction To Multiprocessor Scheduling," Econometric Institute Archives 272258, Erasmus University Rotterdam.
    10. Timkovsky, Vadim G., 2003. "Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity," European Journal of Operational Research, Elsevier, vol. 149(2), pages 355-376, September.
    11. Tianyu Wang & Odile Bellenguez, 2021. "Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time," Journal of Scheduling, Springer, vol. 24(6), pages 649-662, December.
    12. Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    13. Finke, Gerd & Lemaire, Pierre & Proth, Jean-Marie & Queyranne, Maurice, 2009. "Minimizing the number of machines for minimum length schedules," European Journal of Operational Research, Elsevier, vol. 199(3), pages 702-705, December.
    14. Blazewicz, Jacek & Liu, Zhen, 2002. "Linear and quadratic algorithms for scheduling chains and opposite chains," European Journal of Operational Research, Elsevier, vol. 137(2), pages 248-264, March.
    15. Felix Happach, 2021. "Makespan minimization with OR-precedence constraints," Journal of Scheduling, Springer, vol. 24(3), pages 319-328, June.
    16. Rodriguez Diaz, Antonio & Tchernykh, Andrei & Ecker, Klaus H., 2003. "Algorithms for dynamic scheduling of unit execution time tasks," European Journal of Operational Research, Elsevier, vol. 146(2), pages 403-416, April.
    17. Sonja Kolen & Stefan Dähling & Timo Isermann & Antonello Monti, 2018. "Enabling the Analysis of Emergent Behavior in Future Electrical Distribution Systems Using Agent-Based Modeling and Simulation," Complexity, Hindawi, vol. 2018, pages 1-16, February.
    18. Wilbert E. Wilhelm, 1987. "Complexity of sequencing tasks in assembly cells attended by one or two robots," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(5), pages 721-738, October.
    19. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    20. Tianyu Wang & Odile Bellenguez-Morineau, 2019. "The Complexity of Parallel Machine Scheduling of Unit-Processing-Time Jobs under Level-Order Precedence Constraints," Journal of Scheduling, Springer, vol. 22(3), pages 263-269, June.

    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:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-018-0309-3. 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.