A distributed genetic algorithm for deterministic and stochastic labor scheduling problems
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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | article |
| منشور في: |
1999
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/4881 http://dx.doi.org/10.1016/S0377-2217(98)00327-0 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0377221798003270 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513464671666176 |
|---|---|
| author | Mansour, Nashat |
| author2 | Easton, Fred F. |
| author2_role | author |
| author_facet | Mansour, Nashat Easton, Fred F. |
| author_role | author |
| dc.creator.none.fl_str_mv | Mansour, Nashat Easton, Fred F. |
| dc.date.none.fl_str_mv | 1999 2016-12-06T09:35:42Z 2016-12-06T09:35:42Z 2016-12-06 |
| dc.identifier.none.fl_str_mv | 0377-2217 http://hdl.handle.net/10725/4881 http://dx.doi.org/10.1016/S0377-2217(98)00327-0 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. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0377221798003270 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | European Journal of Operational Research |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_0249798c9fbbc4fe1d98873258bae921 |
| identifier_str_mv | 0377-2217 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/4881 |
| publishDate | 1999 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A distributed genetic algorithm for deterministic and stochastic labor scheduling problemsMansour, NashatEaston, Fred F.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.PublishedN/A2016-12-06T09:35:42Z2016-12-06T09:35:42Z19992016-12-06Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0377-2217http://hdl.handle.net/10725/4881http://dx.doi.org/10.1016/S0377-2217(98)00327-0Easton, 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.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://www.sciencedirect.com/science/article/pii/S0377221798003270enEuropean Journal of Operational Researchinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/48812021-03-19T10:03:22Z |
| spellingShingle | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems Mansour, Nashat |
| status_str | publishedVersion |
| title | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| title_full | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| title_fullStr | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| title_full_unstemmed | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| title_short | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| title_sort | A distributed genetic algorithm for deterministic and stochastic labor scheduling problems |
| url | http://hdl.handle.net/10725/4881 http://dx.doi.org/10.1016/S0377-2217(98)00327-0 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0377221798003270 |