Sequencing with Series-Parallel Precedence Constraints

DOI10.1287/moor.4.3.215zbMath0437.90047OpenAlexW2170113998MaRDI QIDQ3879034

Clyde l. Monma, Jeffrey B. Sidney

Publication date: 1979

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ecc879ebccfa021685c566be442635736430825f

zbMATH Keywords

schedulingsequencingseries-parallel precedence constraintsone-machine total weighted completion time problemleast cost fault detection problemmaximum cumulative cost problemadjacent pairwise job interchangeefficient general algorithmsubsequences of jobstotal preference orderingtwo-machine maximum completion time flow-shop problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

Related Items (41)

Optimal ordering of statistically dependent tests ⋮ A compact labelling scheme for series-parallel graphs ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Sequential testing of complex systems: a review ⋮ The two-machine flow shop problem with arbitrary precedence relations ⋮ The three-machine flow-shop problem with arbitrary precedence relations ⋮ Stochastic scheduling and forwards induction ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ Scheduling problems with partially ordered jobs ⋮ Search and rescue in the face of uncertain threats ⋮ Scheduling modular projects on a bottleneck resource ⋮ Confluence up to Garbage ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ Sequencing with general precedence constraints ⋮ On Submodular Search and Machine Scheduling ⋮ Single machine scheduling with a generalized job-dependent cumulative effect ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ Solutions for subset sum problems with special digraph constraints ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times ⋮ A note on the optimality of index priority rules for search and sequencing problems ⋮ Time-critical testing and search problems ⋮ A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations ⋮ Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods ⋮ A branch‐and‐bound algorithm for scheduling of new product development projects ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times ⋮ Minimizing the makespan in a two-machine cross-docking flow shop problem ⋮ Optimal ordering of independent tests with precedence constraints ⋮ On strictly optimal schedules for the cumulative cost-optimal scheduling problem ⋮ Discrete-continuous project scheduling with discounted cash inflows and various payment models -- a review of recent results ⋮ Confluence up to garbage in graph transformation ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ A decomposition theory based on a dominance relation and composite jobs ⋮ On nonpreemptive strategies in stochastic scheduling ⋮ A Note on Stochastic Scheduling on a Single Machine Subject to Breakdown and Repair ⋮ Effective optimization methods for single-machine scheduling (survey) ⋮ Miscellaneous Digraph Classes ⋮ Scheduling Opposing Forests ⋮ Non-bottleneck machines in three-machine flow shops

This page was built for publication: Sequencing with Series-Parallel Precedence Constraints