Hybridising GRASP and network flows in the solution of a medical school scheduling problem

Hybridising GRASP and network flows in the solution of a medical school scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20126650
Volume: 15
Issue: 6
Start Page Number: 717
End Page Number: 731
Publication Date: Dec 2012
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, combinatorial optimization, heuristics, heuristics: local search, networks: flow
Abstract:

This paper tackles the problem of allocating medical students to clinical specialities over a number of time periods. Each speciality is offered by a number of consultant led ‘firms’ and the objective is to optimise the schedule in terms of ensuring a broad range of experience for each student, whilst ensuring that every student covers every speciality exactly once without exceeding the number of places available in each firm. The balance between feasibility and optimality is a key issue. We develop a family of GRASP heuristics for the problem, all based on the same local search heuristic, but using a variety of constructions. These use different building blocks, different score functions, and different ways of balancing feasibility and optimality. Empirical tests show that the best heuristic, based on large building blocks facilitated by the use of a network flow model, and enhanced by feedback in the form of partial reconstructions, performs extremely well on real data, and is able to produce acceptable solutions on more challenging artificial problem instances.

Reviews

Required fields are marked *. Your email address will not be published.