Premium
Solving a timetabling problem using hybrid genetic algorithms
Author(s) -
Kragelund Lars Vestergaard
Publication year - 1997
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(199710)27:10<1121::aid-spe119>3.0.co;2-j
Subject(s) - computer science , scheduling (production processes) , constraint satisfaction problem , operations research , mathematical optimization , genetic algorithm , service (business) , job shop scheduling , artificial intelligence , machine learning , mathematics , schedule , economy , probabilistic logic , economics , operating system
All over the world, human resources are used on all kinds of different scheduling problems, many of which are time‐consuming and tedious. Scheduling tools are thus very welcome. This paper presents a research project, where Genetic Algorithms (GAs) are used as the basis for solving a timetabling problem concerning medical doctors attached to an emergency service. All the doctors express personal preferences, thereby making the scheduling rather difficult. In its natural form, the timetabling problem for the emergency service is stated as a number of constraints to be fulfilled. For this reason, it was decided to compare the strength of a Co‐evolutionary Constraint Satisfaction (CCS) technique with that of two other GA approaches. Distributed GAs and a simple special‐purpose hill climber were introduced, to improve the performance of the three algorithms. Finally, the performance of the GAs was compared with that of some standard, nonGA approaches. The distributed hybrid GAs were by far the most successful, and one of these hybrid algorithms is currently used for solving the timetabling problem at the emergency service. © 1997 John Wiley & Sons, Ltd.