Optimal Sequencing by Modular Decomposition: Polynomial Algorithms

DOI10.1287/OPRE.34.4.606MaRDI QIDQ3750504zbMATH OpenOpenAlexFDO

Authors Jeffrey B. Sidney, George Steiner

Publication date 1986

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

polynomial timeprecedence constraintssequencingpartial-order decomposition algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Recommendations

• Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
• Sequencing with ordered criteria, precedence and group technology constraints
• scientific article; zbMATH DE number 176473
• Algorithms for Scheduling Independent Tasks
• On the complexity of dynamic programming for sequencing problems with precedence constraints

Cited in

(25)

• Scheduling problems with partially ordered jobs
• On Submodular Search and Machine Scheduling
• A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem
• scientific article; zbMATH DE number 3987032 (Why is no real title available?)
• Finding the largest suborder of fixed width
• Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
• Computing the optimal IO sequences of a protocol in polynomial time
• Optimal procedures for the discrete time/cost trade-off problem in project networks
• scientific article; zbMATH DE number 176473 (Why is no real title available?)
• Job selection and sequencing on a single machine in a random environment
• On the complexity of dynamic programming for sequencing problems with precedence constraints
• \(P_ 4\)-trees and substitution decomposition
• NP-completeness of some optimal sequencing problems with a given grouping of elements
• The discrete time-cost tradeoff problem revisited
• Optimal Consecutive-k-out-of-n:F Component Sequencing
• Scheduling results applicable to decision-theoretic troubleshooting
• Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation
• A k-structure generalization of the theory of 2-structures
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• \(N\)-extendible posets, and how to minimize total weighted completion time
• Scheduling with due date assignment under special conditions on job processing
• Shortest-route formulation of mixed-model assembly line balancing problem
• Modular decomposition of graphs and the distance preserving property
• Scheduling of resource tasks
• Single machine scheduling with precedence constraints and positionally dependent processing times

This page was built for publication: Optimal Sequencing by Modular Decomposition: Polynomial Algorithms

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