Robust Resource Allocations in Temporal Networks
AbstractTemporal networks describe workflows of time-consuming tasks whose processing order is constrained by precedence relations. In many cases, the durations of the network tasks can be influenced by the assignment of resources. This leads to the problem of selecting an ‘optimal’ resource allocation, where optimality is measured by network characteristics such as the makespan (i.e., the time required to complete all tasks). In this paper, we study a robust resource allocation problem where the functional relationship between task durations and resource assignments is uncertain, and the goal is to minimise the worst-case makespan. We show that this problem is generically NP-hard. We then develop convergent bounds for the optimal objective value, as well as feasible allocations whose objective values are bracketed by these bounds. Numerical results provide empirical support for the proposed method.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by COMISEF in its series Working Papers with number 020.
Length: 29 pages
Date of creation: 06 Nov 2009
Date of revision:
Contact details of provider:
Web page: http://www.comisef.eu
Robust Optimisation; Temporal Networks; Resource Allocation Problem;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2009-12-05 (All new papers)
- NEP-NET-2009-12-05 (Network Economics)
- NEP-PPM-2009-12-05 (Project, Program & Portfolio Management)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Anil Khuman).
If references are entirely missing, you can add them using this form.