Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem

DOI10.1016/j.ejor.2004.07.050zbMath1077.90030MaRDI QIDQ2569091

Shi, Leyuan, Yunpeng Pan

Publication date: 17 October 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.07.050

zbMATH Keywords

scheduling; branch-and-bound; hard instances; one-machine

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90B35: Deterministic scheduling theory in operations research

Related Items

Improving the preemptive bound for the single machine dynamic maximum lateness problem, Jackson's semi-preemptive scheduling on a single machine

Uses Software

• OR-Library
• JOBSHOP

Cites Work

• A practical use of Jackson's preemptive schedule for solving the job shop problem
• A block approach for single-machine scheduling with release dates and due dates
• The one-machine sequencing problem
• A branch and bound algorithm for the job-shop scheduling problem
• Adjustment of heads and tails for the job-shop problem
• Scheduling the General Job-Shop
• An Algorithm for Solving the Job-Shop Problem
• A Computational Study of the Job-Shop Scheduling Problem
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Minimizing maximum lateness on one machine: computational experience and some applications
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• An existence theorem for packing problems with implications for the computation of optimal machine schedules
• Sequencing with due-dates and early start times to minimize maximum tardiness
• A new approach to computing optimal schedules for the job-shop scheduling problem
• On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/F_max) problem
• Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments