Hybrid Genetic Algorithms for a Rostering Problem

✍ Scribed by A. Monfroglio

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 676 KB
• Volume: 26
• Category: Article
• ISSN: 0038-0644
• DOI: 10.1002/(sici)1097-024x(199607)26:7<851::aid-spe38>3.0.co;2-a

✦ Synopsis

Hybrid Genetic Algorithms are described for a large-size real-life rostering problem (railway workers' job scheduling and roster optimization). The new algorithm uses an order-based representation which encodes as a chromosome the list of job units to schedule. First, a greedy algorithm is considered, which uses a randomly generated job units list, and satisfies only the constraints pertaining to the workers' job contract. Then, a genetic algorithm optimizes the global roster, minimizing its length and achieving some desired homogenizations. Finally, a second 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 optimize the parameter values of the first GA.

The results of significant tests on real data are reported. They compare favourably with the known results on Rostering Problems, both in terms of execution time and solution accuracy.

This work considers a practical Rostering Problem concerning the Railway workers' rosters optimization. The size of the input 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 structure 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 large problem: we will use GAS to solve the problem within an execution time in the order of a few minutes on a common workstation.