Heuristic resource allocation algorithms for maximizing allowable workload in dynamic, distributed real-time systems

摘要: Summary form only given. We examine several heuristic algorithms for the maximum allowable workload (MAW) problem real-time systems with tasks having variable workloads. Briefly, concerns allocation of to m processors, where each task t is characterized by a function t.r(w) that gives running time in terms its (or input size) w. The objective find an processors so feasible (no misses deadline) when given w or smaller and maximized. This optimization uses robustness measure closely related MAIL (maximum increase load) metric recently proposed Gertphol et al. main contribution this paper comparison MAW-RMS problem. Hillclimbing, random search, simulated annealing, first-fit heuristics are presented evaluated via simulation. As we show here, greedy produces solutions reasonable quality compared other algorithms. In addition, demonstrate applicability our model air defense systems.