Minimizing flowtime for paired tasks

Certain service and production systems require that a single processor complete, for each job, a pair of ordered tasks separated in time by a minimal required delay. In particular, circumstances, this mode of operation can characterize a physician in a hospital Emergency Department, a painting crew at a construction site, or a work station in a job shop. Motivated by these scenarios, we formulate an applicable scheduling problem and investigate its solution. To determine an optimal schedule, we formulate an appropriate mixed integer model in which the key lever for process improvement is the batching of tasks. We further show that two special cases of this problem can be optimally solved efficiently. To expedite decision-making, we propose heuristic approaches supported by spreadsheet based software. Numerical results are then presented and insights discussed.