Profit margin oriented course scheduling at Lufthansa Technical Training Ltd

Lufthansa Technical Training Ltd. (LTT) offers about 670 different types of training courses for the technical staff of Lufthansa AG and several other international airlines. 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. We formalize the problem as knapsack model and sketch a heuristic scheme along with a composite priority rule. We describe a local search method to determine well-suited weights for the weighted composite rule. The operational planning situation of 1996 served as our test instance. It turned out that the best schedule computed by the proposed method is substantially better in terms of the profit margin incurred than the solution manually constructed by LTT.