A distributed genetic algorithm for deterministic and stochastic labor scheduling problems

LAUR Repository

Show simple item record

dc.contributor.author Mansour, Nashat
dc.contributor.author Easton, Fred F.
dc.date.accessioned 2016-12-06T09:35:42Z
dc.date.available 2016-12-06T09:35:42Z
dc.date.copyright 1999 en_US
dc.date.issued 2016-12-06
dc.identifier.issn 0377-2217 en_US
dc.identifier.uri http://hdl.handle.net/10725/4881
dc.description.abstract A recurring operational decision in many service organizations is determining the number of employees, and their work schedules, that minimize labor expenses and expected opportunity costs. These decisions have been modeled as generalized set covering (GSC) problems, deterministic goal programs (DGP), and stochastic goal programs (SGP); each a challenging optimization problem. The pervasiveness and economic significance of these three problems has motivated ongoing development and refinement of heuristic solution procedures. In this paper we present a unified formulation for these three labor scheduling problems and introduce a distributed genetic algorithm (DGA) that solves each of them. Our distributed genetic algorithm operates in parallel on a network of message-passing workstations. Separate subpopulations of solutions evolve independently on each processor but occasionally, the fittest solutions migrate over the network to join neighboring subpopulations. With its standard genetic operators, DGA frequently produces infeasible offspring. A few of these are repaired before they enter the population. However, most enter the population as-is, carrying an appropriate fitness penalty. This allows DGA to exploit potentially favorable adaptations that might be present in infeasible solutions while orienting the locus of the search near the feasible region. We applied the DGA to suites of published test problems for GSC, DGP, and SGP formulations and compared its performance with alternative solution procedures, including other metaheuristics such as simulated annealing and tabu search. We found that DGA outperformed the competing alternatives in terms of mean error, maximum error, and percentage of least cost solutions. While DGA is computationally intensive, the quality of its solutions is commensurate with the effort expended. In plots of solution quality versus CPU time for the various algorithms evaluated in our study, DGA consistently appeared on the efficient frontier. en_US
dc.language.iso en en_US
dc.title A distributed genetic algorithm for deterministic and stochastic labor scheduling problems en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 198629170 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal European Journal of Operational Research en_US
dc.journal.volume 118 en_US
dc.journal.issue 3 en_US
dc.article.pages 505-523
dc.keywords Scheduling en_US
dc.keywords Genetic algorithms en_US
dc.keywords Heuristics en_US
dc.keywords Goal programs en_US
dc.identifier.doi http://dx.doi.org/10.1016/S0377-2217(98)00327-0 en_US
dc.identifier.ctation Easton, F. F., & Mansour, N. (1999). A distributed genetic algorithm for deterministic and stochastic labor scheduling problems. European Journal of Operational Research, 118(3), 505-523. en_US
dc.author.email nmansour@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0377221798003270 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account