The objective of this research is to study the difficult (i.e. NP-hard) machine scheduling problems, using mathematical programming approaches. This study will focus on the following four classes of scheduling problems: (1) scheduling with precedence constraints, (2) scheduling with incomplete information, (3) scheduling parallel jobs, and (4) scheduling in shop environments. The theory of mathematical programming will be used as a tool to establish lower bounds on the cost of optimal schedules, to develop insight on the structure of optimal and near-optimal schedules, and to aid in the design of efficient (i.e. polynomial-time) algorithms that produce schedules that are guaranteed to be reasonably close to optimal. In the process, novel mathematical programming formulations for these problems will be developed. The results of this research will be disseminated in a series of book chapters, and in a new course in scheduling designed for doctoral students in computer science and operations research.
The primary goal of this research is to gain a better theoretical understanding of the four aforementioned classes of scheduling problems, both structurally and algorithmically. Success in achieving these goals has some anticipated side benefits. Any new structural or algorithmic ideas, as well as any new mathematical programming formulations developed in this research may lead to better heuristics for related, but more complex, practical scheduling problems. In particular, good lower bounds are critical to the performance of algorithmic schemes such as cutting plane, branch-and-bound, and branch-and-cut methods. In addition, any new mathematical proof techniques pioneered in this work may be useful more generally, for advancing the theory of various other combinatorial optimization problems.
