IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v3y1999i1d10.1023_a1009817206440.html
   My bibliography  Save this article

Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks

Author

Listed:
  • Keqin Li

    (State University of New York)

Abstract

Given P processors, and a set of precedence constrained parallel tasks with their processor requirements and execution times, the problem of scheduling precedence constrained parallel tasks on multiprocessors is to find a nonpreemptive schedule of the tasks on a multiprocessor with P processors, such that the schedule length is minimized. We show that for many heuristic choices of the initial priority list, the list scheduling algorithm has worst-case performance ratio P, which is unbounded as P gets large. However, it is also shown that when task sizes are bounded from above by a fraction of P, the list scheduling algorithm has finite worst-case performance ratio. In particular, we prove that if all tasks request for no more than qP processors, where 0

Suggested Citation

  • Keqin Li, 1999. "Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 73-88, July.
    • Handle: RePEc:spr:jcomop:v:3:y:1999:i:1:d:10.1023_a:1009817206440
    DOI: 10.1023/A:1009817206440
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009817206440
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009817206440?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. Drozdowski, Maciej, 1996. "Scheduling multiprocessor tasks -- An overview," European Journal of Operational Research, Elsevier, vol. 94(2), pages 215-230, October.
    2. Errol L. Lloyd, 1981. "Concurrent Task Systems," Operations Research, INFORMS, vol. 29(1), pages 189-201, February.
    3. J. K. Lenstra & A. H. G. Rinnooy Kan, 1978. "Complexity of Scheduling under Precedence Constraints," Operations Research, INFORMS, vol. 26(1), pages 22-35, 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. Alexander Kononov & Yulia Zakharova, 2022. "Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion," Journal of Global Optimization, Springer, vol. 83(3), pages 539-564, July.

    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. Wu, Lingxiao & Wang, Shuaian, 2018. "Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks," International Journal of Production Economics, Elsevier, vol. 201(C), pages 26-40.
    2. Oguz, C. & Fikret Ercan, M. & Edwin Cheng, T. C. & Fung, Y. F., 2003. "Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop," European Journal of Operational Research, Elsevier, vol. 149(2), pages 390-403, September.
    3. Oguz, Ceyda & Zinder, Yakov & Ha Do, Van & Janiak, Adam & Lichtenstein, Maciej, 2004. "Hybrid flow-shop scheduling problems with multiprocessor task systems," European Journal of Operational Research, Elsevier, vol. 152(1), pages 115-131, January.
    4. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Malyutin, Sergey & Soukhal, Ameur, 2018. "Optimal workforce assignment to operations of a paced assembly line," European Journal of Operational Research, Elsevier, vol. 264(1), pages 200-211.
    5. Fatma-Zohra Baatout & Mhand Hifi, 2023. "A two-phase hybrid evolutionary algorithm for solving the bi-objective scheduling multiprocessor tasks on two dedicated processors," Journal of Heuristics, Springer, vol. 29(2), pages 229-267, June.
    6. Ravindran Vijayalakshmi, Vipin & Schröder, Marc & Tamir, Tami, 2024. "Minimizing total completion time with machine-dependent priority lists," European Journal of Operational Research, Elsevier, vol. 315(3), pages 844-854.
    7. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2021. "Scheduling Human-Robot Teams in collaborative working cells," International Journal of Production Economics, Elsevier, vol. 235(C).
    8. Yan Zhao & Liping Chen & Gang Xie & Jianjun Zhao & Jianwan Ding, 2018. "GPU implementation of a cellular genetic algorithm for scheduling dependent tasks of physical system simulation programs," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 293-317, January.
    9. 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.
    10. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "An Introduction To Multiprocessor Scheduling," Econometric Institute Archives 272258, Erasmus University Rotterdam.
    11. Katarina Cechlarova & Bettina Klaus & David F.Manlove, 2018. "Pareto optimal matchings of students to courses in the presence of prerequisites," Cahiers de Recherches Economiques du Département d'économie 16.04, Université de Lausanne, Faculté des HEC, Département d’économie.
    12. Elisabeth Günther & Felix G. König & Nicole Megow, 2014. "Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width," Journal of Combinatorial Optimization, Springer, vol. 27(1), pages 164-181, January.
    13. Ahadi, Khatereh & Sullivan, Kelly M. & Mitchell, Kenneth Ned, 2018. "Budgeting maintenance dredging projects under uncertainty to improve the inland waterway network performance," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 119(C), pages 63-87.
    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. Christoph Ambühl & Monaldo Mastrolilli & Nikolaus Mutsanas & Ola Svensson, 2011. "On the Approximability of Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 653-669, November.
    16. 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.
    17. Guo, Peng & Weidinger, Felix & Boysen, Nils, 2019. "Parallel machine scheduling with job synchronization to enable efficient material flows in hub terminals," Omega, Elsevier, vol. 89(C), pages 110-121.
    18. Ntuen, Celestine A. & Park, Eui H., 1995. "An experiment in scheduling and planning of non-structured jobs: Lessons learned from artificial intelligence and operational research toolbox," European Journal of Operational Research, Elsevier, vol. 84(1), pages 96-115, July.
    19. Markó Horváth & Tamás Kis, 2020. "Polyhedral results for position-based scheduling of chains on a single machine," Annals of Operations Research, Springer, vol. 284(1), pages 283-322, January.
    20. Levitin, Gregory & Xie, Min & Zhang, Tieling, 2007. "Reliability of fault-tolerant systems with parallel task processing," European Journal of Operational Research, Elsevier, vol. 177(1), pages 420-430, February.

    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:3:y:1999:i:1:d:10.1023_a:1009817206440. 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.