Volltext-Downloads (blau) und Frontdoor-Views (grau)

A new LP rounding algorithm for the active time problem

  • In this paper, we work on the scheduling problem with active time model. We have a set of preemptive jobs with integral release times, deadlines and required processing lengths, while the preemption of jobs is only allowed at integral time points. We have a single machine that can process at most g distinct job units at any given time unit when the machine is switched on. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the time when the machine is on, i.e., the active time. This problem has been studied by Chang et al. where they proposed an LP rounding approach which gives a 2-approximation solution. In this paper, we also give a 2-approximation algorithm based on LP rounding approach with a different rounding technique and analysis. Finally, we give a new linear programming formulation for which we conjecture that the integrality gap is 5/3, which might bring new hope for beating the barrier of 2 for the approximation ratio.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Gruia Cǎlinescu, Kai WangORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):Journal of Scheduling
Year of Completion:2021
First Page:543
Last Page:552
Tag:Active time; Approximation algorithm; Linear program rounding; Scheduling
Content Focus:Academic Audience
Peer Reviewed:Yes
Licence (German):License LogoUrheberrechtlich geschützt