Abstract:
A scheduling system is disclosed for scheduling tasks for fulfilling a series of service requests. When each service request is received, a determination is made as to the amount of resources a task requires to provide the requested service. Further, a preferred time within which to perform the task is obtained from the requestor of the service request. For each service request, data for the estimated amount of resources and the preferred time are supplied, on a first-come-first-serve basis, to a scheduling component for solving a combinatorial optimization model which efficiently allocates a predetermined amount of resources for each time slot in a scheduling period by rearranging tasks for service requests previously received. The scheduling component provides for a service requestor, without regard to subsequently received service requests, a service time in which to perform the task for the requested service substantially immediately after the service request is made. Whenever possible, the service time coincides with the preferred time. Each previously received service request will have its related task performed within the service time provided to the requestor of the service request. The scheduling system is particularly useful in scheduling technician time for service calls received by customer representatives in the telecommunication and utility industries.

Description:
FIELD OF THE INVENTION 
     The present invention relates to scheduling service providers to perform customer service requests and in particular to responding immediately to each customer service request with a time interval in which to perform the service while also being able to optimize the utilization of the service providers. 
     BACKGROUND OF THE INVENTION 
     In many service related industries a customer service request necessitates the scheduling of an appointment for a service provider to perform the requested service. Providing service schedules for large numbers of service requests and relatively large numbers of service providers is typically difficult to accomplish in a cost effective manner. That is, it is difficult to arrange service appointments providing high utilization of service provider personnel without incurring inordinate scheduling time delays and/or costs. 
     In some service industries there are additional difficulties in scheduling in that coordination must be made with each customer to, for example, arrange access to the customer&#39;s premises. Such coordination is particularly prevalent in utility and telecommunication industries. It is typical when such coordination is required, that each customer requesting service is given a service time interval within which the customer&#39;s requested service is to be performed. Thus, a customer is required to be accessible during the service time interval for a service provider to perform the requested service. 
     It is common practice in industries providing such service time intervals in response to customer service requests that service time intervals are typically larger than the estimated time to perform the requested service. This strategy provides additional flexibility in scheduling service providers in that there is allowance or flexibility for schedule changes without the need for additional contacts with customers and rearrangement of service appointments. However, to provide customer satisfaction, it is also preferred that the service time intervals agree or overlap as much as possible with preferred service request times given by customers. Thus, accomplishing the two goals of effectively scheduling service providers and also accommodating the preferred service times given by customers becomes even more difficult. 
     Previous attempts to satisfy both the goal of efficient scheduling for service providers and the goal of accommodating customer preferred service times have focused on obtaining all or substantially all customer service requests before formulating a schedule for service providers. Thus, customers with service requests are typically contacted at some later time after the initial customer request and provided with a time which may or may not correspond with any customer preferred time interval for the service request. This strategy, however, has the disadvantages of: (a) increasing scheduling overhead in that customers must be re-contacted which may involve multiple contact attempts for a single service request; (b) necessitating further inconvenience for customers requesting service; and (c) typically requiring an early cut off date wherein no further customer requests are taken for certain dates not yet having service provider schedules. 
     Thus, it would be advantageous to have a scheduling capability wherein there is a service time interval provided to each customer during the initial contact when the customer requests service, wherein each service time interval substantially overlaps a customer preferred service time, and wherein the provided service time intervals obtained can be used to efficiently schedule service providers. 
     SUMMARY OF THE INVENTION 
     In a general context, the present invention is a scheduling tool for scheduling resources to perform requested tasks wherein the entire set of tasks to be scheduled is not known prior to commencement of a &#34;scheduling&#34; of a particular task. In particular, tasks are allocated resources in the order that they are received. In one preferred embodiment of the present invention, hereinafter denoted as a &#34;scheduler,&#34; tasks to satisfy customer service requests are scheduled according to a predetermined forecast of available resources. During a customer&#39;s initial service request contact, a customer preferred service time interval in which the service request task is to be performed is determined (i.e., as specified by the customer). The scheduler uses this preferred interval to immediately: either inform the customer that the required service task will be performed in the customer&#39;s preferred time interval or, if it&#39;s impossible, provide the customer with a specified service time when the task will be performed. When a specific time is provided, resources are &#34;assigned&#34; to perform the service requested task; that is, the resources are allocated to the task and they are excluded from any further resource rearranging activities. Thus, the resources allocated for this particular task cannot be reallocated to a different task at some later time. Alternatively, if a service time interval is provided, then there is typically more time within the service time interval than necessary to perform the task. That is, the service time interval has &#34;time flexibility.&#34; Such time flexibility allows the task to be shifted within its service time interval as other tasks for subsequent service requests are subsequently scheduled, although the initial task remains scheduled for performance within the service time interval given to the customer. Thus, instead of assigning resources for a particular task as when a specific time is provided, in the present invention resources are merely allocated such that they may be reallocated to another task if the initial task is shifted to a different time and allocated other resources within its specified service time interval. 
     Thus, in this preferred embodiment, it is an aspect of the present invention to provide for the efficient allocation of resources wherein the resources are service provider time such that for each customer service request generating a service time interval, the actual scheduling of a service provider may be performed at a later date than when the initial customer service request is received within, however, the constraints of the previously specified service time interval. 
     It is also an aspect of the scheduler of the present invention to provide the above capabilities by using a resource allocation model, hereinafter denoted the Daily Floater Model (DFM), belonging to the class of combinatorial optimization models which have been developed for scheduling problems. That is, the DFM includes: (a) an optimization function relating to the efficiency of utilization of service providers; and (b) a set of constraints, the constraints defining scheduling criteria such as, for example, the constraints that there is at most one service start time per service appointment or constraints insuring that for every work hour the number of service providers assigned for services does not exceed the total number of available service providers according to the predetermined forecast. The DFM attempts to satisfy the one or more sets of constraints while simultaneously determining an optimal or extreme value for the optimization function. In one preferred embodiment, the optimization function provides values related to the amount of unassigned and unallocated service provider time. Therefore, in this case, the DFM is used to minimize the value of the optimization function while satisfying the one or more sets of constraints provided. 
     It is a further aspect of the present invention to use DFM scheduling models for concurrently constructing schedules for each of a plurality of scheduling time periods (e.g., days or weeks) where the resources are known or forecasted for each such time period and further to schedule service requests which require a plurality of such time periods by decomposing these requests into a plurality of shorter service requests wherein each shorter service request may be performed within a single scheduling time period. 
     It is a further aspect of the present invention that no additional contact with a customer, prior to performing the service requested, is required. Thus, for tasks having time flexibility, the present invention requires the DFM models to honor each service time period supplied to a customer, thus insuring that customers do not have to be contacted to reschedule service times. 
     Other features and benefits of the present invention will become apparent from the accompanying figures and the detailed description following hereinafter. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flowchart providing, at a high level, the steps performed when a customer service request is received by a customer service representative. 
     FIG. 2A is a first part of a flowchart of the steps performed by the present invention when determining a time within which a task to fulfill a service request is to be performed. 
     FIG. 2B is a second part of the flowchart having FIG. 2A as a first part. 
     FIG. 2C is a third part of the flowchart having FIG. 2A as a first part. 
     FIG. 2D is a fourth part of the flow chart having FIG. 2A as a first part. 
     FIG. 2E is a fifth part of the flow chart having FIG. 2A as the first part. 
     FIG. 3 is a flowchart of the steps performed when an appointment is provided for each task in each of one or more scheduling periods (e.g., days). 
    
    
     DETAILED DESCRIPTION 
     The scheduler of the present invention is used to solve problems which differ significantly from traditional scheduling problems. In traditional prior art scheduling problems, the set of tasks (equivalently jobs, requests, etc.) to be scheduled is given or provided before any scheduling is performed. Consequently, a mathematical model describing the constraints of a traditional scheduling problem, such as available resources and feasible time windows to satisfy the requests, is solved only once and the resulting solution provides an optimal schedule for the tasks. 
     Regarding the scheduler of the present invention, however, requested tasks are provided to the present invention sequentially and the scheduler is required to respond in real time with a service interval within which each requested task can be performed. Thus, when a new task is requested, the present invention dynamically attempts to rearrange previously entered tasks to make efficient use of the resources available to perform all tasks and at the same time satisfy time constraints that may be associated with each task. 
     In one preferred embodiment and use of the present invention, the scheduler includes a software tool for scheduling appointments of technicians required to carry out, for instance, repair and installation tasks requested by the customers of a telephone company. In particular, customers typically phone in service requests to company representatives who may, in turn, activate the scheduler of the present invention via, for example, a data entry device, and provide the customer, substantially immediately, with information regarding the time frame within which the service request may be satisfied. To accomplish both the immediate feedback to a customer and at the same time efficiently allocate resources (i.e., technician time), the scheduler retains information regarding time flexibility in performing the service request tasks. More precisely, whenever the time interval within which a task is to be done is sufficiently greater than the estimated time to accomplish the task (i.e., time flexibility), then specifying the exact starting time for performing the service request task is delayed so that such delays may be used in allowing tasks for additional future service requests to be performed within the same scheduling period (e.g., a day or a week). 
     In this preferred embodiment, when the scheduler of the present invention is activated by a customer service representative, the customer service representative determines at least an estimation as to the time required to perform the requested task and preferred times within which the task may be performed. In particular, a preferred starting day, a preferred starting time within the day, a preferred last day by which completion of the task last is to be accomplished, and a preferred time for completion within the last day are solicited from the customer. Thus, based on this information and information regarding the resources (i.e., technician time) available, the scheduler generates a time interval for accomplishing the task which may be supplied immediately to the customer. In supplying this time interval to the customer, the scheduler generates, whenever possible, a time to perform the service request task in accordance with the customer supplied time preferences. However, if the customer preferred time interval cannot be accommodated due to previous customer service requests, then an alternative appointment time may be provided to the customer wherein the alternative time is relatively close to the customer preferred time interval. For example, consider as a simple case, the scheduling of a single technician&#39;s time for a scheduling period of two consecutive days. If a first service request is received from a first customer having a preferred starting time of 8 a.m. on the first day, a preferred completion time of 5 p.m. on the first day, an estimated task duration of three hours, and there are no tasks scheduled for these two days, then the task (hereinafter denoted the first task) for this first service request may be tentatively scheduled for 8 a.m. of the first day and the service time interval provided to the first customer is the preferred time interval. Subsequently, if a second service request is received having a preferred starting time of 9 a.m. on the first day, a preferred completion time of 11 a.m. on the first day, and an estimated task duration of one hour, then since the first task can be shifted and still remain within its service time interval previously provided to the first customer, the first task may be shifted to start, for example, at 11:30 a.m. on the first day, thereby allowing the preferred time interval for the second service request to be accepted as the service time interval due to the shifting of the first task. Thus, this second service time interval is provided to the customer who supplied the second service request. Subsequently, if a third service request is received having a preferred starting time of 1 p.m. on the first day, a preferred completion time of 5 p.m. on the first day and an estimated task duration of four hours, then this preferred time is not accepted as the service time interval since no shifting of the first two entered tasks within their service time intervals will allow the task for this third service request to be performed within its preferred time interval. Thus, the task for this third service request may be, with the requesting customer acceptance, provided with a service time interval of 1 p.m. on the second day to 5 p.m. on the second day. 
     Based upon the foregoing, it will be appreciated that the present invention effectively generates a new schedule on each new customer service request. That is, in those cases where a time interval is provided to previous customers for the relevant time period (e.g., a day) and a new service request is taken for the same time period, resources will actually be allocated within each of the various and previously specified time intervals when generating or attempting to generate a time interval to be provided to the new customer on the new service request. 
     A high level flowchart describing the interaction between the customer and the customer service representative is given in the flowchart of FIG. 1. However, before proceeding with a detailed discussion of the scheduler and the flowchart of FIGS. 2A-2E which embodies the scheduler, a discussion of the following data structures is necessary. 
     (1.1) r: an integer parameter, r identifies a (service request) task by number, r=1, 2, . . . , R. For simplicity, it is assumed that each task r is performed within a single day. This, however, is not a restriction of the present invention in that, for example, as one skilled in the art will recognize, tasks requiring multiple days may be decomposed and portions scheduled one day at a time. 
     (1.2) Preferred customer task completion interval parameters: 
     (a) PS r  (d): the customer preferred earliest start day for performing the service request task r; 
     (b) PS r  (t): the preferred earliest start time within PS r  (d) for performing the service request task r. Note that each day is partitioned into a predetermined number of time slots for designating times within a day such that successive slot times are identified by positive integers. Thus, in one preferred embodiment, each time slot corresponds to half an hour and the time slots for a day are identified with the integers: 0, 1, 2, . . . , 15 wherein 0 is the first time slot of the day and 15 is the last time slot of the day. For simplicity, it is assumed there are T time slots per day. Thus, T+1 denotes the end of the day; 
     (c) PC r  (d): the latest preferred completion day for the service request task r; 
     (d) PC r  (t): the preferred latest completion time slot within PC r  (d) for the service request task r. 
     (1.3) Parameters used by the scheduler for specifying the current time interval within which a task may be performed: 
     (a) CS r  (d): the current value used by the scheduler as the earliest start day for task r; 
     (b) CS r  (t): the current value used by the scheduler as the earliest starting time slot within CS r  (d); 
     (c) CC r  (d): the current value used by the scheduler as the completion day for task r; 
     (d) CC r  (t): the current value used by the scheduler as the latest completion time slot for the task r within CS r  (d). 
     (1.4) T r  : the estimated time (i.e., time slots) required to perform the task r. 
     (1.5) N t  : the number of resources available for a time slot t within a predetermined day. 
     (1.6) D: the last day for which resources are forecasted; i.e., the last day for which N t  is defined for each time slot t=1, 2, . . . , T. 
     (1.7) DFM(d): the data structures and procedures defining the daily floater model (DFM) for day d. ##EQU1## (1.9) x t  (d) or simply x t  when unambiguous: the number of resources, for a predetermined day d, not allocated to tasks at time slot t, t=1, 2, . . . , T. 
     (1.10) Δ 1  : the value used in determining whether a task has time flexibility or not; i.e., if [the number of time slots between PC r  (t) on PC r  (d) and PS r  (t) on PS r  (d)]≦Δ 1 , then the task r has no time flexibility. 
     (1.11) Δ 2  : a value used in determining whether or not spare resources remain available for a predetermined day; i.e., if ##EQU2## then (and only then) is it considered that there are no spare resources on the day to which the summation of x t  &#39;s relate. 
     An important component of the present invention is the resource allocation model, DFM, which can now be described in terms of the above defined data structures. The DFM is a mathematical model for scheduling the resources, one scheduling period (e.g. a day) at a time, according to customer service requests received. The model includes an objective function to be minimized (maximized) and, in addition, a number of constraints which must be simultaneously satisfied. At a high level, the DFM preferably minimizes the number of unallocated resources for a day while simultaneously providing a specific starting time for each task r=1, 2, . . . , R, wherein the starting time is not earlier than the customer preferred starting time and such that the task r may be completed within the customer preferred interval. Further, there are DFM constraints requiring that the resources allocated for a given time slot not exceed N t  for each time slot of each day. 
     The DFM is characterized, for example, for a predetermined day, by the following expressions: 
     (2.1) the objective (or equivalently optimization) function: minimize ##EQU3## subject to the following constraints: ##EQU4## From the definitions of CS r  (t), CC r  (t) and T r  it follows (2.6) x rt  =0 for t&lt;CS r  (t) and for t&gt;CC r  (t)-T r  +1. 
     Referring to the expressions (2.1) through (2.6) above, (2.1) minimizes the total number of spare resources for the day to which the model applies. The constraints provided in (2.2) express the logical requirement that each service request task can be assigned exactly one starting time. The constraints of (2.3) express the requirements that at each time slot t the number of resources having been allocated and/or assigned to tasks to be performed during the time slot cannot exceed the available number of resources. Further note that constraints (2.4) and (2.5) along with the fact that N t  are integers imply that x t  are non-negative integers. Thus, any feasible solution to the DFM above is an integer valued. 
     As an aside, it is worthwhile to note that a novel aspect of the objective function (2.1) above is that for all feasible solutions to the DFM above, the objective function yields the same value; that is, ##EQU5## Thus, solving the combinatorial problem presented by the DFM expressions above is equivalent to searching for an arbitrary solution to the system (2.2)-(2.6). Thus, based on this observation, any optimization procedure used in solving the DFM above can be stopped after finding the first integer feasible solution. 
     Also note that the objective function (2.1) above can be replaced by other objective functions to express alternative requirements when scheduling tasks. For example, consider the following objective function: ##EQU6## where time slots t are assigned priorities P t . In this case, the optimal solution to this modified DFM maximizes the sum of priorities of tasks scheduled in specific hours of the day. Further, the modified DFM provided here may be useful for increasing in the generated schedule the number of requests with high priorities assigned to early morning hours. Thus, it is an important aspect of the present invention that various objective functions can be used with the constraints (2.2)-(2.6). Thus, the set of feasible solutions remains unchanged but some feasible solutions are now &#34;better&#34; than others. 
     Commencing now with the description of the steps of FIGS. 2A-2E, in step 100, a determination is made as to whether the scheduler of the present invention is to be initialized or not. In particular, certain data structures have their values retained between executions of the scheduler once it has been initialized. For instance, all values of x t  (d) may be retained from previous executions of the scheduler. However, if initialization is desired, then in step 104 the number of unassigned resources for each time slot for each day through the forecasted number of days D is initialized with the number of resources that may be provided for tasks. That is, x t  (d) is assigned the value N t , d=1, 2, . . . , D, and t=1, 2, . . . , T. Regardless, however, of the path taken from step 100, step 108 is encountered wherein the scheduler waits for a service request to be input. Once such a request is input, step 112 is performed wherein the following values are determined relating to the task r which is to be performed to satisfy the service request: (a) the duration, T r , of the task r; (b) a preferred time interval in which to perform the task r including an earliest preferred start day PS r  (d); a preferred earliest start time PS r  (t); a latest preferred completion day PC r  (d); and a latest preferred completion time PC r  (t). 
     Subsequently, in step 116 a determination is made as to whether the preferred time interval has at least one day where there are forecasted resources. If this is not the case, then step 120 is encountered wherein the service request for r is accepted and the task r is put on a list of tasks to be scheduled when resources are forecast for at least the first day of the preferred time interval for r. Subsequently, flow of control is transferred to step 108 to wait for a next service request. 
     Alternatively, if in step 116 the preferred interval for task r has at least one day with forecasted resources, then step 124 is encountered wherein the current start day CS r  (d), the current start time CS r  (t), the current completion day CC r  (d) and the current completion time CC r  (t) are each assigned the value of the related preferred input parameter associated with the preferred time interval data determined in step 112. Following this step, in step 128, a record corresponding to the task r is entered into the daily floater model for the current start day CS r  (d). Note that for simplicity r will be used to identify both the task and its related record. Further note that since the actual time for performing the task r can in some cases be changed when allocating resources to a subsequent task, the record r includes at least fields having the values CS r  (d), CS r  (t), CC r  (d), CC r  (t), PS r  (d), PS r  (t), PC r  (d) and PC r  (t). Subsequently, in step 132 a determination is made as to whether the preferred time interval is within a single day. Assuming an affirmative answer results in step 132, step 136 is encountered wherein a determination is made as to whether there are sufficient unassigned resources within the current starting day to complete the task r. If this rather primitive test is not satisfied, then there may be one or more iterations of the loop consisting of the eight steps from step 136 through step 160 wherein the task r is moved to a subsequent day, as will be discussed below, in an attempt to satisfy the test of step 136. 
     Alternatively, if in step 136 there are sufficient resources in CS r  (d), then step 164 is encountered. In this later step, a determination is made as to whether there is no time flexibility within the current time interval and also as to whether there are sufficient unallocated resources within CS r  (d) after CS r  (t) to perform r. In particular, if there is no time flexibility but there are sufficient resources, then step 168 is encountered wherein resources are assigned and a specific time is determined for the task; i.e., resources for task r are assigned and a message is output indicating that the service request has been accepted and that the task r will be performed in the start of the current time interval. Following this step, step 172 is performed wherein the number of unallocated resources is decreased for those time slots of the current service start day CS r  (d) having resources assigned in step 168. Further, the task r is removed from DFM(CS r  (d)). 
     Subsequently, in step 176, a determination is made as to whether there are further resources to allocate for the day CS r  (d). If so, then nothing further remains to be done and control is transferred back to step 108 to wait for another service request. Alternatively, if substantially all resources are allocated for this particular day, then step 180 is encountered wherein any tasks remaining within the DFM(CS r  (d)) are assigned resources. That is, those tasks which have had resources allocated to them within their respective current intervals, but have not had resources assigned for specific times are now assigned resources. Subsequently, in step 184 since substantially all resources for CS r  (d) have been assigned, DFM(CS r  (d)) is excluded from being considered for further tasks. Following this step, step 108 is again encountered and the program for FIG. 1 waits for a new input service request. 
     Returning now to step 164, if the test at this step is negative then either (a) there is time flexibility within the current time interval for the task r, or (b) there are insufficient unallocated resources within the current time interval for r to perform r. However, note that from step 136 there are sufficient unallocated resources within the current starting day for r. Therefore, control is transferred to step 188 wherein any time flexibility in the current time interval for r and other tasks also in DFM(CS r  (d)) are used in an attempt to rearrange the current starting times for r with the other tasks in an attempt to fulfill each task&#39;s requirement for allocated resources and thereby provide a consistent model (i.e., tentative schedule) for all the tasks. Note that an important aspect of the present invention involves the high computational efficiency of this step. It is believed that for substantially all real life service request sequences and for reasonable numbers of resources (e.g., ≦1000), step 188 can be solved in approximately 0.01 seconds of computer time on a Sun Sparc Workstation. This can be explained as follows. DFM is an integer programming model. It&#39;s constraints possess a special property being facets of integer polyhedron (2.2)-(2.6) as described in the following references: 
     [1] George L. Nemhauser, Laurence A. Woolsey, &#34;Integer and Combinatorial Optimization&#34;, JOHN WILEY &amp; SONS, 1988, 763pp. 
     [2] Youngho Lee and Hanif D. Sherali, &#34;Unrelated Machine Scheduling with Time-Window and Machine-Downtime Constraints&#34;, Annals of Operations Research, vol 50, 339-365,1994. 
     [3] Hanif D. Sherali and Youngho Lee, &#34;Sequential and simultaneous lifting of minimal cover inequalities for GOB constrained knapsack polytopes&#34;, to appear in SIAM Journal on Discrete Mathematics, 1995. 
     This means that solving the system (2.2)-(2.6) with integrality requirements (2.4) excluded, which is easy because it is equivalent to solving a linear programming problem, in many cases leads to integer solution thus providing extremely fast solution to the considered combinatorial problem. 
     Following this step, in step 192, a determination is made as to whether the daily floater model from step 188 was able to allocate appropriate resources to all tasks currently requesting allocations on the day, CS r  (d). If no such consistent model for DFM(CS r  (d)) is obtained, then some portion of the seven steps 140-160 are performed wherein some portion of the current time interval for the task r is at least determined for modification in preparation for allocating resources for r on a day when a consistent daily floater model may be obtained. Alternatively, if in step 192 a consistent model is obtained, then in step 196 a determination is made as to whether the current day, CS r  (d), precedes the last day of the preferred interval. If the results of this determination is negative, then in step 200 a determination is made as to whether the task r is presently scheduled to be completed within the preferred time interval on the last day. If so, then the step 204 is performed wherein a message is output indicating that task r will be performed in the preferred time interval. Note that the step 204 is also performed when leaving step 196 via the positive branch. 
     Alternatively, if step 200 results in a determination that task r will not be completed within the preferred time interval on the last day, then step 208 is performed wherein resources are assigned for the task r and a message is output indicating that r will be performed on CS r  (d) between CS r  (t) and CC r  (t) (note, that CS r  (t)&lt;=CC r  (t) if this step is performed). Subsequently, in step 212, DFM(CS r  (d)) is updated. That is, the number of free resources for this day is decreased for the time slots for which the task r is to be performed. Further, r is now removed from DFM(CS r  (d)) since an exact time for performing r has been output thereby forbidding further changes to the resources assigned to r. Following this step, step 176 is again encountered. In fact, step 176 is encountered regardless of the path taken from step 196. Thus, as discussed above, a determination is made in step 176 as to whether there are further resources which may be allocated for the day CS r  (d) and, if not, then in steps 180 and 184 the remaining tasks in DFM(CS r  (d)) are assigned and this model is excluded from being considered for further tasks. Thus, as the flow of control from step 176 demonstrates, step 108 is subsequently performed wherein the program of FIGS. 2A-2E waits for another service request input. 
     Returning now to step 132, if the preferred time interval is not within a single day, as has been assumed in the discussion above, then the negative branch from this step is taken wherein step 216 is encountered. In this step a determination is made as to whether task r is able to be completed in the first day of the multi-day preferred interval if r is started at CS r  (t). That is, a determination is made as to whether there are sufficient time slots T r  remaining in the first day beyond CS r  (t) to complete the task r. If so, then step 220 is performed wherein the current completion time is assigned to the end of the day. Subsequently, step 136 is again encountered to determine whether there are sufficient unallocated resources to complete task r within this day. Since the flow of control leaving step 136 along both the positive and negative paths has been discussed above, one skilled in the art will understand the applicability to the present context of the various flow of control paths of steps 136-212 that have been discussed above. Alternatively, if task r cannot be completed in the first day, then the negative branch from step 216 is followed to step 140. In step 140, a determination is made as to whether the current starting day precedes the preferred completion day by at least two days. If so, then the next day is not the last day of a multi-day preferred time interval. Therefore, in proceeding to the next step (step 144), there need be no concern regarding completing task r within the preferred time interval if r can be completed on the next day. Therefore, bearing these facts in mind, in step 144 the task r is transferred to the next day and the current starting and completion times are set such that all time slots for this next day may be considered when attempting to allocate resources for r. Subsequently, step 136 is again encountered wherein a determination is made as to whether there are sufficient unallocated resources in the current starting time day for r to complete. If an affirmative answer is provided from step 136 then step 164 and subsequent steps as discussed above are performed. Alternatively, if in step 136 a negative result is obtained then step 140 is again encountered wherein the current time interval for r is modified in subsequent steps in an attempt to allocate resources to r. Thus, for example, if the negative branch from step 140 is taken, step 148 is encountered wherein a determination is made as to whether the current starting day for the task r is the next to the last day of the current interval. If an affirmative answer is provided in step 148, step 152 is performed wherein the task r is again transferred to the next day. However, instead of attempting to schedule r within any of the time slots of the day as in step 144, in step 152 only the portion of the day up to the preferred completion time is specified for use. That is, CC r  (t) receives the value of PC r  (t). Subsequently, step 136 is again encountered. Alternatively, if from step 148 a negative result is obtained, then step 154 is performed wherein a determination is made as to whether the current starting day is the last preferred day. Note that whenever the flow of control reaches step 154, the current starting day is either the last day of the preferred time interval or beyond the last day, and in either case the program has been unsuccessful in appropriately allocating resources to the task r. Thus, r cannot be performed within the preferred time interval. However, it may still be possible to perform the task r within the last day of the preferred time interval if the preferred times within this last day can be expanded. Thus, if the current starting day is beyond the last day or the time intervals within the last day cannot be expanded, then step 156 is encountered wherein a determination is made as to whether resources have been scheduled for the next day. If not, then in step 158 r is removed from DFM(CS r  (d)), a message is output indicating acceptance of r, and r is put on a list of tasks to be scheduled when resources are forecasted for CS r  (d.sub.). Subsequently, step 108 is again encountered. Alternatively, if CS r  (d) has resources forecasted, then step 160 is encountered wherein the task r is transferred to the next day and the current starting and completion times within the day are reset to the preferred starting and completion times, respectively. Thus, an attempt is made to at least perform r within what is believed to be the preferred time interval within a day for completing the task r. Note that an assumption is made here that PS r  (t)≦PS r  (t). It is believed that this is typically true for most service requests. However, in the event this does not hold, then CS r  (t) is assigned the value 0 and CC r  (t) is assigned the value T+1. Subsequently, step 136 is again encountered and processing proceeds as described above regarding step 136 and those steps along the flow of control paths from step 136. 
     Returning now to step 154, if the current day is the last day and the current time interval within the last day can be expanded, then step 224 is performed wherein the time slots for allocating resources to r are expanded to include all time slots within the current day. Following this, step 188 is encountered wherein the daily floater model is again executed to determine if a consistent allocation of resources to all tasks within the model for the current day can be obtained. Subsequently, in step 192 a determination is made as to whether the model for the current day is consistent. If not, step 140 and those steps reachable from step 140 are again performed in search of another time interval within which to allocate resources for r. Otherwise, if in step 192 the model is determined to be consistent, then step 196 and those steps reachable from step 196 are performed wherein resources are at least allocated for task r. 
     In FIG. 3 a flowchart is presented describing the steps taken when using the scheduler of FIGS. 2A through 2E to manage resources. In step 304 a determination is made as to whether further resources are to be forecasted. If so, then in step 308 resources for some number of days are forecasted. Subsequently, in step 312 the program of FIGS. 2A-2E is initialized for these additional days with the forecasted resources N t  for each new day and time slot within the day. Alternatively, if in step 304 resources are not to be forecast, then in step 316 a determination is made as to whether one or more appointment schedules are to be produced for scheduling specific resources at specific times for each task within one of the days. If such appointment schedules are to be provided, then step 320 is performed wherein the variable &#34;NEXT --  DAY&#34; is assigned the first day for which an appointment schedule is to be provided. Subsequently, in step 324, all tasks for &#34;NEXT --  DAY&#34; that have had resources assigned to them in the scheduler are retrieved. In step 328, each task r retrieved in step 324 has its assigned resources scheduled. That is, a specific resource (e.g., a technician) is specified to perform the task r in an appointment commencing at CS r  (t). Following this, in step 332 DFM(NEXT --  DAY) is retrieved so that the remaining tasks within this daily floater model which have been allocated resources (but not assigned resources) may also be scheduled. In step 336, the tasks within the DFM(NEXT --  DAY) are scheduled in a similar manner to those tasks in step 328. Subsequently, in step 338, the daily floater model for NEXT --  DAY is deleted. Following this, a determination is made in step 340 as to whether another day is to be scheduled. If so, then steps 320 through 340 are performed again. Otherwise, the flowchart terminates. As an aside, it is worthwhile to note that each task r in one of the daily floater models retrieved in step 332 is a candidate for having its current time interval modified at any time until its daily floater model is retrieved in step 332. Thus, tasks having time flexibility may potentially be provided with the final appointment time immediately before a schedule for the day of the appointment is created. 
     The foregoing discussion of the invention has been presented for purposes of illustration and description. Further, the description is not intended to limit the invention to the form disclosed herein. Consequently, variation and modification commiserate with the above teachings, within the skill and knowledge of the relevant art, are within the scope of the present invention. The embodiment described hereinabove is further intended to explain the best mode presently known of practicing the invention and to enable others skilled in the art to utilize the invention as such, or in other embodiments, and with the various modifications required by their particular application or uses of the invention. It is intended that the appended claims be construed to include alternative embodiments to the extent permitted by the prior art.