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

The Complexity of Parallel Machine Scheduling of Unit-Processing-Time Jobs under Level-Order Precedence Constraints

Author

Listed:
  • Tianyu Wang

    (Institut Mines-Télécom Atlantique, LS2N, UMR CNRS 6004)

  • Odile Bellenguez-Morineau

    (Institut Mines-Télécom Atlantique, LS2N, UMR CNRS 6004)

Abstract

In this paper, we prove that parallel machine scheduling problems where jobs have unit processing time and level-order precedence constraints are NP-complete, while minimizing the makespan or the total completion time. These problems are NP-complete even when preemption is allowed. We then adapt the proof to other open problems with out-tree or opposing-forests precedence constraints.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jsched:v:22:y:2019:i:3:d:10.1007_s10951-018-0596-7
    DOI: 10.1007/s10951-018-0596-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0596-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-018-0596-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. T. C. Hu, 1961. "Parallel Sequencing and Assembly Line Problems," Operations Research, INFORMS, vol. 9(6), pages 841-848, December.
    2. Peter Brucker & M. R. Garey & D. S. Johnson, 1977. "Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 275-284, August.
    3. 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.
    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. 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.
    2. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.

    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. 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.
    3. 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.
    4. Tianyu Wang & Odile Bellenguez-Morineau, 2019. "A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time," Journal of Scheduling, Springer, vol. 22(6), pages 709-714, December.
    5. 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.
    6. 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.
    7. Felix Happach, 2021. "Makespan minimization with OR-precedence constraints," Journal of Scheduling, Springer, vol. 24(3), pages 319-328, June.
    8. Jia, Beizhen & Tierney, Kevin & Reinhardt, Line Blander & Pahl, Julia, 2022. "Optimal dual cycling operations in roll-on roll-off terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    9. 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.
    10. 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.
    11. Pascale Bendotti & Luca Brunod Indrigo & Philippe Chrétienne & Bruno Escoffier, 2024. "Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems," Journal of Scheduling, Springer, vol. 27(6), pages 587-606, December.
    12. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "An Introduction To Multiprocessor Scheduling," Econometric Institute Archives 272258, Erasmus University Rotterdam.
    13. Mina Roohnavazfar & Seyed Hamid Reza Pasandideh, 2022. "Decomposition algorithm for the multi-trip single vehicle routing problem with AND-type precedence constraints," Operational Research, Springer, vol. 22(4), pages 4253-4285, September.
    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. 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.
    16. 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.
    17. 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.
    18. Krishnamoorthy, Venkatesh & Efe, Kemal, 1996. "Task scheduling with and without communication delays: A unified approach," European Journal of Operational Research, Elsevier, vol. 89(2), pages 366-379, March.
    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. Kap Hwan Kim & Jong Wook Bae, 2004. "A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals," Transportation Science, INFORMS, vol. 38(2), pages 224-234, 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:22:y:2019:i:3:d:10.1007_s10951-018-0596-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.