Scheduling with gaps: new models and algorithms

DOI10.1007/978-3-319-18173-8_8MaRDI QIDQ2947014zbMATH OpenOpenAlexWikidataFDO

Authors Dorian Nogneng, Marek Chrobak, Mordecai J. Golin, Tak-Wah Lam

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.7092

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Abstract: We consider scheduling problems for unit jobs with release times, where the number or size of the gaps in the schedule is taken into consideration, either in the objective function or as a constraint. Except for a few papers on energy minimization, there is no work in the scheduling literature that uses performance metrics depending on the gap structure of a schedule. One of our objectives is to initiate the study of such scheduling problems with gaps. We show that such problems often lead to interesting algorithmic problems, with connections to other areas of algorithmics. We focus on the model with unit jobs. First we examine scheduling problems with deadlines, where we consider variants of minimum-gap scheduling, including maximizing throughput with a budget for gaps or minimizing the number of gaps with a throughput requirement. We then turn to other objective functions. For example, in some scenarios, gaps in a schedule may be actually desirable, leading to the problem of maximizing the number of gaps. Other versions we study include minimizing maximum gap or maximizing minimum gap. The second part of the paper examines the model without deadlines, where we focus on the tradeoff between the number of gaps and the total or maximum flow time. For all these problems we provide polynomial time algorithms, with running times ranging from $O(nlogn)$ for some problems, to $O(n^7)$ for other. The solutions involve a spectrum of algorithmic techniques, including different dynamic programming formulations, speed-up techniques based on searching Monge arrays, searching X + Y matrices, or implicit binary search.

Recommendations

• Scheduling with gaps: new models and algorithms
• A greedy approximation algorithm for minimum-gap scheduling
• A greedy approximation algorithm for minimum-gap scheduling
• Scheduling to minimize gaps and power consumption
• The geometry of scheduling

Cites work

• A greedy approximation algorithm for minimum-gap scheduling
• Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines
• Monge strikes again: Optimal placement of web proxies in the internet
• Polynomial Time Algorithms for Minimum Energy Scheduling
• Scheduling to minimize gaps and power consumption
• Scheduling unit tasks to minimize the number of idle periods
• Scheduling with gaps: new models and algorithms
• Selection in \(X+Y\) and matrices with sorted rows and columns

Cited in

(7)

• Scheduling with gaps: new models and algorithms
• Scheduling to minimize gaps and power consumption
• Maximizing dominance in the plane and its applications
• Refined algorithms for hitting many intervals
• Scheduling with gaps: new models and algorithms
• A greedy approximation algorithm for minimum-gap scheduling
• A greedy approximation algorithm for minimum-gap scheduling

This page was built for publication: Scheduling with gaps: new models and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947014)