Coupled‐task scheduling on a single machine subject to a fixed‐job‐sequence

This paper investigates single‐machine coupled‐task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed‐job‐sequence problem under study. While the complexity status of the studied problem remains open, an O(n ²) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed‐job‐sequence constraint. We investigate several polynomially solvable cases of the fixed‐job‐sequence problem and present a complexity graph of the problem.