Task Scheduling on Flow Networks with Temporal Uncertainty
Ping Hu, Meaghan Dellar, Chenyi Hu · 2007
This study was motivated by the large-scale evacuations and aftermath relief efforts caused by hurricanes Katrina and Rita in 2005. During large-scale natural disasters, both demands and uncertainties on transportation networks can be pushed to the extreme. The objective of this study is to optimally schedule tasks on a flow network that has temporal uncertainty modeled with interval valued time costs. We apply a fuzzy partial order relation for intervals to extend the Edmonds-Karp max-flow min-cost algorithm in this paper. Then, using the greedy approach, we propose task optimal schedule algorithms on a flow network with temporal uncertainties by utilizing its full capacity with the least possibility of delay in terms of the fuzzy partial order relations of intervals. In addition to the task scheduling algorithms, simple case studies are also provided in this paper