Single-machine scheduling with supporting tasks

Alexander V. Kononov, Bertrand M.T. Lin*, Kuei Tang Fang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


This paper investigates a single-machine scheduling problem with a set of supporting tasks and a set of jobs. Each job is preceded by a subset of supporting tasks, that is, the job cannot start its processing until all of its supporting tasks are finished. The objective functions are defined solely in job completion times. We discuss the complexities of several special cases for the number of late jobs and the total weighted completion time. This study adds new complexity results to the two standard objective functions under precedence constraints.

Original languageEnglish
Pages (from-to)69-79
Number of pages11
JournalDiscrete Optimization
StatePublished - Aug 2015


  • Number of late jobs
  • Single-machine scheduling
  • Supporting precedence
  • Total weighted completion time

Fingerprint Dive into the research topics of 'Single-machine scheduling with supporting tasks'. Together they form a unique fingerprint.

Cite this