New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Using Techniques of Submodular Optimization for Solving Scheduling Problems with Controllable Processing times on Uniform Machines

SpeakerVitaly Strusevich

Co-author Akiyoshi Shioura, Tohoku University, Sendai, Japan and Natalia V. Shakhlevich, University of Leeds, U.K.

This talk reports on further efforts of our team to establish links between Submodular Optimization and Scheduling. In our previous work, we have reduced several scheduling problems with controllable processing times to linear programs over a submodular polyhedron intersected with a box. In turn, for these submodular optimisation problems, we have shown how to reformulate them in terms of optimizing the same function over a base polyhedron with an updated rank function and developed a decomposition algorithm for their solution. The purpose of this talk is to demonstrate how these techniques can be adapted to solving problems on uniform parallel machines, including problems of finding feasible schedules to minimize total compression costs and their bicriteria counterparts.