Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I

Marshall L. Fisher
Additional contact information
Marshall L. Fisher: University of Chicago, Chicago, Illinois

Operations Research, 1973, vol. 21, issue 5, 1114-1127

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.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.5.1114 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:21:y:1973:i:5:p:1114-1127

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().