Structure of a simple scheduling polyhedron
From MaRDI portal
Publication:1803611
Properties of a simple scheduling polyhedron \(P\) for one-machine nonpreemptive scheduling problem are considered. Any feasible schedule in one-machine nonpreemptive scheduling problem is defined by the vector of job completion times. The polyhedron \(P\) is the convex hull of all feasible completion time vectors. A complete description of \(P\) by a minimal system of linear inequalities is suggested. The author gives also a complete combinatorial description of the face lattice of \(P\) and proposes an \(O(n \log n)\) separation algorithm, which may be used for constructing cutting plane type algorithms for solving different scheduling problems.
Recommendations
Cites work
- Characterizations of adjacency of faces of polyhedra
- Convex Analysis
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- scientific article; zbMATH DE number 3679888 (Why is no real title available?)
- scientific article; zbMATH DE number 3756243 (Why is no real title available?)
- scientific article; zbMATH DE number 3757695 (Why is no real title available?)
- scientific article; zbMATH DE number 3323651 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- scientific article; zbMATH DE number 3096283 (Why is no real title available?)
- Minimizing Weighted Completion Times with Deadlines
- New directions in scheduling theory
- On the facial structure of scheduling polyhedra
- On the Polyhedral Decision Problem
- Selected Applications of Minimum Cuts in Networks
- Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- Submodular systems and related topics
- The ellipsoid method and its consequences in combinatorial optimization
Cited in
(67)- Combinatorial algorithms for data migration to minimize average completion time
- On the convex hull of feasible solutions to certain combinatorial problems
- The relation of time indexed formulations of single machine scheduling problems to the node packing problem
- Approximation algorithms for shop scheduling problems with minsum objective
- A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Approximability of total weighted completion time with resource consuming jobs
- Permutation polytopes corresponding to strongly supermodular functions
- A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling
- The archievable region method in the optimal control of queueing systems; formulations, bounds and policies
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- A game theoretic approach to a problem in polymatroid maximization
- Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times
- On scheduling coflows
- A family of inequalities valid for the robust single machine scheduling polyhedron
- Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates
- Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
- A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- A system-centric metric for the evaluation of online job schedules
- Approximating the least core value and least core of cooperative games with supermodular costs
- Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
- Designing PTASs for MIN-SUM scheduling problems
- The constrained minimum weighted sum of job completion times problem
- On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
- Optimal mechanism design for a sequencing problem with two-dimensional types
- Theory of principal partitions revisited
- Constructing extended formulations from reflection relations
- Scheduling two chains of unit jobs on one machine: a polyhedral study
- Unrelated machine scheduling with stochastic processing times
- Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a single machine
- Decomposition algorithm for the single machine scheduling polytope
- Two-agent scheduling in a flowshop
- Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
- scientific article; zbMATH DE number 4170623 (Why is no real title available?)
- A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints
- On the facial structure of scheduling polyhedra
- Variations on the integral decomposition property
- Two-agent scheduling to minimize the total cost
- An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule
- Single machine due date assignment scheduling problem with precedence constraints and controllable processing times in fuzzy environment
- A supermodular relaxation for scheduling with release dates
- Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
- 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
- Order Scheduling Models: Hardness and Algorithms
- Facets of the generalized permutahedron of a poset
- Minimizing the sum of weighted completion times in a concurrent open shop
- SPT optimality (mostly) via linear programming
- Comparison and polyhedral properties of valid inequalities for a polytope of schedules for servicing identical requests
- Scheduling of uniform parallel machines with s-precedence constraints
- Mixed-model moving assembly line material placement optimization for a shorter time-dependent worker walking time
- Improved linear programming relaxations for flow shop problems with makespan minimization
- Cost-sharing in parking games
- Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms
- Polytope scheduling with groups: unified models and optimal guarantees
- Scheduling MapReduce jobs on identical and unrelated processors
- Mixed integer formulations using natural variables for single machine scheduling around a common due date
- Sequencing unreliable jobs on parallel machines
- Scheduling orders for multiple product types to minimize total weighted completion time
- Mathematical model applied to single-track line scheduling problem in Brazilian railways
- Proportional scheduling, split-proofness, and merge-proofness
- Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time
- Equivalence of permutation polytopes corresponding to strictly supermodular functions
- Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
- Submodular function minimization
This page was built for publication: Structure of a simple scheduling polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803611)
