Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem

Cristina Cavalcante (crisdcc.unicamp.br)
Victor Cavalcante (vfmdcc.unicamp.br)
Celso Ribeiro (celsoinf.puc-rio.br)
Cid Souza (cidic.unicamp.br)

Abstract: In this paper we consider the labor constrained scheduling problem (LCSP), in which a set of jobs to be processed is subject to precedence and labor requirement constraints. Each job has a specified processing time and a labor requirements profile, which typically varies as the job is processed. Given the amount of labor available at each period, the problem consists in determining starting times so as to minimize the overall makespan, subject to the precedence and labor constraints. We propose two parallel cooperative algorithms for LCSP: an asynchronous team and a parallel tabu search strategy. Both algorithms make use of cooperative processes that asynchronously exchange information gathered along their execution. Computational experiments on benchmark instances show that these parallel algorithms produce significantly better solutions than all sequential algorithms previously proposed in the literature.

Keywords: project scheduling, labor constraints, heuristics, parallel tabu search, asynchronous teams

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: To appear in Essays and Surveys in Metaheuristics (C.C. Ribeiro and P. Hansen, editors), Kluwer, 2001.

Download: [Postscript]

Entry Submitted: 05/03/2001
Entry Accepted: 05/03/2001
Entry Last Modified: 05/03/2001

Modify/Update this entry