معماری برای زمان بندی جریان کار تحت محدودیت های تخصیص منابع

Research on specification and scheduling of workflows has concentrated on temporal and causality constraints, which specify existence and order dependencies among tasks. However, another set of constraints that specify resource allocation is also equally important. The resources in a workflow environment are agents such as person, machine, software, etc. that execute the task. Execution of a task has a cost and this may vary depending on the resources allocated in order to execute that task. Resource allocation constraints define restrictions on how to allocate resources, and scheduling under resource allocation constraints provide proper resource allocation to tasks. In this work, we provide an architecture to specify and to schedule workflows under resource allocation constraints as well as under the temporal and causality constraints. A specification language with the ability to express resources and resource allocation constraints and a scheduler module that contains a constraint solver in order to find correct resource assignments are core and novel parts of this architecture.

Workflow is a collection of tasks organized to accomplish some business process. It also defines the order of task invocation or conditions under which task must be invoked, task synchronization, and information flow [1]. Patient treatment in a hospital, banking services, manufacturing and catalog ordering processes and many more activities in today's business life can be modeled as workflow. The nature of the tasks in a workflow may vary considerably. These tasks may be manual jobs or computer programs that execute on different platforms. A workflow management system (WFMS) provides a model and tools for specification, analysis, and execution of workflows. It forms a framework to capture the relations among the tasks (i.e., the business logic of the workflow), to gather the tasks with different nature and to automate the execution in such a way that it obeys the business logic. The correct definition and execution of the workflow means more quality and less cost for an establishment. For this reason, workflows have been an attractive research area. Surveys on the subject can be found in [1], [2], [3], [4], [5], [6] and [49]. Scheduling of workflows is a problem of finding a correct execution sequence for the workflow tasks, i.e., execution that obeys the constraints that embody the business logic of the workflow. Approaches in this area are typically based on temporal logic and specialized algebras [7], [8] and [9], Petri nets [10] and [11], and concurrent transaction logic and other logics for representing actions [12], [13], [14], [15] and [16]. Research on workflow scheduling has largely concentrated on temporal and causality constraints, which specify existence and order dependencies among the tasks. For instance, task 1 must execute before task 2 or if task 1 executes, task 2 must execute as well (also known as Klein's existence constraint [17]) are examples of temporal/causality constraints considered in [7], [9] and [15]. However, another set of constraints that specify resource allocation are equally important. Examples of resources in a workflow are agents such as person, machine, software, etc. that execute the task. Resource allocation constraints define restrictions on the resources of the workflow. Execution of a task has a cost, in terms of money, time etc., and this may vary depending on the resources allocated in order to execute the task. Although resource management has been recognized as an important aspect of a WFMS, most of the work has focused on modeling issues [2], [10] and [18] or agent behavior in workflow systems [19], [20] and [21] with little attention devoted to scheduling. Scheduling under resource allocation constraints include decisions on which resources to allocate and when to allocate them and thus provide proper resource allocation. It seems natural to include resource allocation constraints into the workflow specifications in the areas that require efficient scheduling in order to obtain fast responds to user's demands on the process’ budget, duration, etc. as in catalog ordering, manufacturing. Davulcu et al. [22] discusses about constraints that involve execution cost of tasks and that are used for modeling and reasoning of virtual enterprises modeled as workflows. These constraints may be seen as early version for resource allocation constraints. Simple resource allocation constraints are constraints like if task 1 is executed by some agent, task 2 should be executed by the same agent as well. Moreover, total cost <100 is an example of resource allocation constraints in a system where resource allocation to execute tasks has some associated cost values. Cost may consist of one or more of dimensions such as financial expenditure to fulfill the task by a given agent, the execution time, or the energy consumption, etc. Several resources may be available and qualified to perform the given task with different cost values. It is possible to group resources under roles and define hierarchical role structures. Most of the previous work on workflows concentrated on issues related to run-time check of the constraints. If a workflow is executed before it is verified, its constraints may be checked and a schedule might be obtained incrementally during the execution. However, a workflow specification might be unexecutable because of its incorrect design or conflicting constraints. At some point of the execution, if it is detected that the workflow cannot be completed because of design errors, some rollback operations might be needed before abandoning the execution of the workflow. Obviously, such cases cause waste of resources. Therefore, it is important to verify the given workflow specification, and this verification can be done by obtaining a feasible workflow schedule providing proper resource allocation. In this work, we present a workflow management system architecture that provides modules to model resources and resource allocation constraints and to find schedules fulfilling these constraints. In order to find schedules, constraint programming approach is used. That is, scheduler incorporates an off-the-shelf constraint solver to obtain a feasible schedule for the workflow satisfying both resource allocation and temporal/causality constraints. Operations research (OR) and constraint programming have been successfully used for problems such as job-shop scheduling, in which proper machine (i.e., resource) allocation constitutes an important part of the solution. (For more information on constraint programming, reader may refer to [23], [24], [25] and [26].) However, contrary to most OR problems, our goal is to find a feasible resource allocation rather than finding the optimal solution. A typical constraint solver is not sufficient for finding optimal solution. General algorithms for finding optimal solutions for problems which are specified in terms of constraints are usually not very efficient, and customized algorithms are needed for different classes of problems. This work can be extended to produce optimal solutions by incorporating such algorithms into the proposed system. However, for efficient scheduling, we consider finding any feasible solution that meets the constraints. The study of Senkul et al. [27] is another work that uses constraint programming for workflow scheduling under resource allocation constraint. In [27], a formal model for the problem is presented. In this work, we demonstrate the practicality of the ideas presented in [27], by a system that has a script language which constructs to model resources and resource allocation allocation constraints and that uses constraint solver as the core of the scheduler. This paper presents a system to schedule workflows under resource allocation constraints. Since the concentration of the paper is on pre-scheduling of workflows, concurrent workflows have not been considered. Indeed, at the very basic level the concurrency can be defined in our model by using the AND blocks.1 However, our approach does not support the scheduling of general concurrent workflows. The main contributions of this paper may be summarized as follows: • As a part of the architecture, we have developed a specification language that can model cost information for resources and specify resource allocation constraints, which is not provided by previous workflow definition languages. • The enactment service of the architecture contains a scheduler module, which incorporates a constraint solver. This module gets the workflow specification, which is translated into constraint language, and produces a schedule satisfying resource allocation constraints. This paper is organized as follows: In Section 2, the rationale and motivation behind scheduling workflows under resource allocation constraints are given through examples. In Section 3, workflow structure considered in this paper is explained. In Section 4, resource allocation constraints for workflows are explained. In Section 5, the architecture and the workflow specification in the proposed system is presented. In Section 6, the semantics of the specification language in terms of constraint language is given. Section 7 discusses the related work. Finally, a summary is given in the conclusion.

8. Conclusion This paper presents an architecture to model and schedule workflows with resource allocation constraints as well as with the traditional temporal/causality constraints. Current approaches for scheduling tasks in a workflow provide no mechanism to reason about the relative costs of schedules. Scheduling under resource allocation constraints provide decisions on the assignment of resources to tasks, as well as correct execution sequence of tasks. Hence, workflow schedules with desired execution cost level can be obtained. We use constraint programming to schedule workflows with resource allocation constraints. Workflow specification together with resource information and constraints, including both resource allocation and temporal/causality constraints, are translated to finite-domain constraints. For the implementation, constraint programming language Oz is used. The main contribution of this work is the proposed architecture which provides a specification language that can model resource information and resource allocation constraints, and a scheduler model that incorporates a constraint solver in order to find proper resource assignments. Although workflow processes are generally long-term activities, finding the schedule prior to the enactment of the process must be efficient. For most of the constraint problems, the aim is to find the optimal solution which requires search throughout the whole search space. However, our aim is to obtain a feasible solution to reduce the complexity of the problem. As a future work, the architecture can be extended with a special-purpose constraint solver in order to find solutions for our framework more efficiently. In our work scheduling of single workflow instances are handled. Pre-scheduling of concurrent workflows is also very interesting problem. For this purpose, first, the issue on how to specify the starting times of workflows, must be resolved. Then, our approach can be extended to determine the schedule of concurrent workflows with given starting times by maintaining additional temporal information in order to make the decisions for starting the executions of workflows. The schedule obtained must satisfy all the constraints and obey given starting times of concurrently executing workflows.