Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

June 2022

1 participants
2 discussions

[Scheduling seminar] Maurice Queyranne (Sauder School, UBC)| June 22 | On Polyhedral Approaches to Scheduling Problems
by Zdeněk Hanzálek 20 Jun '22

20 Jun '22

Dear scheduling researcher, 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/

1 0

Nicole Megow (Universität Bremen) | June 8 | Learning-Augmented Online Algorithms for Scheduling and Routing
by Zdeněk Hanzálek 06 Jun '22

06 Jun '22

Dear scheduling researcher, We are delighted to announce the talk given by Nicole Megow (Universität Bremen). The title is "Learning-Augmented Online Algorithms for Scheduling and Routing". The seminar will take place on Zoom on Wednesday, June 8 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/93281103550?pwd=ckU0dWRRYWFUb2tRV2duakRjMVgyZz09 Meeting ID: 932 8110 3550 Passcode: 197150 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions, as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss different prediction models and algorithmic challenges with a focus on online scheduling and routing and give an outlook to network design problems. The next talk in our series will be given by: Maurice Queyranne (Sauder School, UBC)| June 22 | On Polyhedral Approaches to Scheduling Problems 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/

1 0