Mixed-Integer Programming Modeling Strategies for Scheduling-Based Optimization Problems

We provide a tutorial treatment of basic techniques for modeling scheduling optimization problems as mixed-integer linear programs, presented for readers having at least a limited background in linear programming formulations and algorithms for solving mathematical optimization problems. Although the scope of scheduling applications is far too broad to cover with a single chapter, many scheduling formulations employ a common set of modeling strategies that can be directly used, modified, or combined to formulate novel scheduling problems. We briefly cover these fundamental scheduling principles and illustrate how they can be adapted to model several modern applications arising in the field of scheduling optimization. These applications include optimizing radar pulse interleaving, identifying schedules that are robust to changes in data, and scheduling path flows in a dynamic flow optimization problem.