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

DOI10.1016/J.EJOR.2004.07.050MaRDI QIDQ2569091zbMATH OpenOpenAlexFDO

Authors Yunpeng Pan, Shi, Leyuan

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

branch-and-boundhard instancesone-machinescheduling

Mathematics Subject Classification ID

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

Recommendations

• A branch-and-bound algorithm for one class of scheduling problem
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags
• Revisiting branch and bound search strategies for machine scheduling problems
• On the representation of the one machine sequencing problem in the shifting bottleneck heuristic
• A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
• The complexity of one-machine batching problems
• A branch and bound algorithm for the minimum storage-time sequencing problem
• An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints
• Branch and bound algorithms for single-machine scheduling with batch set-up times to minimize total weighted completion time

Cites work

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

Cited in

(8)

• Scheduling a single machine with primary and secondary objectives
• A branch and bound algorithm for the minimum storage-time sequencing problem
• An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints
• On the benefits of using NP-hard problems in branch \& bound
• An 11/7 — Approximation Algorithm for Single Machine Scheduling Problem with Release and Delivery Times
• Scheduling Algorithms for Single Machine Problem with Release and Delivery Times
• Improving the preemptive bound for the single machine dynamic maximum lateness problem
• Jackson's semi-preemptive scheduling on a single machine

Describes a project that uses

Uses Software

• OR-Library
• JOBSHOP

This page was built for publication: Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem

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