A note on scheduling coupled tasks for minimum total completion time

Wiesław Kubiak ()
Additional contact information
Wiesław Kubiak: Memorial University

Annals of Operations Research, 2023, vol. 320, issue 1, No 22, 544 pages

Abstract: Abstract A recent Journal of Scheduling paper by Chen and Zhang (J Sched, 2020. https://doi.org/10.1007/s10951-020-00668-1 ) proves that the problem of scheduling coupled tasks to minimize total completion time is NP-hard in the strong sense even for the case with all tasks having the same, though not necessarily unit, processing times. This note shows a simpler proof of that result, and strengthens it by proving that the problem is NP-hard in the strong sense even if all tasks are unit-time.

Keywords: Coupled tasks; Total completion time; Complexity (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04706-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:320:y:2023:i:1:d:10.1007_s10479-022-04706-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04706-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().