Scheduling with gaps: new models and algorithms

DOI10.1007/978-3-319-18173-8_8zbMATH Open1394.90268arXiv1410.7092OpenAlexW1564611115WikidataQ58062875 ScholiaQ58062875MaRDI QIDQ2947014FDOQ2947014

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines
• Scheduling with Gaps: New Models and Algorithms
• Polynomial Time Algorithms for Minimum Energy Scheduling
• Scheduling unit tasks to minimize the number of idle periods
• Monge strikes again: Optimal placement of web proxies in the internet
• Scheduling to minimize gaps and power consumption
• Selection in \(X+Y\) and matrices with sorted rows and columns
• A Greedy Approximation Algorithm for Minimum-Gap Scheduling

Cited In (3)

• Scheduling with Gaps: New Models and Algorithms
• Maximizing dominance in the plane and its applications
• Refined algorithms for hitting many intervals

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)