HYBRID GENETIC ALGORITHMS FOR A ROSTERING PROBLEM

Hybrid Genetic Algorithms are described for a large-size real-life ros tering problem (railway workers' job scheduling and roster optimizatio n). The new algorithm uses an order-based representation which encodes as a chromosome the list of job units to schedule. First, a greedy al gorithm is considered, which uses a randomly generated job units list, and satisfies only the constraints pertaining to the workers' job con tract. Then, a genetic algorithm optimizes the global roster, minimizi ng its length and achieving some desired homogenizations. Finally, a s econd genetic algorithm (GA) is used to find the best parameter values for the first genetic algorithm. Thus, this work investigates the use of a GA together with a greedy algorithm and of a second GA to optimi ze the parameter values of the first GA. The results of significant te sts on real data are reported. They compare favourably with the known results on Rostering Problems, both in terms of execution time and sol ution accuracy. This work considers a practical Rostering Problem conc erning the Railway workers' rosters optimization. The size of the inpu t data is very challenging: about 1000 duties (i.e. job-units called ' links') based on a large-size city location; 125 days to consider for roster optimization (summer rostering); the goal is to optimize the st ructure of the working-turn for any worker, and to minimize the global cost of the rosters. It should be emphasised that this is a very larg e problem: we will use GAs to solve the problem within an execution ti me in the order of a few minutes on a common workstation.