Article ID: | iaor20084399 |
Country: | Netherlands |
Volume: | 178 |
Issue: | 1 |
Start Page Number: | 46 |
End Page Number: | 56 |
Publication Date: | Apr 2007 |
Journal: | European Journal of Operational Research |
Authors: | Cheng T.C. Edwin, Yuan J.J., Ng C.T., Lin Y.X. |
Keywords: | combinatorial analysis |
We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time