IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v46y1998i3-supplement-3ps1-s12.html
   My bibliography  Save this article

The Stock Size Problem

Author

Listed:
  • Hans Kellerer

    (Universität Graz, Graz, Austria)

  • Vladimir Kotov

    (University of Minsk, Minsk, Byelarussia)

  • Franz Rendl

    (Technische Universität Graz, Graz, Austria)

  • Gerhard J. Woeginger

    (Technische Universität Graz, Graz, Austria)

Abstract

Consider a number of jobs that have to be completed within some fixed period of time. Each job consumes or supplies a certain, job-dependent quantity of a resource thus changing the contents of a stock. Natural examples for this scenario arise in the case of trucks delivering goods to a trade house and taking other goods away from it, or in the case where processes change their environment. The goal is to find an ordering of the jobs such that all jobs can be completed and such that the maximum stock size needed over the time period becomes minimum. Since this problem can be shown to be NP-hard, we present three polynomial time approximation algorithms which yield job sequences with maximum stock size at most 2, respectively 8/5 times and 3/2 times the optimum stock size. These approximation algorithms are also compared by a numerical simulation. Moreover, we consider a variation of the problem where consecutive processes are allowed to directly exchange resources without using the stock.

Suggested Citation

  • Hans Kellerer & Vladimir Kotov & Franz Rendl & Gerhard J. Woeginger, 1998. "The Stock Size Problem," Operations Research, INFORMS, vol. 46(3-supplem), pages 1-12, June.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:3-supplement-3:p:s1-s12
    DOI: 10.1287/opre.46.3.S1
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.3.S1
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.3.S1?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
    ---><---

    References listed on IDEAS

    as
    1. Clyde L. Monma, 1980. "Sequencing to Minimize the Maximum Job Cost," Operations Research, INFORMS, vol. 28(4), pages 942-951, August.
    2. H. M. Abdel-Wahab & T. Kameda, 1978. "Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints," Operations Research, INFORMS, vol. 26(1), pages 141-158, February.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Agnetis, Alessandro & Aloulou, Mohamed Ali & Fu, Liang-Liang, 2014. "Coordination of production and interstage batch delivery with outsourced distribution," European Journal of Operational Research, Elsevier, vol. 238(1), pages 130-142.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chen, Feng & Lee, Chung-Yee, 2009. "Minimizing the makespan in a two-machine cross-docking flow shop problem," European Journal of Operational Research, Elsevier, vol. 193(1), pages 59-72, February.
    2. A.A. Gladky & Y.M. Shafransky & V.A. Strusevich, 2004. "Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 13-28, March.
    3. Chung-Yee Lee & Ming Liu & Chengbin Chu, 2015. "Optimal Algorithm for the General Quay Crane Double-Cycling Problem," Transportation Science, INFORMS, vol. 49(4), pages 957-967, November.
    4. Y.M. Shafransky & V.A. Strusevich, 1998. "The open shop scheduling problem with a given sequence of jobs on one machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 705-731, October.

    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:46:y:1998:i:3-supplement-3:p:s1-s12. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.