Scheduling coupled tasks with exact delays

What is it about?

In this paper, we fill in a conspicuous gap in research on scheduling coupled tasks. We draw a full complexity picture for single-machine scheduling of coupled tasks with exact time delays in between with the objective of minimizing the total of job completion times.

Featured Image

Why is it important?

The problem of scheduling coupled tasks with exact delays was first introduced to model the scheduling of a radar tracking system in which the system transmits pulses and receives their reflections once every specified update period. The transmission and reception of a radar pulse are modeled as a pair of coupled tasks with a fixed length of time lag in between. This basic model of scheduling coupled tasks has been studied for various radar tracking systems of multiple targets and/or multiple functionalities with various objective functions. This scheduling model has also found many other applications, ranging from improving performance of submarine torpedoes to chemistry manufacturing processes, to scheduling systems of robotic cells and to patient appointments in a chemotherapy outpatient clinic.