Review of properties of different precedence graphs for scheduling problems

DOI10.1016/S0377-2217(01)00379-4MaRDI QIDQ1847252zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Kobler, Jacek Blazewicz

Publication date 17 November 2002

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(01)00379-4

zbMATH Keywords

Graph theoryPrecedence constraintsScheduling

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 962288
• On a parallel machine scheduling problem with precedence constraints
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• scientific article; zbMATH DE number 4181112

Cites work

• A labeling algorithm to recognize a line digraph and output its root graph
• A linear-time recognition algorithm for interval dags
• A new polynomial-time algorithm for linear programming
• Algorithm 520: An Automatic Revised Simplex Method for Constrained Resource Network Scheduling [H]
• An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems
• Analysis of scheduling problems with typed task systems
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• scientific article; zbMATH DE number 3896963 (Why is no real title available?)
• scientific article; zbMATH DE number 3675952 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 1128827 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• scientific article; zbMATH DE number 3218572 (Why is no real title available?)
• Intransitive Indifference in Preference Theory: A Survey
• Minimizing the number of tardy jobs with precedence constraints and agreeable due dates
• On the linegraph of a directed-graph
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Preemptive scheduling of interval orders is polynomial
• Scheduling Interval-Ordered Tasks
• Scheduling subject to resource constraints: Classification and complexity
• The jump number problem on interval orders: A 3/2 approximation algorithm

Cited in

(15)

• Tree precedence in scheduling: The strong-weak distinction
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Scheduling chained multiprocessor tasks onto large multiprocessor system
• Parallel dedicated machines scheduling with chain precedence constraints
• Deep infeasibility exploration method for vehicle routing problems
• Minimum equivalent precedence relation systems
• Optimal preemptive scheduling on a fixed number of identical parallel machines
• A new formulation for scheduling unrelated processor under precedence constraints
• Structural and extremal properties of the hot rolling batches precedence graph
• scientific article; zbMATH DE number 1445309 (Why is no real title available?)
• Handling precedence constraints in scheduling problems by the sequence pair representation
• A Precedence Graph Algorithm for the Shop Scheduling Problem
• scientific article; zbMATH DE number 962288 (Why is no real title available?)
• Literature reviews in operations research: a new taxonomy and a meta review
• On a parallel machine scheduling problem with precedence constraints

Describes a project that uses

Uses Software

• Algorithm 520

This page was built for publication: Review of properties of different precedence graphs for scheduling problems

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