| The efficient scheduling of tasks on limited resources is important for many manufacturing and service industries to keep costs low and efficiently use resources. However, scheduling problems are often difficult and common scheduling approaches are inadequate for solving problems at the scale necessary for some applications. Therefore, customized scheduling methods are important for the practical application of scheduling techniques. The central thesis of this dissertation is that the understanding of the capabilities of current scheduling technologies and the use of this knowledge to partition a problem into smaller, more manageable parts that are better suited to these technologies is effective for increasing scheduling performance. These decompositions advance the state-of-the-art scheduling methodologies and extend the capabilities of automated scheduling techniques for real-world applications.;In this dissertation, three decompositions have been developed with varying levels of integration between solvers. Each decomposition addresses the limitations of a technology and improves upon the current techniques so that they can be used for specific application problems.;The first decomposition model is concerned with scheduling a team of robots in a retirement home. The scheduler must consider a complex, multi-objective problem, where it must respect user preferences and schedules. The problem is partitioned into two parts that are each solved using constraint programming. This decomposition shows the improvements that can be obtained when comparing a decomposed model and a non-decomposed model.;The second application studied is a large-scale data center. Here, jobs arrive dynamically and are processed on one of approximately 10,000 machines. The decomposition model makes use of techniques developed in two research areas: queueing theory and scheduling. By segmenting a problem into parts that are amenable to the techniques from queueing theory and scheduling, a state-of-the-art scheduling algorithm is crated.;Finally, the third decomposition model combines different paradigms of computation, quantum and classical computation, into a cohesive algorithm for use in three different scheduling problems. The hybrid classical computing and quantum computing algorithm develops the capabilities of quantum annealing, a quantum algorithm run on specialized quantum hardware. |
