Improving the performance of time-constrained workflow processing

Abstract

Many workflow applications often have timing constraints such that each processing of a workflow needs to be finished within its deadline. There have been some works to improve the performance of time-constrained workflow processing such as predictive workflow scheduling. They, however, have not much considered appropriate analyses to determine the processing capacities for certain activities so that most workflow instances can satisfy the deadline. Our objective in this paper is to address a suitable scheme that can maximize the number of workflow instances satisfying the given deadline. We first present a method to find out a set of critical activities where a critical activity is the one whose delay of completion directly affects the overall processing time of a workflow. Since each critical activity must have a certain number of servers for the sufficient processing capacity, we then develop a method to determine the minimum. number of servers (MNS) for the critical activity such that this activity should be finished without delay for a given input arrival rate. We show through performance experiments that our method can be effectively utilized in practice. (C) 2001 Elsevier Science Inc. All rights reserved.