Scheduling projects with labor constraints

Cristina C.B. Cavalcante, Cid Carvalho de Souza, Martin W.P. Savelsbergh and Yaoguang Wang
Additional contact information
Cristina C.B. Cavalcante: Instituto de Computacao, Universidade Estadual de Campinas — UNICAMP, Caixa Postal 6176 – CEP: 13083-970 – Campinas, SP – Brazil
Cid Carvalho de Souza: Instituto de Computacao, Universidade Estadual de Campinas — UNICAMP, Caixa Postal 6176 – CEP: 13083-970 – Campinas, SP – Brazil
Martin W.P. Savelsbergh: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA
Yaoguang Wang: Navigation Technologies, 10400 W. Higgins Road, Rosemont, IL 60018

No 1998059, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 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 the 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 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.

Keywords: Pro ject Scheduling; Labor Constraints; Integer Programming; Valid Inequalities; Tabu Search; LP-based Ordering Heuristics (search for similar items in EconPapers)
Date: 1998-09-01
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1998.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1998059

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().