Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Scheduling Projects With Labor Constraints
Author: Cavalcante C.C.B.
Carvalho De Souza C.
Savelsbergh M.W.P.
Wang Y.
Wolsey L.A.
Abstract: In this paper we consider a labor constrained scheduling problem (LCSP) which is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labor requirement varies as the job is processed. Given 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, subject to the precedence and labor constraints. Several integer programming (IP) formulations for this problem are discussed and valid inequalities for these different models are introduced. It turns out that a major drawback in using an IP approach is the weakness of the lower bound relaxations. However, we report computational experiments showing how the solution of the linear relaxation of the IP models can be used to provide good schedules. Solutions arising from these LP-based heuristics are considerably improved by local search procedures. We further exploit the capabilities of local search for LCSP by designing a Tabu search algorithm. The computational experiments 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 IP can be used to provide reasonably good lower bounds for LCSP when the makespan is replaced by suitably modified objective functions. Finally, some directions for further investigations which may turn IP techniques into a more interesting tool for solving such a problem are suggested. © 2001 Elsevier Science B.V.
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(00)00308-5
Date Issue: 2001
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-0345821708.pdf178.85 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.