A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing)

DOI10.1137/0803002MaRDI QIDQ4697307zbMATH OpenOpenAlexFDO

Authors Norbert Ascheuer, Martin Grötschel, Mechthild Stoer, Laureano F. Escudero Bueno

Publication date 29 June 1993

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0803002

zbMATH Keywords

precedence constraintstraveling salesmanbranch-and-cut algorithmsfeasible minimum cost Hamiltonian path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Recommendations

• On dual based lower bounds for the sequential ordering problem with precedences and due dates
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• Local search procedures for improving feasible solutions to the sequential ordering problem
• Note—Operations Sequencing in Discrete Parts Manufacturing
• On due-date based valid cuts for the sequential ordering problem

Cited in

(22)

• A cutting and scheduling problem in float glass manufacturing
• An inexact algorithm for the sequential ordering problem
• A sequential ordering problem in automotive paint shops
• Tree based models and algorithms for the preemptive asymmetric stacker crane problem
• Computing Hamiltonian paths with partial order restrictions
• A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem
• The application of preprocessing and cutting plane techniques for a class of production planning problems
• A polyhedral study of the asymmetric traveling salesman problem with time windows
• Local search procedures for improving feasible solutions to the sequential ordering problem
• Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem
• DGFFRL: solving multi-machine collaborative scheduling based on dual graph feature fusion reinforcement learning
• The path set polytope of an acyclic, directed graph with an application to machine sequencing
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• A heuristic manipulation technique for the sequential ordering problem
• Coupling ant colony systems with strong local searches
• A hybrid particle swarm optimization approach for the sequential ordering problem
• Note—Operations Sequencing in Discrete Parts Manufacturing
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• Solving the job sequencing and tool switching problem as a nonlinear least cost Hamiltonian cycle problem
• Tight lower bounds for the traveling salesman problem with draft limits
• On due-date based valid cuts for the sequential ordering problem
• A hybrid heuristic approach for the multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This page was built for publication: A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing)

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