A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time

C. N. Potts
Additional contact information
C. N. Potts: Department of Mathematics, University of Keele, Keele, Staffordshire ST5 5BG, United Kingdom

Management Science, 1985, vol. 31, issue 10, 1300-1311

Abstract: The single machine sequencing problem is considered in which there are precedence constraints on the jobs. The objective is to minimize the sum of weighted completion times. A lower bound is obtained by successively performing a Lagrangean relaxation of appropriate constraints. Each Lagrange multiplier is chosen to provide the maximum increment to the lower bound subject to retaining the nonnegativity of the coefficients of the variables. When no further suitable constraints can be introduced into the Lagrangean function, the variables having zero cost coefficient are used to obtain a feasible sequence which provides an upper bound. The gap between the lower and upper bound is reduced by removing some constraints from the Lagrangean function and replacing them with others. This lower bounding procedure is used in a branch and bound algorithm. Computational results indicate that the algorithm can satisfactorily solve problems with up to 100 jobs.

Keywords: scheduling; branch and bound (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.31.10.1300 (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:ormnsc:v:31:y:1985:i:10:p:1300-1311

Access Statistics for this article

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