Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Finding total unimodularity in optimization problems solved by linear programs

SpeakerMathilde Hurand

Co-authorChristophe Dürr

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with same cost from the fractional solution. Examples are two scheduling problems [1,2] and the single disk prefetching/caching problem [3].

We show that problems such as the three previously mentioned can be separated into two subproblems:

  1. finding an optimal feasible set of slots, and
  2. assigning the jobs or pages to the slots.

It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, which provides simpler (and sometimes combinatorial) algorithms with better worst case running times.

[1]
Baptiste and B. Schieber. A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. J. Sched., 6(4):395-404, 2003.
[2]
P. Brucker and S.A. Kravchenko. Scheduling jobs with equal processing times and time windows on identical parallel machines.
[3]
S. Albers, N. Garg, and S. Leonardi. Minimizing stall time in single and parallel disk systems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 454--462, New York, May 23--26 1998. ACM Press.