On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
From MaRDI portal
Publication:3313599
DOI10.1287/opre.32.1.80zbMath0531.90048OpenAlexW2112230387MaRDI QIDQ3313599
Michael Sipser, Barbara B. Simons
Publication date: 1984
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.32.1.80
NP-completenesspolynomial timemaximum completion timefeasible schedulemultiple release time/deadline intervalsscheduling n unit-time jobssum of the completion times
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items (8)
Online scheduling of time-critical tasks to minimize the number of calibrations ⋮ Energy optimal schedules for jobs with multiple active intervals ⋮ The complexity of scheduling independent two-processor tasks on dedicated processors ⋮ Scheduling jobs on a single machine with periodic release date/deadline intervals ⋮ Parallel machine problems with equal processing times: a survey ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ Scheduling with a common due-window: polynomially solvable cases ⋮ Interval vertex-coloring of a graph with forbidden colors
This page was built for publication: On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
