Complexity of Scheduling under Precedence Constraints

DOI10.1287/opre.26.1.22zbMath0371.90060OpenAlexW2150446509MaRDI QIDQ4147824

Alexander H. G. Rinnooy Kan, Jan Karel Lenstra

Publication date: 1978

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.26.1.22

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Equitable scheduling on a single machine, Resource-constrained multi-project scheduling problem: a survey, Minimizing the total weighted duration of courses in a single machine problem with precedence constraints, Server cloud scheduling, Tree scheduling with communication delays, Profile Scheduling of Opposing Forests and Level Orders, Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors, A compact labelling scheme for series-parallel graphs, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Analysis of scheduling problems with typed task systems, Applications of scheduling theory to formal language theory, Single machine scheduling problems with uncertain parameters and the OWA criterion, Scheduling of machines and automated guided vehicles in FMS using differential evolution, Scheduling with constrained processor allocation for interval orders, The three-machine flow-shop problem with arbitrary precedence relations, Three, four, five, six, or the complexity of scheduling with communication delays, Stochastic scheduling and forwards induction, On the Complexity of Scheduling to Optimize Average Response Time, Two level heuristic for the resource constrained scheduling problem, Approximability of single machine scheduling with fixed jobs to minimize total completion time, Pareto optimal matchings of students to courses in the presence of prerequisites, Time complexity of single machine scheduling with stochastic precedence constraints, Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness, On a parallel machine scheduling problem with precedence constraints, An experiment in scheduling and planning of non-structured jobs: Lessons learned from artificial intelligence and operational research toolbox, The pairwise flowtime network construction problem, Algorithms for the multiperiod workforce scheduling and routing problem with dependent tasks, Open shop problems with unit time operations, Complexity results for scheduling chains on a single machine, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Scheduling malleable tasks with precedence constraints, Scheduling loosely connected task graphs., GPU implementation of a cellular genetic algorithm for scheduling dependent tasks of physical system simulation programs, Discrete optimization with polynomially detectable boundaries and restricted level sets, On the approximability of average completion time scheduling under precedence constraints., Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Parallel machine problems with equal processing times: a survey, A complete 4-parametric complexity classification of short shop scheduling problems, Revisiting multiple pattern matching algorithms for multi-core architecture, Homogeneously non-idling schedules of unit-time jobs on identical parallel machines, Unnamed Item, On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems, On the complexity of generalized due date scheduling problems, Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time, Approximating Weighted Completion Time for Order Scheduling with Setup Times, Quasi-PTAS for scheduling with precedences using LP hierarchies, On scheduling with the non-idling constraint, Performance of Garey-Johnson algorithm for pipelined typed tasks systems, A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Time-critical testing and search problems, Vertex Cover in Graphs with Locally Few Colors, Stochastic scheduling in an in-forest, Single-machine scheduling with supporting tasks, Bi-criteria Pareto-scheduling on a single machine with due indices and precedence constraints, Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal, A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations, APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS, An EPTAS for scheduling fork-join graphs with communication delay, PARAdeg-processor scheduling for acyclic SWITCH-less program nets, Scheduling partially ordered jobs faster than \(2^n\), Scheduling with bully selfish jobs, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, Scheduling \(UET\)-tasks on a star network: complexity and approximation, Complexity of two coloring problems in cubic planar bipartite mixed graphs, On scheduling with the non-idling constraint, The complexity of machine scheduling for stability with a single disrupted job, The worst-case analysis of the Garey-Johnson algorithm, Scheduling tasks with exponential duration on unrelated parallel machines, APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS, Simultaneous job input sequencing and vehicle dispatching in a single-vehicle automated guided vehicle system: a heuristic branch-and-bound approach coupled with a discrete events simulation model, Ideal schedules in parallel machine settings, Machine scheduling with soft precedence constraints, Improving local search heuristics for some scheduling problems. II, Facets of the generalized permutahedron of a poset, Four solution techniques for a general one machine scheduling problem. A comparative study, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Polyhedral results for position-based scheduling of chains on a single machine, Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates, Unnamed Item, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Open-shop scheduling for unit jobs under precedence constraints, Single machine precedence constrained scheduling is a Vertex cover problem, Optimal and heuristic solution methods for a multiprocessor machine scheduling problem, NP-Complete operations research problems and approximation algorithms, Makespan minimization with OR-precedence constraints, An improved approximation algorithm for scheduling under arborescence precedence constraints, Complete Complexity Classification of Short Shop Scheduling, Minimizing setups in ordered sets of fixed width, On the complexity of scheduling with large communication delays, Online Linear Optimization for Job Scheduling Under Precedence Constraints, A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles, Scheduling three chains on two parallel machines, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, Server cloud scheduling, Minimizing Setups for Ordered Sets: A Linear Algebraic Approach, Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems, Local search procedures for improving feasible solutions to the sequential ordering problem, On scheduling cycle shops: Classification, complexity and approximation, A comparative study of computational procedures for the resource constrained project scheduling problem, Decision diagrams for solving a job scheduling problem under precedence constraints, On the complexity of scheduling unit-time jobs with or-precedence constraints, Complexity of the scheduling language RSV, A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications