US 5,797,129 AGrant
Predicting Resource Usage in a Multiple Task, Multiple Resource Environment
Issue Date:1998-08-18
•16 Claims
•2 Drawing Sheets
Abstract
A method for calculating the use of resources in a multi-task, multi-resource environment, such as a factory that produces more than one product and that has at least one machine that can process more than one product. The resources are grouped into resource groups according to the tasks they process. The method includes solving an iterative algorithm, whose solution is a fractional value representing the effective number of resources per resource group. This value can be used in usage formulas where the number of resources per group is used to determine how tasks should be allocated.
Metadata
Assignee
- Texas Instruments Incorporated
Inventor
- Darius Rohan
Application Information
Application Number:US 7858361
Filing Date:1991-10-31
Priority Date:1991-10-31
Art Unit:271
Classifications
IPC:
G06F16300
Field of Search:
364395705401;406;408;468;468.13207-208;201;2591;7;8;6;9
Patent Drawings (2 sheets)
Description
Related Patent Applications
The following patent applications are related to the present application, and are incorporated by reference herein:
U.S. Ser. No. 07/558,970, filed Jul. 26, 1990, now U.S. Pat. No. 5,280,925, "Apparatus and Method for Production Planning".
Technical Field of the Invention
This invention relates to production planning, and more particularly to a method for predicting the usage of scarce resources when there are multiple tasks and multiple resources that may perform the same task.
Background of the Invention
Processes that involve tasks to be performed on various types of equipment are often analyzed in terms of the most efficient method for scheduling the use of each piece of equipment. Typically each piece of equipment, generally referred to as a "resource", has its own set of constraints defining that resource's ability to respond to demand.
An example of resource allocation involving multiple tasks and multiple resources is a system of satellites and their associated communication channels. The multiple resources are three satellites, which are positioned to transmit from the United States to, respectively, other locations in the United States, locations in Europe, and locations in both the United States and Europe. The multiple tasks are the incoming customer requests for connections to Europe and the United States. The scheduling problem involves dispatching customer requests into the alternative communication channels so as to maximize performance of the entire system.
Another example of a multiple task, multiple resource environment is a manufacturing plant in which a factory makes more than one product and each process uses one or more of three different machines.
In order to configure resources and schedule tasks for the most efficient use, various methods of production planning have been developed. One approach to production planning is computer simulation, which is expensive and time consuming. The simulation must be set up and the appropriate algorithms programmed.
Another approach involves analytical algorithms that do not involve simulations. Many such algorithms include an analysis of the pattern of usage across each resource, and methods have been developed for calculating usage factors. A usage factor for a single resource is defined as:
where the arrival rate and service time are in terms of the resource in question and N is the number of resources. Once a usage factor is determined, known scheduling techniques can be used to adjust them so that processing time per task is minimized.
In multi-task production planning usage factor calculations often define "machine groups", where a "machine group" includes those machines that can perform the same task. If a machine in one group can perform more than one task, it is considered a "shared machine", and it will be a member of all groups associated with the tasks it can perform. The usage factor may then be determined with respect to each machine group, such that N in the above expression represents the number of machines in the machine group.
In existing methods, a sharable machine is represented in each machine group of which it is a member. However, a problem with this method is that it overstates the availability of resources. A need exists for a method to determine a usage factor that preserves the true availability of resources.
Summary of the Invention
One aspect of the invention is a method for determining usage of resources in a multi-task multi-resource environment. At least two resource groups are identified, such that the members of each resource group are those resources capable of performing a certain task. In the multi-task, multi-resource environment, it is assumed that at least one member of said resource groups is a shared resource, in that it may perform more than one task. With respect to each resource group, a group weight value that equals the total resource usage of that group divided by the number of resources in that group is calculated. With respect to each resource, a resource weight value that equals the sum of resource usage for all tasks for that resource is calculated, and the group weight value is divided by said resource weight value to obtain an allocation value for that resource. Then, with respect to each resource group, the allocation values for each resource in the group are summed, to obtain a value approximating the effective number of resources in that group. These steps are repeated, using the results of l the summing step instead of using the initial number of resources in each group to calculate the group weight value, until a final effective resource value approximating the effective number of resources for each group is obtained. Based on this effective number of resources per group, tasks are assigned, which may involve adjusting arrival rates, service times, or resource configurations within each group.
Variations of the algorithm include the use of different weighing functions, and the solution of the algorithm with more than one weighing function and interpolation of results. Also, a correction factor has been developed for improving the accuracy of the solution for a greater number of resource configurations.
A technical advantage of the invention is that it provides a method for predicting use of alternative resources in an environment where multiple tasks may be executed by one of more shared resources. A steady state usage factor for the resources may be accurately calculated. A relatively small amount of calculations are required, which permits the computerized algorithm to be very fast.
Using this method, procurement and configuration of resources may be planned. Tasks can be dispatched and the resources can be reconfigured according to current predicted use. In a factory environment, potential bottlenecks can be identified and changing product mixes can result in reconfiguration of machine groups.
Brief Description of the Drawings
FIG. 1 illustrates a multiple-task, multiple resource environment.
FIG. 2 illustrates the grouping of resources into resource groups, which may have shared resources.
FIG. 3 illustrates two resource groups, each having an allocation of a shared machine as a member.
FIG. 4 illustrates a control system having a controller programmed in accordance with the invention.
Detailed Description of the Invention
FIG. 1 illustrates an multiple task, multiple resource environment. The example used herein of such an environment is a production plant having machines for processing multiple products. However, this is only one application of the invention. Other examples are switching of telephone calls into alternative communication channels, scheduling tasks among microprocessors in a multi/parallel processing environment, and job assignment in projects with a mixed/multi skilled labor pool.
There are two products, X and Y, and three resources in the form of machines. Each machine is identified with a unique numeral Mk, where k=1 . . . K. Machines M1 and M2 can process product X and machines M2 and M3 can process product Y. In other words, machine M2 is "sharable", whereas machines M1 and M3 are dedicated to a single task.
FIG. 2 illustrates the concept of a resource group, which in the production plant example used herein, is a machine group (MG). The set of machines that can perform a certain task are members of a group. Each machine group is identified by a numeral MGj, where j=1 . . . J. Thus, because machines M1 and M2 can process product X, they are members of MG1. Similarly, machines M2 and M3 are members of MG2. The notation, MG.sub.j, represents the set of all machines in a machine group. A machine Mk may be shared by two or more machine groups.
FIG. 3 illustrates a machine group decomposition into separate groups, each containing a fractional representation of the sharable machine, M2. A basic concept of the invention is that each sharable machine, such as M2, is represented as a fraction of a machine in each of its groups, i.e., an "allocation value". For example, a machine equally shared between two groups would be represented as 1/2 a machine in one group and 1/2 in the other. When considering the total number of effective resources in a group, the shared machine's fractional allocation value is added to the integer allocation values of non-shared machines. The fractions are derived using an iterative analytical algorithm described herein.
Referring again to FIG. 1, each machine group is associated with a mean arrival rate, AR.sub.j, of jobs into the queue for that machine group, MGj. The mean service time corresponding to jobs coming into this queue is ST.sub.j. The notation, MH.sub.j, represents the total machine hours needed for processing at a machine group, MGj. The total machine hours may be symbolically expressed as:
Given a value representing MH.sub.j, the ability to determine a usage factor for that machine group, MH.sub.j /N.sub.j, depends on the value of N.sub.j. Once the usage factor is known, a decision can be made regarding how tasks should be allocated to each machines or the machines reconfigured. Techniques are known in the art of production planning whereby certain usage factor values are desired to maximize overall efficiency.
If the group has one or more shared resources, counting that machine as a member of each machine group results in inaccurate usage factors for its groups. To avoid overstating the availability of shared resources, an iterative algorithm is used to determine an "effective" number of machines, N.sub.j, for any one machine group. The number of machines attributed to machine group j at an ith iteration, where i=0, 1, 2, 3 . . . , is N.sub.ij. The problem is to find a function such that:
with the property that N.sub.ij approaches N.sub.j as i approaches infinity, given that an arbitrary but suitable initial value of N.sub.0j is chosen.
A solution to the above algorithm may be found by first defining the following generalized weight function:
where g is any well behaved function that increases as MH.sub.j increases and that decreases as N.sub.ij increases. The value, w.sub.ij, representing the weight given to each resource of a group MG.sub.j during an ith iteration, is referred to herein as a "group weight value".
The sum of weight values that correspond to a given machine, Mk, for all tasks it performs is expressed as: ##EQU1##
The value, WS.sub.ik, representing the sum of weights for a given machine during an ith iteration is referred to herein as a "resource weight value".
The fractional allocation of a machine, Mk, to a machine group, MGj, at the ith iteration of the algorithm, is expressed as:
for all machines that are members of MG.sub.j =0 otherwise.
The sum of allocations for all machines belonging to machine group MG.sub.j is expressed as: ##EQU2##
At the final iteration, N.sub.j represents the effective number of resources in the group. If the machine group MG.sub.j has at least one shared machine, N.sub.j is a fractional value. A machine group may have only one resource which may be a shared resource, in which case N.sub.j is the same as that resource's allocation value and is a value less than one. Typically, however, a machine group will have one or more shared resources and one or more non-shared resources, in which case N.sub.j is the sum of the allocation values of the shared resources plus an integer value representing the non-shared resources.
The above algorithm acts as a linear distributor of fixed resources. The distribution of each machine's time to different machine groups is made relative to the weight values represented by w.sub.j 's that correspond to those machine groups containing the machine as a member. The weights used by each iteration, the w.sub.ij 's, depend on the summed distribution of resources to the machine groups as calculated in a previous iteration.
Given a certain arrival rate, processing time, and machine group configuration, convergence of the algorithm to a desired N.sub.j depends largely on the choice of function for the weight values. As explained below, the algorithm may be solved with any one of a number of weight functions. Also, it may be solved more than once with different weighing functions to obtain intermediate solutions, which are then interpolated for a final solution.
A weighing function that is a simple ratio of MH.sub.j and N.sub.ij may be expressed as: ##EQU3## Letting N.sub.2j and N.sub.3j be the solutions of the second and third iterations of the above algorithm, the general solution is:
where the midpoint between the last two iterations is used to provide a solution closer to the convergence point.
A second weighing function may be expressed as: ##EQU4## Again, letting N.sub.2j and N.sub.3j be the solutions of the second and third iterations of the algorithm, the general solution is: ##EQU5##
As compared to a solution using only one of the above weighing functions, an interpolation of two different weighing functions has been found to provide accurate results. Using w.sub.ij =p.sub.ij, the solution is: ##EQU6## where ##EQU7##
Using ##EQU8## the solution is: ##EQU9## where ##EQU10##
The above solutions are based on three iterations; any number of iterations may be used to obtain a final solution N.sub.j. If more iterations are used, the last two iterations may be used to determine an average value.
Another version of the algorithm uses an average utilization of machine groups to adjust values of N.sub.j during each iteration. An average utilization of machine groups MG.sub.j 's of which machine Mk is a member, is estimated as follows: ##EQU11## where P.sub.j =MH.sub.j /N".sub.j. The above equation can be informally expressed as: ##EQU12## The adjustment factor is then calculated as:
and the improved algorithm is: ##EQU13## where A(kj)=(.alpha.)A'(kj)+(1-.alpha.)A"(kj).
The accuracy of the above algorithm may be still further improved by adding a correction term, .omicron., such that:
The correction term, .omicron., provides a means for adjusting the algorithm according to a scheduling strategy. For random and unbiased priority among machines, .omicron. is determined as follows:
For a strategy that gives preference to unshared machines, .omicron. is determined as:
which keeps shared machines available for other tasks.
A simplified example of calculation steps for the above algorithm may be followed with respect to FIGS. 1-3. In this example, the weight function is p.sub.ij only; the interpolated solution using two weight functions, p.sub.ij
and ##EQU14## is not used. For purposes of example, the following data are assumed: 10 minutes=service time per item of product A (T.sub.A)
20 minutes=service time per item of product B (T.sub.B)
6 lots/hour=arrival rate for product A (AR.sub.A)
1.5 lots/hour=arrival rate for product B (AR.sub.B).
If total machine hours, MH, for a product is defined as:
then
1.0 machine hours are used for MG 1
0.5 machine hours are used for MG 2.
If the fraction of time each machine is available for production is assumed to be 1.0, the usage factor for each machine group is: ##EQU15## where N.sub.j is the number of effective machines in the machine group MG.sub.j.
The initial setting of N.sub.j for solving this example represents the shared machine, M2, in full in each machine group. Thus, N.sub.1 =2 and N.sub.2 =2 for the first iteration.
Using the machine usage values set out above, during the first iteration, the group weight values are: ##EQU16## and the resource weight values are:
For this first iteration, the weight values and the allocation values are summarized in the following table:
It follows from the above calculations that
During the second iteration of the algorithm, using the values from the first iteration as set out above, the group weight values are: ##EQU17## The resource weight values and allocation values are calculated, with the following table summarizing the results:
It follows from the above calculations that
For the final result, the midpoint between the last two iterations provides a solution close to the convergence point. Thus, ##EQU18## Using these values for N.sub.A and N.sub.B, a usage factor for each machine group can be calculated. This usage factor can then be compared to desired usage factors. A decision can then be made regarding how tasks should be allocated or whether resource groups should be reconfigured.
FIG. 4 illustrates a control system for allocating tasks in a multi-task multi-resource environment. The resources, R1-R3, like the machines M1-M3 in the description above, include at least one shared resource. A controller 41 is programmed to calculate usage values for each machine. These values are based on data gathered by a counter/timer unit 42 associated with each machine for measuring values such as service times and arrival rates. Controller 41 receives this data via communication links 45 and calculates actual usages over a time period, t, resulting in a value, A. Over this same time period, t, running averages of arrivals and service times are received by controller 41 from task queue 43 via bidirectional communications link 46. These data are used to calculate expected usages, resulting in a value B, in accordance with the above-described method. Current data about arrivals of tasks and their required service times are also received by controller 41 via link 46 from task queue 43 to predict the upcoming expected usages, resulting in a value C, in accordance with the above-described method.
The results of the above calculations, A, B, and C, are used to predict the usage factors for the current task dispatching policy. One such method may be to set a usage factor, UF, as: ##EQU19##
The usage factor, which assumes no change in the task dispatching policy, is compared with a desired usage factor to determine the needed increases or decreases in flow of tasks to various resources. This modified dispatch policy is implemented by regulating the flow of tasks from task queue 43 using link 46. In this manner, as the intensity and mix of incoming tasks shift, controller 41 adjusts the flow of tasks that are delivered from task queue 43 to each resource via task flow lines 44, to achieve a desired effect.
Other Embodiments
Although the invention has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as alternative embodiments, will be apparent to persons skilled in the art. It is, therefore, contemplated that the appended claims will cover all modifications that fall within the true scope of the invention.
Claims
What is claimed is:
1. A method for controlling usage of machines in a multi-task, multi-machine environment, comprising the steps of: a) providing a counter/timer unit for determining arrival rates and process times for each machine; b) providing and coupling a task queue to said machines and said counter/timer unit; said task queue receiving a flow of tasks; c) providing and coupling a programmable controller to said task queue; d) identifying at said controller at least two machine groups, wherein the members of each machine group are those machines capable of performing a certain task, and wherein at least one member of one of said machine groups is a shared machine capable of performing more than one task; e) with respect to each machine group, generating in said controller a signal representing a group weight value that equals the total machine usage of that group based on arrival rates and process times from said counter/timer unit divided by the number of machines in that group; f) with respect to each machine, generating in said controller a signal representing machine weight value that equals the sum of machine usage for all tasks for that machine; g) with respect to each machine, generating in said controller an allocation value signal for each machine representing dividing said group weight value by said machine weight value; h) with respect to each machine group, summing in said controller allocation value signals for each machine in said group and generating a signal representing a value approximating an effective number of machines in each machine group; i) repeating said steps e thru h in said controller using the signal representing a value approximating an effective number of machines generated in step h instead of using the number of machines in each group to generate a signal representing said group weight value until a signal representing a final effective machine value approximating the effective number of machines for each group is generated; and j) controlling flow of tasks at said task queue to said machines dynamically in response to said signal representing said final effective machine value for each group.
2. The method of claim 1 wherein said signal representing said group weight value is generated by said controller by taking the product of the process time per task times the arrival rate of said tasks and dividing that by the number of machines in the group.
3. The method of claim 1 wherein said signal representing said final effective machine value is generated by said controller by calculating the final effective machine value of the two proceeding iterations.
4. The method of claim 1 wherein in generating said signal representing said group weight value said group weight value is squared and divided by the difference between one and said group weight value, and the resulting value is used in subsequent steps instead of said group weight value.
5. The method of claim 1, and further comprising the step of using said final effective machine value to calculate a group usage value.
6. The method of claim 1, wherein said step of controlling flow of tasks includes reconfiguring machines within said machine groups.
7. The method of claim 1, and further comprising the step of using more than one group weighing function and interpolating the results at each iteration to provide said signal representing said final effective machine value.
8. The method of claim 7, wherein said interpolation is accomplished by averaging the results at each iteration.
9. The method of claim 7, wherein said interpolation is accomplished by calculating an adjustment factor that equals the square root of an average machine utilization, multiplying one result by said adjustment factor, multiplying another result by the difference between one and said adjustment factor, and summing the products.
10. The method of claim 9, and further comprising the step of adding a correction value.
11. A method for controlling usage of machines in a multi-task, multi-machine environment, comprising the steps of: a) providing a counter/timer unit for determining arrival rates and process times for each machine; b) providing and coupling a task queue to said machines and said counter/timer unit; said task queue receiving a flow of tasks; c) providing and coupling a programmable controller to said task queue; d) identifying at said controller at least two machine groups, wherein the members of each machine group are those machines capable of performing a certain task, and wherein at least one member of said machine group is a shared machine capable of performing more than one task; e) with respect to each machine group, generating in said controller a signal representing a group weight value that equals the total machine usage of that group based on arrival rates and process times from said counter/timer unit divided by the number of machines in that group, f) with respect to each machine, calculating in said controller a machine weight value that equals the sum of machine usage for all tasks for that machine and generating a signal representing a first allocation value that is equal to said group weight value divided by said machine weight value; g) with respect to each machine group, generating in said controller a normalized group weight value representing first group weight value squared divided by the difference between one and said group weight value; h) with respect to each machine, generating in said controller a signal representing a second allocation value that equals said normalized group weight value divided by said equipment weight value; i) with respect to each machine group, generating a signal representing a final effective machine value in said controller by summing said first allocation value and said second allocation value to obtain two iteration values approximating an effective number of machines in each group and by interpolating in said controller said two iteration values; j) repeating said steps h and i in said controller using the results of said interpolation instead of using the number of machines in each group to determine said group weight value, until a signal is generated representing a final effective machine value approximating the effective number of machines for each group is obtained; and k) controlling flow of tasks at said task queue to said machines dynamically in response to said signal representing said final effective machine value for each group.
12. The method of claim 11, wherein said interpolation is accomplished by finding an average of said two iteration values.
13. The method of claim 11, and further comprising the step of calculating an average utilization factor of each machine group, and where said interpolation is accomplished by multiplying said average utilization factor times said first iteration value, multiplying said average utilization factor times said second iteration value, summing the products, and adding a correction value.
14. The method of claim 13, wherein said correction value depends on a scheduling strategy.
15. The method of claim 13, wherein said correction value is the product of said group weight value minus said average utilization factor times a predetermined number minus said average utilization factor.
16. A multi-machine apparatus with means for controlling the allocation of machine in a multi-task, multi-machine environment comprising: a plurality of machines; said machines comprising at least two machine groups wherein the members of each machine group are those machines capable of performing a certain task, and wherein at least one of those machines in a machine group is a shared machine capable of performing more than one of the tasks; a task queue coupled to said plurality of machines and adapted to receive a plurality of tasks; a counter/timer unit coupled to said task queue and responsive to said multi-tasks for determining the process time per lot of said multi-tasks and the arrival rate of lots of said multi-tasks for said machine group; a programmable controller coupled using communication links to sad task queue for generating a control signal representing a final effective machine value; said control signal generated by said controller programmed to perform the following steps: a) with respect to each machine group, generating in said controller a signal representing a group weight value that equals the total machine usage of that group based on arrival rates and process times from said counter/timer unit divided by the number of machines in that group; b) with respect to each machine, generating in said controller a signal representing machine weight value that equals the sum of machine usage for all tasks for that machine; c) with respect to each machine, generating in said controller an allocation value signal for each machine weight value; d) with respect to each machine group, summing in said controller allocation values for each machine in said group and generating a signal representing a value approximating an effective number of machines in each equipment group; and e) repeating said steps a thru d in said controller using the signal representing an effective number of machines generated in step d instead of using the number of machines in each group to generate a signal representing said group weight value until said control signal representing a final effective machine value approximating the effective number of machines for each group is generated; and a communications link for coupling said control signal to said task queue to control the flow of tasks to said machines dynamically in response to said control signal from said controller.