Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
From MaRDI portal
Publication:4060706
DOI10.1287/opre.23.2.283zbMath0304.90058OpenAlexW2096521993MaRDI QIDQ4060706
Publication date: 1975
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.23.2.283
Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35)
Related Items (45)
Decomposition of Directed Graphs ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ File space utilization in database conversion ⋮ Single-machine scheduling with precedence constraints and position-dependent processing times ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ A 2-OPT procedure to reduce total inspection time in a serial inspection process ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Ranking the vertices of a complete multipartite paired comparison digraph ⋮ An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs ⋮ Partially ordered knapsack and applications to scheduling ⋮ The pairwise flowtime network construction problem ⋮ Sequencing with general precedence constraints ⋮ On Submodular Search and Machine Scheduling ⋮ On the measurement of complexity in activity networks ⋮ Task scheduling with precedence constraints to minimize the total completion time ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games ⋮ Precedence constrained scheduling to minimize sum of weighted completion times on a single machine ⋮ \(N\)-extendible posets, and how to minimize total weighted completion time ⋮ Sensitivity analysis for some scheduling problems ⋮ The permutahedron of series-parallel posets ⋮ Time-critical testing and search problems ⋮ Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times ⋮ Asymptotically optimal schedules for single-server flow shop problems with setup costs and times ⋮ Single machine scheduling with decreasing linear deterioration under precedence constraints ⋮ On batch scheduling of jobs with stochastic service times and cost structures on a single server ⋮ A branch and bound algorithm for the minimum storage-time sequencing problem ⋮ On strictly optimal schedules for the cumulative cost-optimal scheduling problem ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Effective solution of certain problems of theory of schedulings of nets ⋮ A decomposition theory based on a dominance relation and composite jobs ⋮ Single Machine General Maximum Cost Problem with Parallel-Chain Precedence Constraints ⋮ Base polytopes of series-parallel posets: Linear description and optimization ⋮ Finding a Maximum-Weight Convex Set in a Chordal Graph ⋮ Single-machine scheduling problems with precedence constraints and simple linear deterioration ⋮ A decomposition of distributive lattices ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem ⋮ On the convexity of precedence sequencing games
This page was built for publication: Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
