Abstract:
Unlike time restrictions on jobs, such as release dates or deadlines, which are common in scheduling, we consider position restrictions. For example, a job may be required to be in position x of the job sequence. Such a restriction may be motivated by maintenance scheduling, among other things. In maintenance scheduling, we may also encounter constraints, such as a maintenance operation that must be performed after executing at most k jobs.
We provide an overview of classical one-machine problems and demonstrate how these additional constraints affect their complexity. While the complexity remains unchanged for many cases, it changes for some, revealing surprising effects.