Scheduling projects with labor constraints

In this paper we consider a labor constrained scheduling problem (LCSP) whi ch is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Mor eover, for each job the labor requirement varies as the job is processed. G iven the amount of labor available in each period, the problem is to finish all the jobs as soon as possible, that is, to minimize the makespan, subje ct to the precedence and labor constraints. Several integer programming (IP ) formulations for this problem are discussed and valid inequalities for th ese different models are introduced. It turns out that a major drawback in using an IP approach is the weakness of the lower bound relaxations. Howeve r, we report computational experiments showing how the solution of the line ar relaxation of the IP models can be used to provide good schedules. Solut ions arising from these LP-based heuristics are considerably improved by lo cal search procedures. We further exploit the capabilities of local search for LCSP by designing a Tabu search algorithm. The computational experiment s on a benchmark data set show that the Tabu search algorithm generates the best-known upper bounds for almost all these instances. We also show how I P can be used to provide reasonably good lower bounds for LCSP when the mak espan is replaced by suitably modified objective functions. Finally, some d irections for further investigations which may turn IP techniques into a mo re interesting tool for solving such a problem are suggested. (C) 2001 Else vier Science B.V. All rights reserved.