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

DOI10.1137/0803002zbMATH Open0794.90039OpenAlexW1964651230MaRDI QIDQ4697307FDOQ4697307

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

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

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)

Cited In (20)

• A cutting and scheduling problem in float glass manufacturing
• A sequential ordering problem in automotive paint shops
• An inexact algorithm for the sequential ordering problem
• Tree based models and algorithms for the preemptive asymmetric stacker crane problem
• 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
• 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
• Note—Operations Sequencing in Discrete Parts Manufacturing
• A hybrid particle swarm optimization approach for the sequential ordering problem
• 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)