Decision diagrams for solving a job scheduling problem under precedence constraints

DOI10.4230/LIPIcs.SEA.2018.5zbMath1493.68037OpenAlexW2810078262MaRDI QIDQ5140712

Kohei Hatano, Kosuke Matsumoto, Eiji Takimoto

Publication date: 16 December 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.SEA.2018.5

zbMATH Keywords

schedulingpermutationprecedence constraintsNP-hardnessdecision diagramMDD

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05)

Cites Work

• Unnamed Item
• Zero-suppressed BDDs and their applications
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• On the Approximability of Single-Machine Scheduling with Precedence Constraints
• An Efficient Method for Indexing All Topological Orders of a Directed Graph
• πDD: A New Decision Diagram for Efficient Problem Solving in Permutation Space
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Graph-Based Algorithms for Boolean Function Manipulation
• Complexity of Scheduling under Precedence Constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Binary Decision Diagrams
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
• Multivalued Decision Diagrams for Sequencing Problems
• Single-Machine Scheduling with Precedence Constraints

This page was built for publication: Decision diagrams for solving a job scheduling problem under precedence constraints