ABSTRACT. An analytical formulation is derived to predict the success of scheduling activities on discrete multiple resource time lines using sequential approaches. Success is defined in terms of the probability of scheduling a single activity and the number and cumulative duration of scheduled activities. The results are extended to include scheduling activities with flexible start times. The principal assumption is that the activity start times are randomly distributed over the available time in the time line.

1. INTRODUCTION

This analysis addresses a type of scheduling problem frequently referred to as activity scheduling. Each activity is assumed to use one of a set of equivalent resources. Each resource can be used to perform only one activity at any time. The activities are independent and have no predecessor relationships. Each activity has a specified duration and start time, although the possibility that the start time is flexible is also considered.

Scheduling becomes challenging when not all of the activities can be scheduled because of conflicting demand for the resources. The question then becomes: which activities get scheduled and at what times, and which do not get scheduled?

Ideally, an objective should be defined that can be used to identify the optimal schedule and select a scheduling approach that achieves or nearly achieves an optimal schedule as defined by that objective. A typical objective might consist of maximizing the sum of values assigned to each scheduled activity. If the value were the same for each activity, then maximizing the value is equivalent to maximizing the number of scheduled activities. If the value were proportional to the duration of the activity, then maximizing the value is equivalent to maximizing the total time scheduled.

Because optimally solving such problems is complex, most approaches do not attempt to achieve optimality directly and have resorted to a sequential scheduling approach (see Figure 1). A sequential scheduling approach typically begins by using heuristically determined metrics to order the activities by priority. It then considers each activity in priority order and attempts to find an available time for using one of the resources. Assuming such a time exists, a second heuristic approach determines the start time. If previously scheduled activities conflict with all possible start times, the activity is not scheduled. In either case, the next activity on the list is then considered for scheduling.

The principal method for evaluating scheduling approaches is to determine the extent to which the objective is met. Evaluation is typically accomplished by establishing benchmark problems and generating test schedules. The evaluation criteria generally include the fraction of activities and the fraction of activity time that gets scheduled. This paper provides an analytical technique for predicting scheduling success in these terms.

A closely related issue is the fraction of available resource time that gets scheduled. Providing resources is generally costly, and, before spending money to provide additional resource, managers want to be sure that the existing resources are being used efficiently to perform the specified activities.

The first part of this paper presents the derivation of the probability of a single additional activity being successfully scheduled on either a single or multiple resources. An iterative process is then defined to determine the overall probability of successfully scheduling any number of activities.

Next the benefits to improved scheduling success from start-time flexibility are included. Finally, the distribution of gaps remaining in the time line is discussed.

2. SINGLE-ACTIVITY SCHEDULING SUCCESS

Scheduling success probability is derived by considering an attempt to schedule a single additional activity on a resource time line that contains a number of activities already scheduled. Given a single, discrete, resource time line (see Figure 2) with n randomly scheduled activities at start times and with durations

(1)

such that

(2)

consider a new activity with duration and random start time . The new activity will not be scheduled successfully if its start time conflicts with any previously scheduled activity or if a previously scheduled activity has a start time that conflicts with the new activity .

Since is uncorrelated with any previously scheduled activity, the probability that it will not conflict with a previously scheduled activity is given by the fraction of the time line remaining unscheduled

(3)

where

= the length of the time line

and the remaining time is given by

(4)

The probability that no previously scheduled activity has a start time that conflicts with the new activity is determined by considering a compressed time line of length (see Figure 3), generated by removing the scheduled activity durations from the available time line. The previously scheduled activities appear with zero duration randomly distributed throughout the time line. For each of the n previously scheduled activities, the probability that start time will not conflict with the new activity is given by

(5)

under the assumption that

and (6)

to avoid any effects from the ends of the time line. Combining the probability that is not in conflict with any previously scheduled activity, with the probability that none of the are in conflict with the new activity, results in the probability that the new activity can be scheduled

(7)

In the limit that n becomes large while remains fixed

(8)

where

(9)

(10)

= average duration of scheduled activities

If each activity can be scheduled on any of m equivalent unconstrained resources, then becomes the probability that the new activity can be scheduled on each of the m resources. The probability of successfully scheduling an additional activity on any of the m resources is then

(11)

Figure 4 shows the probability of successfully scheduling a new activity of average duration as a function of the already scheduled load. For small values of L, the probability decreases as . For larger values of L, the exponential causes the probability to fall more rapidly. For a single resource, by the time L has reached 30 percent, the scheduling success for a new activity has fallen to 46 percent. Four equivalent resources are required to keep the single-activity scheduling success above 50 percent for 50 percent loading.

3. INTEGRATED SCHEDULING SUCCESS

Scheduling success integrated over all activities is determined by applying iteratively. Consider N activities with random start times to be scheduled on m equivalent resources. The first m activities can each be scheduled successfully without conflict, one activity on each resource. Therefore, the number of activities and the scheduled load are

(12)

(13)

For activities j=m+1,N, the steps are

1. Compute the probability to schedule activity j, given n(j-1) previously scheduled activities out of j-1 attempts

2. Update the number of activities scheduled out of
j attempts n(j)=n(j-1)+

3. Compute the scheduled load

(14)

The average scheduling success can then be computed as the ratio of the number of scheduled activities to the number of attempted activities

(15)

or as the ratio of the scheduled time to the attempted time

(16)

If all of the activities are of the same duration, then the two measures are identical. Figure 5 illustrates the integrated scheduling success when all activities are of the same duration. If the demand is for 50 percent of the available time on 4 resources, 90 percent of the activities will be scheduled successfully. With 2 resources, 79 percent will be scheduled successfully. If the demand is for 70 percent of the resources, the success for 4 resources drops to 79 percent and it drops to 69 percent for 2 resources.

4. START-TIME FLEXIBILITY

The activity start times for some scheduling problems are not fixed. Rather, they have flexibility such that they can be scheduled to start at any time between and + . The benefit of the start-time flexibility can be determined by considering an activity (see Figure 6) with start time that conflicts with a previously scheduled activity of duration , scheduled to start at time . If , then the conflict with activity i can be resolved by adjusting the new activity start time to . The probability that this resolution is possible is given by

(17)

for

(18)

For larger values of , the probability of resolving the conflict is 100 percent. The average probability for resolving a conflict with the new event start time is given by the product of the probability that the new activity conflicts with the previously scheduled activity i, multiplied by the probability that a conflict with activity i can be resolved, summed over all previously scheduled activities

(19)

where f is the normalized flexibility

(20)

The probability of successfully scheduling the new activity is determined by multiplying Lf by the probability that another activity will have been scheduled in conflict with the adjusted activity and by adding the result to the previously determined value of

(21)

Figure 7 shows the probability for successfully scheduling a new activity of flexibility f = 1 of average duration as a function of the already scheduled load. Because of the flexibility, this data shows significant improvement in scheduling success when compared with Figure 4. For a single resource scheduled at 30 percent of available time, the scheduling success for a new activity increases from 46 percent to 65 percent. With 4 equivalent resources, 50 percent scheduling success can be maintained up to a demand of 65 percent of available resources.

The improvement in integrated scheduling success is illustrated in Figure 8. Increasing flexibility from f= 0 to f = 0.5 increases the scheduling success by approximately 5 percent for high levels of demand. Increasing flexibility to f = 1 increases scheduling success by an additional 5 percent.

5. DURATION FLEXIBILITY

As previously indicated, the exponential term in dominates the linear term for larger values of scheduled load L. The impact of the exponential term can be partially reduced by first scheduling the larger duration activities and then scheduling the shorter duration activities.

Figure 9 illustrates scheduling success when the demand above 40 percent is divided into twice the number of activities, each activity of half the duration of the activities below 40 percent. This success is compared to scheduling success when all activities have the same duration. With the reduced-duration activities, scheduling success is increased by approximately 5 percent. In practical applications, durations of unschedulable activities can be reduced to improve scheduling success.

6. HIGHLY FLEXIBLE START TIMES

As the flexibility of start times increases, the probability of successfully scheduling an activity increases. For values of , conflicts of the new activity start time with a previously scheduled activity can always be resolved (see Figure 6) by delaying the new activity to start at the end of the conflicting activity. The linear term in the scheduling probability is eliminated, and the single resource success probability becomes

(22)

This probability is actually a lower bound. The new activity is also schedulable if the start time of a previously scheduled activity conflicts with the new activity and if .

For values of (for an average-duration activity , this value corresponds approximately to ), the success probability increases further, as illustrated in Figure 10. If the length of the first gap following the start time of the new activity is less than the duration of the new activity, , then the new activity will not be schedulable in that gap. This probability is given by

(23)

If the new activity is not schedulable in the first gap, then its start time can be delayed to the end of the next previously scheduled activity. The probability is identical that the gap following this activity is also too small in which to schedule the new activity. Consequently, the probability that the new activity will be schedulable in one of these two gaps is given by

(24)

As increases further, scheduling success continues to increase. Figure 11 illustrates the significant gain in scheduling success that accrues from this added flexibility for an average-duration activity. It also illustrates that, even with this amount of flexibility, it is difficult to successfully schedule beyond a demand of 60 percent of the resources.

This conclusion depends on the assumption that scheduled activities are placed randomly within their schedulable start-time flexibility. Techniques exist for selecting start times to optimize resource use. These techniques effectively reduce the size of small gaps and increase the size of large gaps, thereby improving scheduling success.

7. GAP SIZE DISTRIBUTION

The difficulty in scheduling more than 60 percent of the resources results from both the time line being heavily scheduled and the remaining gaps being too small for additional activities to be scheduled. This problem can be understood by determining the distribution of gap sizes.

The probability for an individual gap to have a length greater than value g can be determined by selecting the end, , of any scheduled activity and by considering the probability that no other activity is scheduled within gap g from this point. This probability is precisely the same probability derived earlier for scheduling an activity with a non-conflicting start time

(25)

The distribution of gap sizes (see Figure 12) is given by the probability of finding a gap between g and g+dg

(26)

As the resource becomes more heavily scheduled, the remaining gaps become significantly smaller than the average activity duration, making them unusable for scheduling average-duration activities. The amount of time T(g) remaining in gaps larger than g is given by

(27)

(28)

The ratios of T(g) to and are given by

(29)

and

(30)

which, in the case g=<d>, go to

(31)

(32)

Figure 13 illustrates the fraction of the time line remaining in gaps larger than the average activity duration as a function of scheduled load L. For example, when 50 percent of the time line has been scheduled, only 37 percent of it consists of gaps larger than an average-duration activity. When L reaches 70 percent, only 10 percent of the time line consists of gaps larger than an average-duration activity. The remaining 20 percent is in gaps that cannot be used to schedule activities of average or larger duration. The time in these gaps can be recovered by adjusting activity start times to reduce the size of small gaps and increase the size of large gaps.

8. CONCLUSION

This paper provides formulae to compute success for scheduling individual activities with start-time and duration flexibility on single or multiple resources. An iterative technique is presented for determining scheduling success integrated over all schedulable activities. It demonstrates the significant increase in scheduling success that can be achieved when scheduling flexible activities. It also provides a distribution of sizes of gaps remaining in the time line and demonstrates the dramatic decrease in time remaining in large gaps as scheduled time increases.

This analytical formulation can be used to calculate realistic estimates of scheduling success without actually developing schedules. Such estimates can be used for capacity planning or predicting scheduling success for varying combinations of activities and resources.