LAGRANGIAN HEURISTICS FOR INSTRUCTOR SCHEDULING IN EXECUTIVE-DEVELOPMENT PROGRAMS

In this paper we present the problem of scheduling instructors in a un iversity management development programme. Problems of similar structu re arise in a number of scheduling applications like assigning officia ls to athletic competitions, inspectors to sites and maintenance crews to jobs. The problem is formulated as a zero-one linear integer progr amme but is difficult to solve in real life situations because of prob lem size. The bounds on total assignments for different nested time pe riods give sub-problems that can be solved as network flow problems. F our Lagrangian relaxation heuristics are developed using different rel axations of the problem. Computational results are reported on 1350 ra ndom problems. In over 85% of these problems, the heuristics find solu tions 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 t wo significantly larger real problems indicate that the heuristics are capable of solving real sized problems with tolerable deviations of a round 4% from the optimal. An integrated strategy utilizing the streng ths of the optimal and heuristic approaches is described for schedule generation and updating.