We are delighted to announce the talk given by Maurice Queyranne (Sauder
School, UBC).
The title is "On Polyhedral Approaches to Scheduling Problems".
The seminar will take place on Zoom on Wednesday, June 22 at 13:00 UTC.
Join Zoom Meeting
https://cesnet.zoom.us/j/91083429684?pwd=QlJXcHB4dGtLdE40b1hGaEVMbTNFdz09
Meeting ID: 910 8342 9684
Passcode: 190280
You can follow the seminar online or offline on our Youtube channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
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.
The next talk in our series will be in September.
For more details, please visit https://schedulingseminar.com/
With kind regards
Zdenek, Mike and Guohua
--
Zdenek Hanzalek
Industrial Informatics Department,
Czech Institute of Informatics, Robotics and Cybernetics,
Czech Technical University in Prague,
Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic
https://rtime.ciirc.cvut.cz/~hanzalek/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
