Three Essays on Operations Scheduling with Job Classes and Time Windows
27 November 2015
Operations scheduling is a prominent combinatorial optimization problem with many different applications in production management and service operations. Its goal is to assign jobs to resources and determine their order as efficiently as possible. Due to its high complexity it is usually solved heuristically, e.g., using priority rules. Sequence-dependent processing times and limited time windows further increase complexity. This thesis focuses, amongst others, on the “Aircraft Landing Problem”: A number of aircraft (i.e., jobs) approach an airport and have to be assigned to runways (i.e., resources) and landing times while considering the sequence-dependent separation requirements between two landings. Using mixed-integer programming, the problem is intractable even for small instances. Yet, by dividing jobs into classes with similar properties (e.g., aircraft of the same type), small instances can be solved to optimality efficiently using dynamic programming approaches. These approaches also serve as basis for heuristics to tackle large instances. Other applications for the proposed approaches are single-stage production scheduling problems with groups of similar jobs as well as task assignment problems with groups of similar tasks, e.g., in hospitals and nursing homes.