Interval scheduling on related machines

DOI10.1016/j.cor.2011.03.001zbMath1215.90029OpenAlexW2094561371WikidataQ57851420 ScholiaQ57851420MaRDI QIDQ547142

Sven O. Krumke, Stephan Westphal, Clemens Thielen

Publication date: 30 June 2011

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.03.001

zbMATH Keywords

computational complexityschedulingcompetitive analysisonline algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (12)

Online Optimization of Busy Time on Parallel Machines ⋮ A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem ⋮ Fixed interval scheduling with third‐party machines ⋮ Online interval scheduling on two related machines: the power of lookahead ⋮ On-line scheduling of equal-length intervals on parallel machines ⋮ Online interval scheduling with a bounded number of failures ⋮ No-Wait Scheduling for Locks ⋮ Online optimization of busy time on parallel machines ⋮ Online C-benevolent job scheduling on multiple machines ⋮ Competitive algorithms for multistage online scheduling ⋮ Matching supply and demand in a sharing economy: classification, computational complexity, and application ⋮ Online scheduling of jobs with fixed start times on related machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Online interval scheduling: Randomized and multiprocessor cases
• Scheduling jobs with fixed start and end times
• Randomized online interval scheduling
• On-line scheduling of jobs with fixed start and end times
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• An improved randomized on-line algorithm for a weighted interval selection problem
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Improved Randomized Results for That Interval Selection Problem
• An optimal real-time algorithm for planar convex hulls
• Bounding the Power of Preemption in Randomized Scheduling

This page was built for publication: Interval scheduling on related machines