Scheduling Tasks with Nonuniform Deadlines on Two Processors

DOI10.1145/321958.321967zbMath0338.68048OpenAlexW1976306508MaRDI QIDQ4105798

Michael R. Garey, David S. Johnson

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321958.321967

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Effective iterative algorithms in scheduling theory, On the Complexity of Scheduling to Optimize Average Response Time, k-optimal solution sets for some polynomially solvable scheduling problems, A survey of single machine scheduling to minimize weighted number of tardy jobs, Open shop problems with unit time operations, Scheduling UET-UCT tasks: Branch-and-bound search in the priority space, Complexity results for scheduling chains on a single machine, An iterative algorithm for scheduling UET tasks with due dates and release times., Solving the resource constrained deadline scheduling problem via reduction to the network flow problem, Discrete optimization with polynomially detectable boundaries and restricted level sets, Normal-form preemption sequences for an open problem in scheduling theory, A state-of-the-art review of parallel-machine scheduling research, An efficient parallel algorithm for scheduling interval ordered tasks, Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays, A model for minimizing active processor time, Performance of Garey-Johnson algorithm for pipelined typed tasks systems, Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness, PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES, Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal, Minimizing the number of tardy jobs in single machine sequencing, Scheduling UET-UCT outforests to minimize maximum lateness, Performance of critical path type algorithms for scheduling on parallel processors, Minimizing the number of tardy jobs with precedence constraints and agreeable due dates, Simple algorithms for multiprocessor scheduling to meet deadlines, Deadline scheduling of tasks with ready times and resource constraints, NP-Complete operations research problems and approximation algorithms, Inhomogeneous graph sorting and job distribution between two processors, An efficient algorithm for finding ideal schedules, Approximation scheduling algorithms: a survey, Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost, Scheduling Opposing Forests, On the complexity of scheduling unit-time jobs with or-precedence constraints, Scheduling multiprocessor tasks on two parallel processors