Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
From MaRDI portal
Publication:4181574
DOI10.1287/moor.2.3.275zbMath0397.90044OpenAlexW2040035940MaRDI QIDQ4181574
Peter Brucker, Michael R. Garey, David S. Johnson
Publication date: 1977
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.2.3.275
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of graph theory to circuits and networks (94C15)
Related Items
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Effective iterative algorithms in scheduling theory, A backward approach in list scheduling algorithms for multi-machine tardiness problems, On the Complexity of Scheduling to Optimize Average Response Time, UET scheduling with unit interprocessor communication delays, k-optimal solution sets for some polynomially solvable scheduling problems, A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile, Open shop problems with unit time operations, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Parallel machine problems with equal processing times: a survey, A state-of-the-art review of parallel-machine scheduling research, Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays, Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness, PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES, A metric approach for scheduling problems with minimizing the maximum penalty, Scheduling UET-UCT outforests to minimize maximum lateness, The worst-case analysis of the Garey-Johnson algorithm, Performance of critical path type algorithms for scheduling on parallel processors, Ideal schedules in parallel machine settings, The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints, Deadline scheduling of tasks with ready times and resource constraints, Preemptive scheduling with variable profile, precedence constraints and due dates, Scheduling with precedence constraints: Worst-case analysis of priority algorithms, NP-Complete operations research problems and approximation algorithms, Makespan minimization with OR-precedence constraints, On the complexity of coordinated display of multimedia objects, Scheduling Opposing Forests, Lower bounds on precedence-constrained scheduling for parallel processors., On scheduling cycle shops: Classification, complexity and approximation
