Abstract: Recent years have seen application of Linear programming techniques to solve problems in scheduling. One technique that has been applied very effectively to both online and offline scheduling problems is the Primal-Dual method. In this talk I will take two examples from our own research to illustrate some of the key ideas. The problems I will consider are:
- the online problem of minimizing flow time on unrelated machines
- the offline problem of minimizing weighted flow time on a single machine.
The talk will assume only basic familiarity with linear programming and duality.
