Scheduling

The management of transportation and production systems often requires solving a sequence of optimization problems, each problem optimizing the utilization of some resources: equipment, personnel, etc. For instance, transit authorities perform bus scheduling followed by daily and monthly driver scheduling; airlines perform aircraft scheduling followed by crew pairing and monthly crew scheduling; and manufacturing companies address manpower scheduling before production scheduling. Such a sequential approach for management was introduced a long time ago when solutions were computed manually.

Algorithms for solving difficult computational problems play a key role in many applications, including scheduling, resource allocation, computer-aided design, and software verification. In many cases, heuristic methods are the key to solving these problems effectively. However, the design of effective heuristic algorithms, particularly algorithms for solving computationally hard problems, is a difficult task that requires considerable expertise.