Assignment-dependent resource allocation method

• US 5,077,661 A
• Filed: 05/03/1989
• Issued: 12/31/1991
• Est. Priority Date: 05/03/1989
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jain, Shailendra K., Williams, Paul F.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Brutman, Laura
• Application Number:
  US07/346,850
• Time in Patent Office: 972 Days
• Field of Search: 364/402, 364/474.15
• US Class Current: 700/99
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

An iterative, assignment-dependent, method of allocating manufacturing resources to perform operations required in the manufacture of multiple products provides for improved conformance with actual manufacturing situations and for solutions which approximate optimal allocation while requiring only modest computational power and time. The first step involves attributing complex costs to potential assignments of operations to resources. Complex costs include two components, combined money-costs and combined times. Combined cost is an assignment dependent variable which can equal operational cost or the sum of operation cost and set-up cost depending on assignments that have already been made. Combined time is likewise assignment dependent. In a second step, combined cost is selected as a parameter to evaluate each potential operation-resource pair. In a third step, a lowest cost and a second lowest cost resource are determined for each unassigned operation. In a fourth step, a maximum penalty operation is identified by finding the maximum difference between lowest and second lowest costs. In a fifth step, the maximum penalty operation is assigned to its lowest cost resource. In a sixth step, combined costs are re-evaluated to take the most recent assignment into account. In a seventh step, iteration is continued by returning to the third step until all operations have been assigned to resources. Once all operations have been assigned, the assignments are reported as a solution to the allocation problem. The inventive method readily handles capacity constrained resource allocation problems, which are difficult or impossible to solve with conventional techniques.

Claims

1. A method of allocating processing resources to maximize complex-cost-effectiveness, wherein plural products, each requiring at least one processing operation, are to be processed on plural processing resources, each of said operations being performable on at least one of said resources, each of said operations belonging at any given time to one of two sets, an assigned set and an unassigned set, said assigned set including all operations which have been assigned to resources, said unassigned set including all operations which have not been assigned to resources, said assigned set including a whole number of elements, said unassigned set including a whole number of elements, said assigned set defining an assignment map the elements of which are operation-resource pairs, each operation-resource pair including an operation and the resource to which it has been assigned;

said method comprising the following series of steps and mathematic equivalents thereof;

1) attributing a complex cost to each potential assignment of an unassigned operation to a resource, said complex cost including a money-cost and time-cost, the complex cost for each operation-resource pair being a function of and varying according to the assignment map existing at the time of the potential assignment;

2) evaluating potential assignments according to a parameter to obtain a respective parameter value, the magnitude of said parameter value negatively correlated to said effectiveness, said parameter being a function of complex cost, said parameter having an associated comparison function which can be used to compare two parameter values so that a comparison value is obtained, the magnitude of said comparison value providing a measure of differences in effectiveness;

3) determining a most effective resource for each of said unassigned operations, said most effective resource being the resource belonging to the potential assignment with the lowest parameter value for a given operation, also identifying a second most effective resource for each of said unassigned operations, said second most effective resource being the resource belonging to the potential assignment with the second lowest parameter value for a given operation;

4) identifying a maximum penalty operation by comparing parameter values of the most effective resource and the second most effective resource for each operation according to said comparison function to obtain a respective comparison value, then selecting the operation associated with the maximum comparison value;

5) assigning said maximum penalty operation to its most effective resource, changing assignment maps by changing the status of said maximum penalty operation from unassigned to assigned;

6) re-evaluating those of said parameter values affected by changes in complex costs due to the immediately preceding change in assignment maps;

7) iterating steps 3-6 until all operations are assigned;

8) allocating resources in correspondence with the assigned operations;

9) moving the products to the respective allocated resources; and

10) performing the assigned operations on the products by means of the respective allocated resources.

2. A method of allocating plural processing resources in the processing of plural products, plural operations being required for the processing of said products, each of said products requiring at least one associated operation of said operations, each of said operations belonging to one of said products, said operations at any given time being classifiable into two sets including an assigned set of operations which have been assigned to resources to define operation-resource pairs and an unassigned set of operations not assigned to resources, said assigned set defining a respective assignment map of operation-resource pairs, each operation-resource pair having a respective operational cost and a respective operational time, each operation-resource pair having an associated product-resource pair where the operation of the operation-resource pair belongs to the product of the associated product-resource pair, each product-resource pair having a respective set-up cost and a respective set-up time, said method comprising:

1) attributing a combined cost and a combined time to each potential assignment of an unassigned operation, the combined cost for a given operation-resource pair being the sum of the respective operational cost and the set-up cost associated with the associated product-resource pair, unless another operation belonging to that product has been previously assigned to said resource, in which case said combined cost for the given operation-resource pair equals its operational cost, the combined time for a given operation-resource pair being the sum of the respective operational time and the set-up time associated with the associated product-resource pair, unless another operation belonging to that product has been previously assigned to said resource, in which case said combined time for the given operation-resource pair equals its operational time;

2) evaluating each potential operation-resource pair according to a parameter which is a function of and correlates positively with at least one of cost and time, the evaluation of each potential operation-resource pair yielding a respective parameter value, said parameter having a corresponding comparison function for comparing parameter values, said comparison function yielding a comparison value when applied to a pair of parameter values;

3) determining a lowest value resource and a second lowest value resource for each operation, the lowest value resource for a given operation being the resource associated with the potential operation-resource pair having the lowest parameter value of the parameter values for operation-resource pairs including the given operation, the second lowest value resource for a given operation being the resource associated with the potential operation-resource pair having the next-to-lowest parameter value of the parameter values for operation-resource pairs including the given operation;

4) identifying a maximum penalty operation by comparing the lowest and second lowest parameter values for each resource according to said comparison function to yield a comparison value for each unassigned operation, the maximum comparison value among all unassigned operations identifying and belonging to said maximum penalty operation;

5) assigning said maximum penalty operation to its lowest cost resource, transferring said maximum penalty operation from said unassigned set to said assigned set, and revising said assignment map accordingly;

6) re-evaluating the remaining potential operation-resource pairs according to said parameter as required by the assignment of step 5;

7) serially assigning operations to resources by iterating steps 3-6 until all operations have been assigned to resources;

8) allocating resources in correspondence with the resource assignment;

9) moving the products to the respective resources; and

10) performing the assigned operations on the products by means of the respective allocated resources.

3. The method of claim 2 wherein said parameter is capacity qualifed combined cost.

4. The method of claim 3 wherein said comparison function yields a difference in parameter values.

5. The method of claim 3 wherein said comparison function yields a difference in parameter values divided by an operational time.

6. The method of claim 2 wherein said parameter is capacity-qualified combined time and said comparison function yields a difference in parameter values.

7. The method of claim 2 wherein said parameter is a capacity-qualified product of cost and time and said comparison function yields a difference in parameter values.