Scheduling Resources of Varying Speed – The Power of Dual Schedules
In various computation and production environments we face scheduling problems in which the processing speed of resources may vary. We distinguish mainly two types of varying-speed scenarios: one in which the speed function is static and cannot be influenced, and another dynamic setting in which deciding upon the processor speed is part of the scheduling problem. In both cases, the task is to design cost-efficient scheduling algorithms for resources of varying speed. We focus on minimizing the total weighted completion time on a single machine and show how to compute nearly optimal solutions efficiently in the dynamic problem variant or when the static speed function is known. Assuming unreliable resources with unknown speed functions, we can construct a universal solution that obtains for any speed function a schedule of cost within a small factor of the optimal solution. It is somewhat surprising that such a universal solution always exists. Our results heavily rely on dual schedules, a re-interpretation of the problem within the well-known two dimensional Gantt charts.
About Nicole Megow:
After graduating with a Diploma in business mathematics in 2002, Nicole Megow received her Ph.D. at TU Berlin in 2006 for work on “Coping with Incomplete Information in Scheduling“. She was a research associate at the Max Planck Institute for Informatics in Saarbrücken from 2008-2012 and a guest professor at TU Darmstadt from 2011-12. Since 2012, she has been the head of an Emmy Noether Junior Research Group at TU Berlin. Her work has won several major awards, including the Dissertation Award by the German Operations Research Society (GOR), the Berlin Research Award by the Governing Mayor of Berlin, and the Heinz Maier-Leibnitz Prize by the German Research Foundation (DFG).