On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

DOI10.1287/OPRE.32.1.80MaRDI QIDQ3313599zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

feasible schedulemaximum completion timemultiple release time/deadline intervalsNP-completenesspolynomial timescheduling n unit-time jobssum of the completion times

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling jobs on a single machine with periodic release date/deadline intervals
• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• An NC Algorithm for Scheduling Unit-Time Jobs with Arbitrary Release Times and Deadlines
• scientific article; zbMATH DE number 1187294

Cited in

(16)

• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling jobs on a single machine with periodic release date/deadline intervals
• Some results concerning the complexity of restricted colorings of graphs
• Scheduling jobs with release times on a machine with finite storage
• Interval vertex-coloring of a graph with forbidden colors
• Job release scheduling problem: complexity and an approximation algorithm
• Scheduling jobs with release and delivery times subject to nested eligibility constraints
• Online scheduling of time-critical tasks to minimize the number of calibrations
• Scheduling with a common due-window: polynomially solvable cases
• Parallel machine problems with equal processing times: a survey
• Scheduling Unit Jobs with a Common Deadline to Minimize the Sum of Weighted Completion Times and Rejection Penalties
• Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines
• An NC Algorithm for Scheduling Unit-Time Jobs with Arbitrary Release Times and Deadlines
• A note on ``Scheduling unit-time tasks with integer release times and deadlines
• Scheduling jobs to minimize a convex function of resource usage
• Energy optimal schedules for jobs with multiple active intervals

This page was built for publication: On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

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