IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v31y1985i10p1300-1311.html
   My bibliography  Save this article

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

Author

Listed:
  • C. N. Potts

    (Department of Mathematics, University of Keele, Keele, Staffordshire ST5 5BG, United Kingdom)

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.

Suggested Citation

  • C. N. Potts, 1985. "A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time," Management Science, INFORMS, vol. 31(10), pages 1300-1311, October.
    • Handle: RePEc:inm:ormnsc:v:31:y:1985:i:10:p:1300-1311
    DOI: 10.1287/mnsc.31.10.1300
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.31.10.1300
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.31.10.1300?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2002. "A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems," International Journal of Production Economics, Elsevier, vol. 79(3), pages 185-196, October.
    2. Prahalad Venkateshan & Joseph Szmerekovsky & George Vairaktarakis, 2020. "A cutting plane approach for the multi-machine precedence-constrained scheduling problem," Annals of Operations Research, Springer, vol. 285(1), pages 247-271, February.
    3. Rostami, Salim & Creemers, Stefan & Leus, Roel, 2019. "Precedence theorems and dynamic programming for the single-machine weighted tardiness problem," European Journal of Operational Research, Elsevier, vol. 272(1), pages 43-49.
    4. François Margot & Maurice Queyranne & Yaoguang Wang, 2003. "Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem," Operations Research, INFORMS, vol. 51(6), pages 981-992, December.
    5. Yiyo Kuo & Sheng-I Chen & Yen-Hung Yeh, 2020. "Single machine scheduling with sequence-dependent setup times and delayed precedence constraints," Operational Research, Springer, vol. 20(2), pages 927-942, June.
    6. Ali Koç & David P. Morton, 2015. "Prioritization via Stochastic Optimization," Management Science, INFORMS, vol. 61(3), pages 586-603, March.
    7. Nicholas G. Hall & Marc E. Posner, 2001. "Generating Experimental Data for Computational Testing with Machine Scheduling Applications," Operations Research, INFORMS, vol. 49(6), pages 854-865, December.
    8. Tanaka, Shunji & Sato, Shun, 2013. "An exact algorithm for the precedence-constrained single-machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 345-352.
    9. Öncan, Temel & AltInel, I. Kuban, 2008. "Exact solution procedures for the balanced unidirectional cyclic layout problem," European Journal of Operational Research, Elsevier, vol. 189(3), pages 609-623, September.
    10. P. Detti & D. Pacciarelli, 2001. "A branch and bound algorithm for the minimum storage‐time sequencing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(4), pages 313-331, June.

    More about this item

    Keywords

    scheduling; branch and bound;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:31:y:1985:i:10:p:1300-1311. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.