An exact algorithm for scheduling identical coupled tasks

The coupled task problem is to schedule n jobs on one machine where each job consists of two subtasks with required delay time between them. The objective is to minimize the makespan. This problem was analyzed in depth by Orman and Potts [3]. They investigated the complexity of different cases depending on the lengths a <Subscript> i </Subscript> and b <Subscript> i </Subscript> of the two subtasks and the delay time L <Subscript> i </Subscript>. [InlineMediaObject not available: see fulltext.][InlineMediaObject not available: see fulltext.]-hardness proofs or polynomial algorithms were given for all cases except for the one where a <Subscript> i </Subscript>=a, b <Subscript> i </Subscript>=b and L <Subscript> i </Subscript>=L. In this paper we present an exact algorithm for this problem with time complexity O(nr <Superscript> 2L </Superscript>) where [InlineMediaObject not available: see fulltext.] holds. Therefore the algorithm is linear in the number of jobs for fixed L. Copyright Springer-Verlag 2004