Robust Resource Allocations in Temporal Networks

Wolfram Wiesemann, Daniel Kuhn and Berc Rustem

No 20, Working Papers from COMISEF

Abstract: Temporal 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.

Keywords: Robust Optimisation; Temporal Networks; Resource Allocation Problem (search for similar items in EconPapers)
Pages: 29 pages
Date: 2009-11-06
New Economics Papers: this item is included in nep-net and nep-ppm
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://comisef.eu/files/wps020.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to comisef.eu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

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:com:wpaper:020

Access Statistics for this paper

More papers in Working Papers from COMISEF
Bibliographic data for series maintained by Anil Khuman ().