Marcus Oswald

Title:
A new approach for solving coupled task scheduling problems

Abstract:
The coupled task problem is to schedule jobs on a single machine
where each job consists of two subtasks and where the second subtask has to be
started exactly after a given time gap with respect to the first subtask. The
coupled task problem is NP-hard. We describe a new approach for solving the
problem to optimality. Linear Ordering Variables for each pair of subtasks
were introduced. Then the coupled task conditions can be modelled with the
help of certain knapsack constraints.