Business processes or workflows are often used to model enterprise applications [1–۴]. A workflow consists of multiple activities or tasks with precedence constraints. When we design workflow management/scheduling strategies, or evaluate the performance of workflow execution on target resources, it is often assumed that when a task is allocated to a resource, the resource will accept the task and start the execution once the processor becomes available. In reality, however, authorization policies may be deployed in the organizations and used to specify who is allowed to perform which tasks at what time. When these authorization schemes are taken into account, the situation can become complex. A number of authorization schemes have been presented in [5–۷]. The RBAC (Role Based Access Control) scheme is one of most popular authorization schemes. Under the RBAC scheme, users are assigned to certain roles while the roles are associated with prescribed permissions. Therefore, the organizations can control the users permissions through these roles. The following example in banking illustrates the effect of the RBAC scheme on the workflow execution [8]. A bank often uses a variety of computing applications to support its business; these applications may be deployed in a central resource pool (e.g., a cluster) of the bank. A workflow may consist of tasks such as credit data checks, automated signature approval, risk analysis and so on. In each task, a particular application has to be launched to perform the corresponding business functions. Under RBAC, an application may only be launched by certain users (i.e., the employees in the bank) assuming certain roles (i.e., job positions, such as branch manager or financial advisor). The following authorization constraints are often encountered in such scenarios: (1) Role constraints: A task may only be performed by a particular role; (2) Temporal constraints: A role or a user is only activated during certain time intervals (e.g., a staff member only works in certain hours of a day); (3) Separation of Duty constraints: If Task A is run by a role (or a user), then Task B must not be run by the same role (or user); (4) Binding of Duty constraints: If Task A is run by a role (or user), then Task B must be run by the same role (or user). Since a valid and activated role has to be assigned to a task before the task can start execution, these authorization constraints may delay the start of a task in a workflow, and consequently have negative impact on application performance (e.g. mean response time of workflows). Similar authorization constraints and situation also exist in other application domains such as healthcare systems [9], the manufacturing community [10,11], and other business processes [12,13].