Abstract
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 language | English |
---|---|
Pages (from-to) | 69-79 |
Number of pages | 11 |
Journal | Discrete Optimization |
Volume | 17 |
DOIs | |
State | Published - Aug 2015 |
Keywords
- Number of late jobs
- Single-machine scheduling
- Supporting precedence
- Total weighted completion time