Structure of a simple scheduling polyhedron
From MaRDI portal
Publication:1803611
DOI10.1007/BF01581271zbMath0778.90031OpenAlexW2075265959MaRDI QIDQ1803611
Publication date: 29 June 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01581271
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic scheduling theory in operations research (90B35)
Related Items (56)
Permutation polytopes corresponding to strongly supermodular functions ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time ⋮ A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling ⋮ Sequencing unreliable jobs on parallel machines ⋮ Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times ⋮ Two-agent scheduling in a flowshop ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Decomposition Algorithm for the Single Machine Scheduling Polytope ⋮ The archievable region method in the optimal control of queueing systems; formulations, bounds and policies ⋮ Scheduling orders for multiple product types to minimize total weighted completion time ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Minimizing the sum of weighted completion times in a concurrent open shop ⋮ A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness ⋮ A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ The affine hull of the schedule polytope for servicing identical requests by parallel devices ⋮ Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds ⋮ Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types ⋮ SPT optimality (mostly) via linear programming ⋮ Two-agent scheduling to minimize the total cost ⋮ Mathematical model applied to single-track line scheduling problem in Brazilian railways ⋮ An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule ⋮ A system-centric metric for the evaluation of online job schedules ⋮ Theory of Principal Partitions Revisited ⋮ On scheduling coflows ⋮ Scheduling of uniform parallel machines with s-precedence constraints ⋮ Approximating the least core value and least core of cooperative games with supermodular costs ⋮ A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine ⋮ Proportional scheduling, split-proofness, and merge-proofness ⋮ Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Equivalence of permutation polytopes corresponding to strictly supermodular functions ⋮ Constructing Extended Formulations from Reflection Relations ⋮ A supermodular relaxation for scheduling with release dates ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ On the convex hull of feasible solutions to certain combinatorial problems ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ The constrained minimum weighted sum of job completion times problem ⋮ A family of inequalities valid for the robust single machine scheduling polyhedron ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints ⋮ Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms ⋮ Approximability of total weighted completion time with resource consuming jobs ⋮ Submodular function minimization ⋮ Facets of the generalized permutahedron of a poset ⋮ Order Scheduling Models: Hardness and Algorithms ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ SINGLE MACHINE DUE DATE ASSIGNMENT SCHEDULING PROBLEM WITH PRECEDENCE CONSTRAINTS AND CONTROLLABLE PROCESSING TIMES IN FUZZY ENVIRONMENT ⋮ Combinatorial algorithms for data migration to minimize average completion time ⋮ Scheduling MapReduce jobs on identical and unrelated processors ⋮ A game theoretic approach to a problem in polymatroid maximization ⋮ Approximation algorithms for shop scheduling problems with minsum objective
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New directions in scheduling theory
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach
- The ellipsoid method and its consequences in combinatorial optimization
- Minimizing Weighted Completion Times with Deadlines
- On the facial structure of scheduling polyhedra
- Submodular systems and related topics
- On the Polyhedral Decision Problem
- Characterizations of adjacency of faces of polyhedra
- Selected Applications of Minimum Cuts in Networks
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- Convex Analysis
This page was built for publication: Structure of a simple scheduling polyhedron
