Activity Scheduling Queues

Experiment in the previous section showed that there is still a difference between choosing appropriate resource for an activity and actual allocation of such resource. Activities that need to wait for a resource becoming available can heap one over another and when the resource finally becomes available, the Coordination model non-deterministically starts one of these activities with the available resource. When this happens, unavailable time of the allocated resource changes accordingly with the duration of the currently started activity. This can have an important impact on the third allocation strategy question for the remaining activities that were waiting for the allocated resource as well – other suitable resources can become available sooner than the previously chosen resource or they can finish the activity sooner considering their productivity. This means that resource assignment for the remaining activities has to be reconsidered and it can lead to a very similar situation of activity heaping for the second best resource. This mechanism can negatively influence the duration of the

Figure 5.12: Process Waiting Times for Strategies 1a(80%),2a,3a and 1a(80%),2a,3b

process (as shown in the example in previous section) because the process waits for assignment reconsideration even though the final resource is already available before the reconsideration happens.

This problem can be solved by scheduling activities when the best resource is unavailable.

All further allocations will take already scheduled activities into consideration when choosing the best resource for the activity. For example, if some worker is currently performing activity A and is assigned as the best resource for activity B, then B is scheduled to be the next activity that this worker will execute. Then if assignment for activity C is considered, the availability of this worker will be evaluated from the end of the scheduled activity B, not from the end of the current activity A. If even then this worker is assigned as the best resource for activity C, this activity will also be scheduled for this worker to be executed after activity B is finished. This leads to introduction of scheduling queues for each worker in the model.

The previous example assumed that the scheduling queue for the worker is behaving as a standard first in, first out (FIFO) queue (also called first come, first served (FCFS)), but different scheduling techniques can be used in the queue, such as shortest processing time (SPT), longest processing time (LPT), earliest due date (DD), etc. (for more information about individual techniques see [80]). In discrete-event simulations of business processes, priority queues are more useful than basic scheduling techniques because concurrent process instances and even individual activities in these instances can have different priorities.

Activities will then be scheduled in this queue based on their priority and the priority of their process instance with higher combined priorities being put at the front of the queue and executed before the lower priorities. Activities with the same priority will be scheduled by the standard first in, first out technique.

5.4.6.1 Activity Priority Extension of Coordination Model

To introduce priority queues to the Coordination model, activity priorities have to be defined first as they are not yet present in the model. Activity priority extension is simple and straightforward as priority with possible values of low, medium or high will be assigned to each activity in the process. This is formally defined in Definition 5.28.

Definition 5.28:

Coordination model system with activity priority (CMSAP) is defined as a tuple CMSAP = (CMSPAS, activityPriority) where:

• CMSPAS is a Coordination model system with productivity and allocation strategies as defined in Definition 5.27 and

• activityPriority: AN → {low, medium, high} (AN is a set of activity nodes defined in Definition 3.6) is a function that specifies a priority for every activity node in the model. Priority is defined for each activity node to differentiate the priority of different nodes of the same activity based on the context of their involvement in the process.

5.4.6.2 Combination of Activity and Process Instance Priorities

To correctly use the priority queue, activity allocations that will be managed in the queue have to define their priority accordingly to the priority of the whole process instance combined with the individual priority of the activity. The combination approach used in this thesis is inspired by the calculation of incident priority in IT Infrastructure Library (ITIL) process framework [81] that is done by combining impact and urgency of the incident. This combination is defined using priority table or matrix in which rows describe individual levels

for the appropriate combination of impact and urgency. I have adapted this table to the purposes of combining activity and process instance priorities and it is shown in Table 5.4.

Process Instance Priority

low medium high

Activity Priority

low 1 2 3

medium 2 3 4

high 3 4 5

Table 5.4: Combination of Activity and Process Instance Priority

Formal definition of this combination function is stated in Definition 5.29.

Definition 5.29:

Given priorityValue: {low, medium, high} → ℕ is a function that assigns numerical value for each possible priority value and is defined as:

priorityValue(p) =

{

then combinePriority: {low, medium, high} × {low, medium, high} → ℕ is a function that combines activity priority ap Î {low, medium, high} with process instance priority pip Î {low, medium, high} and is defined as:

combinedPriority(ap , pip) = priorityValue(ap) + priorityValue(pip) −1 (5.57) 5.4.6.3 Activity Scheduling Queue Extension of Coordination Model

With the definition of activity priority and the technique used for priority combination, everything is in place to enable activity scheduling queue extension of the model. Each shared resource in the Coordination model will therefore be extended with a priority queue and all allocations in the process will be planned using these queues. This is stated in Definition 5.30.

Definition 5.30:

Coordination model system with activity scheduling queues (CMSASQ) is defined as a tuple CMSASQ = (CMSAP, ASQ) where:

• CMSAP is a Coordination model system with activity priority as defined in Definition 5.28 and

• ASQ = (SQ, schedulingQueue) is a tuple that specifies activity scheduling queues in the model, where:

◦ SQ is a finite set of scheduling queues in the model and

◦ schedulingQueue: SR → SQ (SR is a set of shared resources defined in Definition 3.21) is a function that assigns one scheduling queue to every shared resource in the model. Each scheduling queue is assigned to exactly one shared resource:

∀sq∈SQ ∃!sr ∈SR

[

]

Every allocation aa Î AA assigned to any shared resource sr Î SR will be added to its queue schedulingQueue(sr) Î SQ as the last allocation with combined priority cpa,cpi Î ℕ evaluated as:

cp_{a ,cpi}=combinePriority

(

parameterSetPriority(processInstanceParameterSet(cpi))) ^(5.59) where cpi Î PI is the current process instance of allocation aa. Duration of allocation aa will be evaluated from the probability distribution modified by the resource's productivity as specified in section 5.4.2 Introducing Productivity into Coordination Model.

Simulation and allocation behaviour of the model will change in the following ways:

• When the resource becomes available, the scheduled activity at the front of the queue will be executed and removed from the queue.

• When the earliest available time of the resource is evaluated for allocation with combined priority p, ending time of the last allocation with combined priority p in the queue will be used. If no allocations with the checked priority are present in the queue, one step higher priority is checked and so on. If no allocations with priority p or higher are present in the queue, ending time of the currently executed allocation is used. If the allocation does not currently perform any activity, it is currently available.

• If there are any allocations with lower priorities than a newly added allocation in the queue, all these allocations have to be rescheduled or reassigned to other resources if the allocation strategy chooses another resource for the allocation.

• If an allocation with higher priority than currently executed activity is added to the queue, it does not interrupt the currently executed activity, as Coordination model is not able to stop the running activity and resume it later. Such high priority activity will be performed after the current activity finishes if it is not preceded by another activity with even higher priority.

• If several allocations are needed to start the execution of one activity, all such allocations have to be scheduled for the same time and will be scheduled for the latest time one of the allocated resources becomes available. This can create gaps in the individual schedules that can be filled by other shorter activities if able.