Zhang, Junxing, authorShestak, Vladimir Vladimirov, authorRaskey, Michael, authorPippin, Alan J., authorPichel, Ron, authorOltikar, Mohana, authorMehta, Ashish, authorLee, Panho, authorKrishnamurthy, Yogish G., authorHoriuchi, Aaron, authorGuru, Kumara, authorAydin, Mahir, authorAl-Otaibi, Mohammad, authorAli, Syed Amjad, authorMaciejewski, Anthony A., authorSiegel, Howard Jay, authorSugavanam, Prasanna V., authorIEEE, publisher2007-01-032007-01-032005Sugavanam, Prasanna V., et al., Processor Allocation for Tasks that is Robust Against Errors in Computation Time Estimates, 19th International Parallel and Distributed Processing Symposium: Proceedings, April 4-8, 2005, Denver, Colorado: 14 p.http://hdl.handle.net/10217/2451Heterogeneous computing systems composed of interconnected machines with varied computational capabilities often operate in environments where there may be sudden machine failures, higher than expected load, or inaccuracies in estimation of system parameters. Makespan (defined as the completion time for an entire set of tasks) is often the performance feature that is optimized in such systems. It is important that the makespan of a resource allocation (mapping) be robust against errors in task computation time estimates. The problem of optimally mapping tasks onto machines of a heterogeneous computing environment has been shown, in general, to be NP-complete. Therefore, heuristic techniques to find near optimal solutions to this mapping problem are required. The goal of this research is to find a static mapping of tasks so that the robustness of the desired system feature, makespan, is maximized against the errors in task execution time estimates. Seven heuristics to derive near-optimal solutions and an upper bound to this problem are presented and evaluated.born digitalproceedings (reports)eng©2005 IEEE.Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.computational complexitymultiprocessing systemsresource allocationText