An algorithm for the single machine sequencing problem with precedence constraints
From MaRDI portal
Publication:3883868
DOI10.1007/BFb0120909zbMath0441.90038OpenAlexW179016828MaRDI QIDQ3883868
Publication date: 1980
Published in: Mathematical Programming Studies (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bfb0120909
algorithmlower boundprecedence constraintsbranch and bound algorithmcomputational experienceprocessing timedominance rulessingle machine sequencingminimization of completion time
Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Boolean programming (90C09)
Related Items
Single machine scheduling problems with uncertain parameters and the OWA criterion ⋮ Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ Minimizing the total weighted duration of courses in a single machine problem with precedence constraints ⋮ Mathematical model applied to single-track line scheduling problem in Brazilian railways ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Precedence constrained scheduling to minimize sum of weighted completion times on a single machine ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Time-critical testing and search problems ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ A heuristic hybrid framework for vector job scheduling
