Interval scheduling on related machines

DOI10.1016/J.COR.2011.03.001MaRDI QIDQ547142zbMATH OpenOpenAlexWikidataFDO

Authors Sven O. Krumke, Clemens Thielen, Stephan Westphal

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 complexityonline algorithmscompetitive analysisscheduling

Mathematics Subject Classification ID

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

Recommendations

• Online splitting interval scheduling on \(m\) identical machines
• scientific article; zbMATH DE number 1003261
• On-line scheduling of equal-length intervals on parallel machines
• Interval selection with machine-dependent intervals
• Online interval scheduling with a bounded number of failures

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• An improved randomized on-line algorithm for a weighted interval selection problem
• An optimal real-time algorithm for planar convex hulls
• Bounding the Power of Preemption in Randomized Scheduling
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Improved Randomized Results for That Interval Selection Problem
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• On-line scheduling of jobs with fixed start and end times
• Online interval scheduling: Randomized and multiprocessor cases
• Randomized online interval scheduling
• Scheduling jobs with fixed start and end times

Cited in

(23)

• Online scheduling of jobs with fixed start times on related machines
• Online interval scheduling on two related machines: the power of lookahead
• Interval scheduling on identical machines
• On-line scheduling of equal-length intervals on parallel machines
• On the parameterized complexity of interval scheduling with eligible machine sets
• Matching supply and demand in a sharing economy: classification, computational complexity, and application
• Online C-benevolent job scheduling on multiple machines
• Online interval scheduling to maximize total satisfaction
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• Competitive algorithms for multistage online scheduling
• No-wait scheduling for locks
• Approximating interval selection on unrelated machines with unit-length intervals and cores
• Fixed interval scheduling with third‐party machines
• Bag-Of-Tasks Scheduling on Related Machines
• Computing and Combinatorics
• Online optimization of busy time on parallel machines
• Interval selection with machine-dependent intervals
• Online splitting interval scheduling on \(m\) identical machines
• Online optimization of busy time on parallel machines. (Extended abstract)
• Online interval scheduling with a bounded number of failures
• Online Interval Scheduling to Maximize Total Satisfaction
• A triplet-based exact method for the shift minimisation personnel task scheduling problem
• Interval scheduling maximizing minimum coverage

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

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