Approaches to Solving RCPSP Using Relaxed Problem with Consumable Resources

Ivan A. Rykov ()
Additional contact information
Ivan A. Rykov: Novosibirsk State University

A chapter in Operations Research Proceedings 2006, 2007, pp 547-552 from Springer

Abstract: Abstract In the work a resource-constrained project scheduling problem (RCPSP) is considered. This classical NP-hard problem evokes interest from both theoretical and applied points of view. Thus we can divide effective (i.e. polynomial) approximation algorithms in two groups: fast heuristic algorithms for the whole problem and generalizations and algorithms with performance guarantee for particular cases. In first section we consider the statement of the problem and some generalizations. Along with renewable resources we consider consumable resources which can be stored to be used at any moment after the moment of allocation. A polynomial optimal algorithm for solving the problem with consumable resources only was suggested by Gimadi, Sevastianov and Zalyubovsky [2]. So we can consider polynomially solved relaxation of RCPSP. In this relaxation instead of each renewable resource we have consumable resource which is allocated at each moment of time in one and the same amount. Then we can use information about the solution of this relaxation for approximate solving the original problem in polynomial time (for example, the order of starting times can be used as a heuristic for serial scheduling scheme). Furthermore, the optimal value of relaxation gives the lower bound for the optimal value of the original problem.

Keywords: Precedence Constraint; Feasible Schedule; Binary Packing Problem; Project Schedule Problem; Consumable Resource (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-540-69995-8_87

Ordering information: This item can be ordered from
http://www.springer.com/9783540699958

DOI: 10.1007/978-3-540-69995-8_87

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().