「最適モデリング」セミナー案内 (11/13)

「最適モデリング」セミナー案内 (11/13)

日時: 2019年11月13日(水) 16:00~17:00
場所: 東京大学工学部 14号館 5階 534号室
https://www.u-tokyo.ac.jp/campusmap/cam01_04_15_j.html

講演者: S. Thomas McCormick (UBC)

講演題目: Separation of Series Constraints for One-Machine Scheduling with Precedence

共同研究者: A. Ridha Mahjoub, Y. Kobayashi

講演概要:
A 1991 paper by Queyranne and Wang proposed three classes of valid
constraints for the convex hull of feasible completion times for
schedules on a single machine subject to precedence constraints. These
classes are called the parallel constraints, serial constraints, and Z
constraints. These constraints have been very useful in many contexts.
Queyranne and Wang showed how to separate the parallel constraints, but
the complexity of separating the serial and Z constraints has remained
open. Here we show that it is NP Hard to separate even a very special
subclass of serial constraints.  We also develop a fast, parametric way
to find an earliest feasible deadline for a subset of jobs, and use it
to show that separation is polynomial when the precedence constraints
are series-parallel.  We also note that there is a compact extended
formulation of the problem by Wolsey, and in this context separation of
both series and parallel constraints becomes trivial.  It is surprising
that an NP Hard separation problem can “hide” within an extended
formulation where separation is much easier.  We further consider the
case of two-dimensional precedence constraints, whose underlying problem
is solvable in polynomial time.  We show how to separate the serial
constraints in this case as well.