Description:
Several well-known and well-researched problem fields, such as school scheduling or university scheduling, reside in the realm of educational scheduling. Recently, some new course scheduling problems have begun to draw attention, which turn out to sport substantially more complex requirements and objectives than the classical course scheduling problems. We refer to their problem field as professional course scheduling. In order to demonstrate its practical relevance, we describe a real-world application. Lufthansa Flight Training GmbH (LFT) offers license, recurrency, emergency, and human factors training for airline, navy, and air force pilots as well as service and emergency training for cabin attendants of more than 50 airlines worldwide. This charges LFT with the problem to develop a monthly schedule for courses, instructors, and rooms that optimizes an objective function measuring adherence to seven different soft constraints while meeting a number of complex precedence, temporal, and resource-related constraints. In the past, LFT did all its scheduling manually, but management was dissatisfied with this process due to the significant cost and time involved. LFT commissioned us to carry out a feasibility study in which the applicability of operations research methods was to be demonstrated. We developed a prototype decision support system which utilizes construction and neighborhood search methods based upon concepts from project scheduling and graph theory. It turned out that significant improvements over the manual process could be realized; in addition, the algorithmic ideas employed are general enough to be easily adapted to other problems in the field of professional course scheduling. The development of a full-fledged decision support system is currently in progress at LFT.