Single-Machine Scheduling Polyhedra with Precedence Constraints
From MaRDI portal
Publication:3971735
DOI10.1287/moor.16.1.1zbMath0747.90051OpenAlexW2032912812MaRDI QIDQ3971735
Maurice Queyranne, Yaoguang Wang
Publication date: 25 June 1992
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.16.1.1
single machineprecedence constraintsconvex hullsnon-preemptive schedulingfacet- inducing inequalities
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)
Related Items
Mixed integer formulations using natural variables for single machine scheduling around a common due date, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times, How to make OR-results available: A proposal for project scheduling, Exact and Approximation Algorithms for the Expanding Search Problem, Separable approximations and decomposition methods for the augmented Lagrangian, The affine hull of the schedule polytope for servicing identical requests by parallel devices, Formulating a scheduling problem with almost identical jobs by using positional completion times, Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds, SPT optimality (mostly) via linear programming, Comparison and polyhedral properties of valid inequalities for a polytope of schedules for servicing identical requests, Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms, An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective, Precedence constrained scheduling to minimize sum of weighted completion times on a single machine, The permutahedron of series-parallel posets, On the convex hull of feasible solutions to certain combinatorial problems, Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem, The constrained minimum weighted sum of job completion times problem, Facets of the generalized permutahedron of a poset, A branch and bound algorithm for the minimum storage-time sequencing problem, Structure of a simple scheduling polyhedron, Scheduling two chains of unit jobs on one machine: A polyhedral study, Base polytopes of series-parallel posets: Linear description and optimization, Local search procedures for improving feasible solutions to the sequential ordering problem
