Approximation algorithms for UET scheduling problems with exact delays

摘要

In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively. (c) 2006 Elsevier B.V. All rights reserved.