Course planning at Lufthansa technical training: Constructing more profitable schedules

Lufthansa Technical Training GmbH (LIT) performs training courses for Lufthansa AG as well as for several other international airlines. Courses of about 670 different types are offered of which several hundred take place each year. The course scheduling problem faced by LTT is to develop a yearly schedule which maximizes the profit margin incurred while meeting a variety of complex precedence, temporal, and resource-related constraints. A "good" operational schedule should also meet a number of additional subordinate objectives. In the past, scheduling was solely done manually. We describe the problem and survey the process of developing a prototype course scheduling module. The operational planning Situation of 1996 served as our major test instance; it turned out that the best so-found schedule is substantially better than the Solution manually constructed by LTT, measured in terms of profit margin incurred as well as computation time required. Details on the subsequently developed fully-fledged decision support system are also provided.