Surrogate duality relaxation for job shop scheduling

DOI10.1016/0166-218X(83)90016-1zbMath0498.90045OpenAlexW2094331967MaRDI QIDQ1171504

B. J. Lageweg, Alexander H. G. Rinnooy Kan, Marshall L. Fisher, Jan Karel Lenstra

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(83)90016-1

zbMATH Keywords

job shop schedulingprecedence constraintscapacity constraintsreplacing constraints by weighted sumssurrogate duality bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

Related Items (12)

On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming ⋮ Job-shop production scheduling with reverse flows ⋮ Matheuristics: survey and synthesis ⋮ A new approach to computing optimal schedules for the job-shop scheduling problem ⋮ Deterministic job-shop scheduling: Past, present and future ⋮ Lagrangian relaxation of the generic materials and operations planning model ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Reduction of job-shop problems to flow-shop problems with precedence constraints ⋮ New directions in scheduling theory ⋮ Applying machine based decomposition in 2-machine flow shops ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ On generalized surrogate duality in mixed-integer nonlinear programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Calculating surrogate constraints
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• A branch and bound algorithm for the generalized assignment problem
• Surrogate Constraint Duality in Mathematical Programming
• Minimizing maximum lateness on one machine: computational experience and some applications
• A dual algorithm for the one-machine scheduling problem
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• Job-Shop Scheduling by Implicit Enumeration
• The Complexity of Flowshop and Jobshop Scheduling
• Computational Complexity of Discrete Optimization Problems
• Surrogate Constraints
• Solving Resource-Constrained Network Problems by Implicit Enumeration—Nonpreemptive Case
• A Direct Search Method to Locate Negative Cycles in a Graph
• A Method of Solution for General Machine-Scheduling Problems
• The traveling-salesman problem and minimum spanning trees: Part II
• Convergence rate of the gradient descent method with dilatation of the space
• On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/F_max) problem

This page was built for publication: Surrogate duality relaxation for job shop scheduling