Scheduling to minimize energy and flow time in broadcast scheduling

摘要

In this paper, we initiate the study of minimizing power consumption in the broadcast scheduling model. In this setting, there is a wireless transmitter. Over time requests arrive at the transmitter for pages of information. Multiple requests may be for the same page. When a page is transmitted, all requests for that page receive the transmission simultaneously. The speed the transmitter sends data at can be dynamically scaled to conserve energy. We consider the problem of minimizing flow time plus energy, the most popular scheduling metric considered in the standard online scheduling model when the scheduler is energy aware. We will assume that the power consumed is modeled by an arbitrary convex function. For this problem, there is an Ω (n) lower bound on the competitive ratio. Due to the lower bound, we consider using resource augmentation and give a scalable algorithm.