A polyhedral approach to single-machine scheduling problems.

DOI10.1007/s10107990047azbMath1072.90523OpenAlexW2140333448MaRDI QIDQ1586211

J. M. van den Akker, Stan P. M. van Hoesel, Savelsbergh, Martin W. P.

Publication date: 12 November 2000

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://cris.maastrichtuniversity.nl/ws/files/1177972/guid-b1a8d1f0-5a4c-483d-8c75-777e72eaa106-ASSET1.0.pdf

zbMATH Keywords

schedulingseparationbranch-and-cutpolyhedral methodsfacet inducing inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items (24)

Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs ⋮ Fast separation for the three-index assignment problem ⋮ Just-in-time single-batch-processing machine scheduling ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ A branch and price solution approach for order acceptance and capacity planning in make-to-order operations ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ Changeover formulations for discrete-time mixed-integer programming scheduling models ⋮ Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ A time-dependent multiple criteria single-machine scheduling problem ⋮ Valid inequalities for a time-indexed formulation ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ Scheduling of tasks with effectiveness precedence constraints ⋮ Scheduling two chains of unit jobs on one machine: A polyhedral study ⋮ Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars ⋮ A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times

Uses Software

• MINTO

This page was built for publication: A polyhedral approach to single-machine scheduling problems.