IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v23y1975i2p283-298.html
   My bibliography  Save this article

Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs

Author

Listed:
  • Jeffrey B. Sidney

    (University of British Columbia, Vancouver, British Columbia)

Abstract

A one-machine deterministic job-shop sequencing problem is considered. Associated with each job is its processing time and linear deferral cost. In addition, the jobs are related by a general precedence relation. The objective is to order the jobs so as to minimize the sum of the deferral costs, subject to the constraint that the ordering must be consistent with the precedence relation. A decomposition algorithm is presented, and it is proved that a permutation is optimal if and only if it can be generated by this algorithm. Four special network structures are then considered, and specializations of the general algorithm are presented.

Suggested Citation

  • Jeffrey B. Sidney, 1975. "Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs," Operations Research, INFORMS, vol. 23(2), pages 283-298, April.
    • Handle: RePEc:inm:oropre:v:23:y:1975:i:2:p:283-298
    DOI: 10.1287/opre.23.2.283
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.23.2.283
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.23.2.283?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. Herbert Hamers & Flip Klijn & Bas Velzen, 2005. "On the Convexity of Precedence Sequencing Games," Annals of Operations Research, Springer, vol. 137(1), pages 161-175, July.
    2. Davila-Pena, Laura & Borm, Peter & Garcia-Jurado, Ignacio & Schouten, Jop, 2023. "An Allocation Rule for Graph Machine Scheduling Problems," Other publications TiSEM 17013f33-1d65-4294-802c-b, Tilburg University, School of Economics and Management.
    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. Felix Happach & Lisa Hellerstein & Thomas Lidbetter, 2022. "A General Framework for Approximating Min Sum Ordering Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1437-1452, May.
    6. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    7. 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.
    8. Kevin D. Glazebrook, 1987. "Evaluating the effects of machine breakdowns in stochastic scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 319-335, June.
    9. Davila-Pena, Laura & Borm, Peter & Garcia-Jurado, Ignacio & Schouten, Jop, 2023. "An Allocation Rule for Graph Machine Scheduling Problems," Discussion Paper 2023-009, Tilburg University, Center for Economic Research.
    10. Seyed M. R. Iravani & John A. Buzacott & Morton J. M. Posner, 2003. "Operations and Shipment Scheduling of a Batch on a Felxible Machine," Operations Research, INFORMS, vol. 51(4), pages 585-601, August.
    11. Robbert Fokkink & Thomas Lidbetter & László A. Végh, 2019. "On Submodular Search and Machine Scheduling," Management Science, INFORMS, vol. 44(4), pages 1431-1449, November.
    12. 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.
    13. Lisa Hellerstein & Thomas Lidbetter & Daniel Pirutinsky, 2019. "Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games," Operations Research, INFORMS, vol. 67(3), pages 731-743, May.
    14. D. Prot & O. Bellenguez-Morineau, 2018. "A survey on how the structure of precedence constraints may change the complexity class of scheduling problems," Journal of Scheduling, Springer, vol. 21(1), pages 3-16, February.
    15. Andreas S. Schulz & Nelson A. Uhan, 2011. "Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 14-23, February.
    16. Christoph Ambühl & Monaldo Mastrolilli & Nikolaus Mutsanas & Ola Svensson, 2011. "On the Approximability of Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 653-669, November.
    17. Herbert Hamers & Flip Klijn & Bas van Velzen, 2002. "On Games corresponding to Sequencing Situations with Precedence Relations," UFAE and IAE Working Papers 553.02, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    18. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    19. 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.
    20. K. D. Glazebrook, 1992. "Single‐machine scheduling of stochastic jobs subject to deterioration or delay," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(5), pages 613-633, August.
    21. Hamers, H.J.M. & Klijn, F. & van Velzen, S., 2002. "On the Convexity of Precedence Sequencing Games," Other publications TiSEM 0511fa02-e967-42b3-b9f8-3, Tilburg University, School of Economics and Management.
    22. Agnetis, Alessandro & Hermans, Ben & Leus, Roel & Rostami, Salim, 2022. "Time-critical testing and search problems," European Journal of Operational Research, Elsevier, vol. 296(2), pages 440-452.

    More about this item

    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:oropre:v:23:y:1975:i:2:p:283-298. 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.