Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines

DOI10.1137/0210018zbMATH Open0472.68021OpenAlexW2055849951MaRDI QIDQ3925879FDOQ3925879

Authors: M. R. Garey, D. S. Johnson, Barbara B. Simons, Robert E. 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)

Cited In (40)

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

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

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