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

partial-order decomposition algorithmspolynomial timeprecedence constraintssequencing

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

(26)

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

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)