Loading…

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

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, whil...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2012-12, Vol.15 (6), p.717-731
Main Authors: Goodman, Melissa D., Dowsland, Kathryn A., Thompson, Jonathan M.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-012-0289-6