Scheduling with gaps: new models and algorithms

DOI10.1007/s10951-021-00691-wzbMath1479.90083OpenAlexW3186047907MaRDI QIDQ2059088

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

Publication date: 13 December 2021

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-021-00691-w

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Refined algorithms for hitting many intervals
• Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Geometric applications of a matrix-searching algorithm
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Improved complexity bounds for location problems on the real line
• Monge strikes again: Optimal placement of web proxies in the internet
• Perspectives of Monge properties in optimization
• A greedy approximation algorithm for minimum-gap scheduling
• Scheduling to minimize gaps and power consumption
• Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines
• Polynomial-time algorithms for minimum energy scheduling
• Generalized Selection and Ranking: Sorted Matrices
• Polynomial Time Algorithms for Minimum Energy Scheduling
• Scheduling unit tasks to minimize the number of idle periods
• New Results on the Complexity of p-Centre Problems
• The disjoint cliques problem
• A Greedy Approximation Algorithm for Minimum-Gap Scheduling
• A Dynamic Programming Approach to Length-Limited Huffman Coding: Space Reduction With the Monge Property

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