The Stock Size Problem

Hans Kellerer, Vladimir Kotov, Franz Rendl and Gerhard J. Woeginger
Additional contact information
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

Operations Research, 1998, vol. 46, issue 3-supplement-3, S1-S12

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.

Keywords: analysis of algorithms: worst-case analysis of heuristics; production/scheduling: minimization of maximum stock size (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.S1 (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:46:y:1998:i:3-supplement-3:p:s1-s12

Access Statistics for this article

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