Bin Packing Heuristics for the Multiple Workflow Scheduling Problem

Abstract

In the multiple workflow scheduling problem a set of workflows has to be scheduled concurrently onto system's available resources. Workflows exhibit different characteristics e.g., topological structure, size and computation-communication demands while they can have different or conflicting optimization goals. The above results in scheduling decisions of high complexity which in turn may adversely affect the quality of solutions. In this paper we present a fast scheduling algorithm (i.e., the Multiple Workflow Complementary Packing algorithm, MWCP algorithm) for the management of multiple workflows. MWCP combines list scheduling methodologies and Bin Packing techniques to minimize the overall execution time of the workflows. For each workflow the scheduler decides on the best policy considering only the information provided by the workflow in question. We evaluate the performance of the proposed algorithm using real workflow applications being tested under different system heterogeneity levels. Results indicate that performance gains over existing studies are up to 9% while different workflow characteristics reveal different trade-offs on the performance of MWCP. © 2021 ACM.