Lagrangian heuristics for instructor scheduling in executive development programmes

In this paper we present the problem of scheduling instructors in a university management development programme. Problems of similar structure arise in a number of scheduling applications like assigning officials to athletic competitions, inspectors to sites and maintenance crews to jobs. The problem is formulated as a zero–one linear integer program but is difficult to solve in real life situations because of problem size. The bounds on total assignments for different nested time periods give sub-problems that can be solved as network flow problems. Four Lagrangian relaxation heuristics are developed using different relaxations of the problem. Computational results are reported on 1350 random problems. In over 85% of these problems, the heuristics find solutions within 1% of the optimal. Heuristic performance is also analyzed in terms of average percent deviation from optimal, percent of times optimal solution is found and the cpu time. Computational results on two significantly larger real problems indicate that the heuristics are capable of solving real sized problems with tolerable deviations of around 4% from the optimal. An integrated strategy utilizing the strengths of the optimal and heuristic approaches is described for schedule generation and updating.