Scheduling two chains of unit jobs on one machine: a polyhedral study

DOI10.1002/NET.20452MaRDI QIDQ3100690zbMATH OpenOpenAlexFDO

Authors Claudio Arbib, Martine Labbé, Mara Servilio

Publication date 21 November 2011

Published in Networks (Search for Journal in Brave)

Full work available at URL https://dipot.ulb.ac.be/dspace/bitstream/2013/74877/1/ArbibLabbeServilio.pdf

zbMATH Keywords

convex hullfacet-defining inequalitiesone-machine scheduling

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Polyhedral results for position-based scheduling of chains on a single machine
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• scientific article; zbMATH DE number 4170623
• Structure of a simple scheduling polyhedron
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem

Cites work

• A competitive scheduling problem and its relevance to UMTS channel assignment
• A polyhedral approach to single-machine scheduling problems.
• A set packing model for the ground holding problem in congested networks
• Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation
• Lot-Sizing with Constant Batches: Formulation and Valid Inequalities
• On facets of stable set polytopes of claw-free graphs with stability number 3
• On maximal independent sets of vertices in claw-free graphs
• On project scheduling with irregular starting time costs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Order preserving assignments without contiguity
• Polyhedral Characterization of Discrete Dynamic Programming
• Scheduling jobs of equal length: Complexity, facets and computational results
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation
• Solving project scheduling problems by minimum cut computations
• Strong formulations for mixed integer programming: A survey
• The relation of time indexed formulations of single machine scheduling problems to the node packing problem

Cited in

(6)

• Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra
• A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
• The affine hull of the schedule polytope for servicing identical requests by parallel devices
• Scheduling three chains on two parallel machines
• Optimum Solution of the Closest String Problem via Rank Distance
• Polyhedral results for position-based scheduling of chains on a single machine

This page was built for publication: Scheduling two chains of unit jobs on one machine: a polyhedral study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3100690)