[Scheduling seminar] Maurice Queyranne (Sauder School, UBC) | On Polyhedral Approaches to Sched...

Keywords: Scheduling, Polyhedra, Formulations The formulation of scheduling problems as mathematical optimization problems is a useful step in deriving exact solutions, or approximate solutions with performance guarantees. We give a brief overview of polyhedral approaches, which aim to apply the power of linear and mixed-integer optimization to certain classes of scheduling problems, in particular those with min-sum type of objectives such as to minimize weighted sums of completion dates. The choice of decision variables is the prime determinant of such formulations. Constraints, such as facet inducing inequalities for corresponding polyhedra, are often needed, in addition to those just required for the validity of the initial formulation, in order to derive useful dual bounds and structural insights. Alternative formulations are based on various types of decision variables, such as: start date and completion date variables, that simply specify when a task is performed; linear ordering variables, that prescribe the relative order of pairs of tasks; traveling salesman variables, which capture immediate succession of tasks and changeovers; assignment and positional date variables, which specify the assignment of tasks to machine or to positions; and time-indexed variables which rely on a discretization of the planning horizon, in particular machine switch-on and switch-off variables in production planning and unit commitment in power generation. We point out relationship between various models, and emphasize the role of supermodular polyhedra and greedy algorithms. Organized by Zdenek Hanzalek (CTU in Prague), Michael Pinedo (New York University), and Guohua Wan (Shanghai Jiao Tong). Seminar's webpage: https://schedulingseminar.com/