Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines

DOI10.1137/0210018zbMath0472.68021OpenAlexW2055849951MaRDI QIDQ3925879

Michael R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0210018

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (40)

Efficient scheduling algorithms for a single batch processing machine ⋮ Single machine scheduling with two competing agents, arbitrary release dates and unit processing times ⋮ Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan ⋮ One machine scheduling problem with fuzzy duedates ⋮ Effective iterative algorithms in scheduling theory ⋮ The feasibility of general task systems with precedence constraints on multiprocessor platforms ⋮ Scheduling Equal-Length Jobs with Delivery times on Identical Processors ⋮ Theoretical expectation versus practical performance of Jackson's heuristic ⋮ Parallel batch scheduling of equal-length jobs with release and due dates ⋮ Scheduling jobs of equal length: Complexity, facets and computational results ⋮ Arc-B-consistency of the inter-distance constraint ⋮ A note on scheduling equal-length jobs to maximize throughput ⋮ A procedure for the one-machine sequencing problem with dependent jobs ⋮ Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time ⋮ Algorithms for Necklace Maps ⋮ A study of single-machine scheduling problem to maximize throughput ⋮ Fast solution of single-machine scheduling problem with embedded jobs ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Preemptive scheduling of equal-length jobs in polynomial time ⋮ Security-aware database migration planning ⋮ Parallel machine problems with equal processing times: a survey ⋮ Dispersing points on intervals ⋮ Probabilistic single processor scheduling ⋮ Contiguous Cake Cutting: Hardness Results and Approximation Algorithms ⋮ Optimization of inland shipping. A polynomial time algorithm for the single-ship single-lock optimization problem ⋮ A note on ``Scheduling unit-time tasks with integer release times and deadlines ⋮ Runway sequencing with holding patterns ⋮ Feasibility analysis under fixed priority scheduling with limited preemptions ⋮ Jackson's semi-preemptive scheduling on a single machine ⋮ Ideal schedules in parallel machine settings ⋮ Throughput scheduling with equal additive laxity ⋮ Throughput scheduling with equal additive laxity ⋮ Theoretical and practical issues in single-machine scheduling with two job release and delivery times ⋮ Handling mixed sets of tasks in combined offline and online scheduled real-time systems ⋮ Scheduling equal-length jobs on identical parallel machines ⋮ Single machine scheduling subject to precedence delays ⋮ Scheduling unit-time tasks with integer release times and deadlines ⋮ Effective optimization methods for single-machine scheduling (survey) ⋮ New directions in scheduling theory ⋮ Interval edge coloring of a graph with forbidden colors

This page was built for publication: Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines