Single Machine Scheduling with Series-Parallel Precedence Constraints

DOI10.1287/OPRE.29.6.1195MaRDI QIDQ3929382zbMATH OpenOpenAlexFDO

Authors R. N. Burns, George Steiner

Publication date 1981

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

acyclic digraphcompact labeling schemeefficient algorithmminimal total costseries-parallel graphsseries-parallel precedence constraintssingle machinetask sequencing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• On a parallel machine scheduling problem with precedence constraints
• scientific article; zbMATH DE number 4181112
• scientific article; zbMATH DE number 3894817

Cited in

(28)

• An algorithm for minimizing setups in precedence constrained scheduling
• A compact labelling scheme for series-parallel graphs
• \(P_ 4\)-trees and substitution decomposition
• Modular decomposition and transitive orientation
• Optimal timing of a sequence of tasks with general completion costs
• Review of properties of different precedence graphs for scheduling problems
• Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• Succinct representation of linear extensions via MDDs and its application to scheduling under precedence constraints
• Minimum equivalent precedence relation systems
• Schedules with precedence restrictions and position-dependent servicing durations
• Minimizing the number of grab's changes in a single machine scheduling problem
• scientific article; zbMATH DE number 4181112 (Why is no real title available?)
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• scientific article; zbMATH DE number 1305426 (Why is no real title available?)
• Structural and extremal properties of the hot rolling batches precedence graph
• Scheduling with AND/OR Precedence Constraints
• Handling precedence constraints in scheduling problems by the sequence pair representation
• scientific article; zbMATH DE number 3894817 (Why is no real title available?)
• Single-Machine Scheduling with Precedence Constraints
• Integer Programming and Combinatorial Optimization
• `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders
• Minimizing the total weighted duration of courses in a single machine problem with precedence constraints
• On a parallel machine scheduling problem with precedence constraints
• Parametric precedence relations in single machine scheduling
• On the complexity of dynamic programming for sequencing problems with precedence constraints

This page was built for publication: Single Machine Scheduling with Series-Parallel Precedence Constraints

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