Title :
Scheduling Coupled-Tasks on a Single Machine
Author :
Li, Haibing ; Zhao, Hairong
Author_Institution :
Lehman Bros. Inc., New York, NY
Abstract :
In this paper, we consider the coupled-task scheduling problem, to schedule n jobs on a single machine. Each job consists of two coupled tasks which have to be processed in a predetermined order and at exactly a specified interval apart. The objective is to minimize the makespan. The problem was shown to be NP-hard in the strong sense even for some special cases. We analyze some heuristics with worst-case bounds for some NP-hard cases. In addition, we present a tabu search meta-heuristic for solving the general case. Computational results show that the meta-heuristic is efficient to solve the problem in terms of solution quality and running time
Keywords :
computational complexity; search problems; single machine scheduling; NP-hard; coupled-tasks scheduling; single machine scheduling; tabu search metaheuristic; Algorithm design and analysis; Approximation algorithms; Computational intelligence; Delay; Dynamic programming; Heuristic algorithms; Polynomials; Processor scheduling; Scheduling algorithm; Single machine scheduling;
Conference_Titel :
Computational Intelligence in Scheduling, 2007. SCIS '07. IEEE Symposium on
Conference_Location :
Honolulu, HI
Print_ISBN :
1-4244-0704-4
DOI :
10.1109/SCIS.2007.367681
