Energy-efficient due date scheduling

Abstract

This paper considers several online scheduling problems that arise from companies with made-to-order products. Jobs, which are product requests, arrive online with different sizes and weights. A company needs to assign a due date for each job once it arrives, and complete the job by this due date. The (weighted) quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We focus on companies that mainly rely on computers for production. In those companies, energy cost is a large concern. For most modern processors, its rate of energy usage equals sα, where s is the current speed and α > 1 is a constant. Hence, reducing the processing speed can reduce the rate of energy usage. Algorithms are needed to optimize the (weighted) quoted lead time (for better user experience) and the energy usage (for a smaller energy cost). We propose an algorithm which is 4((log k)α-1 + -α/α-1)-competitive for minimizing the sum of the quoted lead time and energy usage, where k is the ratio between the maximum to minimum job density. Here, the density of a job equals its weight divided by its size. We also consider the setting where we may discard a job by paying a penalty, and the setting of scheduling on a multiprocessor. We propose competitive algorithms for both settings. © 2011 Springer-Verlag.