Budget-Deadline Constrained Workflow Planning for Admission Control in Market-Oriented Environments

There is an increasing interest for distributed computing technologies to be delivered through a market-based paradigm, which allows consumers to make use of and pay for services that meet certain Quality of Service requirements. In turn, providers receive income for successful provision of these services. In this paper, we assume an environment with multiple, heterogeneous resources, which provide services of different capabilities and of a different cost. Users want to make use of these services to execute a workflow application, within a certain deadline and budget. The problem considered in this paper is to find a plan for admission control. This allows providers to agree on constraints set by the user and allocate services for the execution of a workflow so that both deadline and budget constraints are met while account is also taken of the existing load (confirmed reservations) in the environment and the planning costs. A novel heuristic is proposed and evaluated using simulation with four different real-world workflow applications.