Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems


Share/Save/Bookmark

Möhring, R.H. and Schulz, A.S. and Stork, F. and Uetz, M.J. (1999) Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems. In: Algorithms (ESA 1999), 16-18 July 1999, Prague, Czech Republic.

[img]PDF
Restricted to UT campus only
: Request a copy
153Kb
Abstract:We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent costs and temporal constraints in the form of time windows, find a feasible schedule of minimum total cost. In fact, we show that any instance of this problem can be solved by a minimum cut computation in a certain directed graph.
We then discuss the performance of the proposed Lagrangian approach when applied to various types of resource-constrained project scheduling problems. An extensive computational study based on different established test beds in project scheduling shows that it can significantly improve upon the quality of other comparably fast computable lower bounds.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62242
Official URL:http://dx.doi.org/10.1007/3-540-48481-7_13
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page