Abstract
This paper presents an algorithm for solving resource-constrained network scheduling problems, a general class of problems that includes the classical job-shop-scheduling problem. It uses Lagrange multipliers to dualize the resource constraints, forming a Lagrangian problem in which the network constraints appear explicitly, while the resource constraints appear only in the Lagrangian function. Because the network constraints do not interact among jobs, the problem of minimizing the Lagrangian decomposes into a subproblem for each job. Algorithms are presented for solving these subproblems. Minimizing the Lagrangian with fixed multiplier values yields a lower bound on the cost of an optimal solution to the scheduling problem. The paper gives procedures for adjusting the multipliers iteratively to obtain strong bounds, and it develops a branch-and-bound algorithm that uses these bounds in the solution of the scheduling problem. Computational experience with this algorithm is discussed.
Keywords
Lagrange multiplierMathematical optimizationLagrangian relaxationLagrangianJob shop schedulingScheduling (production processes)Computer scienceConstraint algorithmMathematicsScheduleApplied mathematics
Affiliated Institutions
Related Publications
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and co...
A new approach to variable selection in least squares problems
The title Lasso has been suggested by Tibshirani (1996) as a colourful name for a technique of variable selection which requires the minimization of a sum of squares subject to ...
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
The number of days required to clear a check drawn on a bank in city j depends on the city i in which the check is cashed. Thus, to maximize its available funds, a company that ...
GloptiPoly
GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a mult...
An Algorithm for the Traveling Salesman Problem
A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by...
Publication Info
- Year
- 1973
- Type
- article
- Volume
- 21
- Issue
- 5
- Pages
- 1114-1127
- Citations
- 249
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
249
OpenAlex
Cite This
Marshall L. Fisher
(1973).
Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I.
Operations Research
, 21
(5)
, 1114-1127.
https://doi.org/10.1287/opre.21.5.1114
Identifiers
- DOI
- 10.1287/opre.21.5.1114