Manufacturing or service system allocating resources to associated demands by comparing time ordered arrays of data

• US 5,128,860 A
• Filed: 04/25/1989
• Issued: 07/07/1992
• Est. Priority Date: 04/25/1989
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Chapman, William
• Primary Examiner(s): Hayes, Gail O.
• Application Number:
  US07/342,774
• Time in Patent Office: 1,169 Days
• Field of Search: 364/419, 364/401, 364/408, 400/63, 400/76
• 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 improved method and system is described for allocating manufacturing or process resources having multiple constraints thereon to meet various time varying manufacturing or service demands having multiple parameter requirements.

The demand requirements are expressed as a multi-dimensional time ordered array of vertices D_q [t,r,j], for each demand q, wherein t is time and r identifies the physical requirements associated with the q^th demand and j is an integer index running from 1 to J wherein J is the total number of times wherein r has differing values. The available resources are expressed as a multi-dimensional time ordered array of resource vertices R_p [t,c,i] for each resource p, where c expresses the physical capacities associted with the p^th resource, t is time and i is an integer index running from 1 to I where I is the total number of times wherein c has differing values.

A logical system is provided for comparing R_p and D_q to determine when and how D_q may be accommodated by R_p. The invented arrangement provides very compact representation of the demand and resource information so that very complex processes and products may be modeled and scheduled with great time precision without requiring large amounts of memory. The invented arrangement can provide scheduling accuracy of one second over a scheduling interval of a century even with a modest size computer.

Claims

1. A process for altering the physical state of predetermined input materials by allocating one or more resources to meet one or more predetermined demands on the resources, comprising:

providing predetermined input materials having a physical state it is desired to alter;

identifying a plurality of demands for altering the physical state of the predetermined input materials;

providing a plurality of physical resources needed to perform the desired alteration of the physical state of the predetermined input materials;

converting the demands into an array of physical resource capacity requirements for each resource which is ordered in time and has entries only for time values when the required capacities change;

providing for each resource an array of available capacities which is ordered in time and has entries only for time values when the available capacities change;

comparing the time ordered arrays of required and available capacities to determine whether and when the available capacities equal or exceed the required capacities and, when successful, modifying the time ordered array of available capacities to provide an up-dated time ordered array of available capacities reflecting the assignment of available capacities to meet the requirements associated with the demands, wherein the up-dated time ordered array of available capacities only has entries when the up-dated available capacities change; and

applying the resource required first in time to the input materials to change the physical state thereof.

2. A process of altering the physical state of predetermined input materials to meet a predetermined production or service demand, including steps for allocating resources, said process comprising:

providing predetermined input materials having a physical state it is desired to alter;

identifying a plurality of demands for altering the physical state of the predetermined input materials and selecting a first demand q from the plurality of demands;

identifying one or more quantifiable physical requirements r associated with the q^th physical demand, relevant to altering the physical state of the input materials;

providing a plurality of physical resources needed to perform the desired alteration of the physical state of the predetermined input materials;

selecting a p^th physical resource from the plurality of resources and identifying one or more quantifiable physical constraints c associated with the p^th physical resource, relevant to altering the physical state of the predetermined input materials;

providing an orderable array of multidimensional demand vertices D_q for the demand q, wherein t is time, r identifies the physical requirements associated with the q^th demand, and j is an integer index running from 1 to j wherein j is the total number of times wherein r has differing values;

ordering the array of multidimensional vertices D_q for increasing values of t, wherein each value of j corresponds to a value of t where r changes value;

storing the ordered values of D_q corresponding to each value of j;

providing an orderable array of multidimensional resource vertices R_p for the resource p, wherein t is time, c identifies the physical constraints associated with the p^th resource, and i is an integer index running from 1 to I wherein I is the total number of times wherein c has differing values;

ordering the array of multidimensional vertices R_p for increasing values of t, wherein each value of i corresponds to a value of t where c changes value;

storing the ordered values of R_p corresponding to each value of i;

comparing R_p and D_q to determine the values i'"'"' and i" of i between which c>

/=r,t(i'"'"')<

/=t(j=1) and t(i")>

/=t(j=2), and decrementing the values of c in R_p for i=(i'"'"'=1) to (i"+1) to (i"-1) by r(j=1), and if t(i'"'"') =t(j=1), replacing c in the value of R_p by c=c(i'"'"')-r(j=1), or if t(i'"'"')<

t(j=1), inserting a first new value R+_p in the ordered array of vertices R_p at t(i'"'"')<

t<

/=t(j=1), wherein the first newly inserted value R+_p has c=c(i'"'"')-r(j=1), and if t(i")=t(j=2), leaving the value of R_p unaltered, or if t(i")>

t(j=2), inserting a further new value R++_p in the ordered array of vertices R_p at t(j=2)<

/=t<

t(i")>

, wherein the further newly inserted value R++_p has c=c(i"-1)+r(j=1), and increasing I by the number of newly inserted values of R_p ; and

changing the physical state of the input material by applying the p^th resource to the input material of the q^th demand at a beginning time t_b of t(i'"'"') <

/=t_b <

/=t(j=1) until an ending time t_e of t(j=2)<

/=t_e <

/=t(i").

3. The process of claim 2 wherein the described process is repeated for each resource p and demand q until a series of beginning and ending times is obtained for completing the entire desired manufacturing or service sequence on all of the needed resources.

4. The process of claim 2 further comprising providing an updated ordered array of resource vertices R_p incorporating the newly accommodate demand.

5. The process of claim 2 wherein the comparing step is modified to determine the first available values i* and i** and corresponding times t(i*) and t(i**) when c >

/=r for a time interval dt=t(j=2)-t(j=1), and then setting t(j=1)=t(i*) and t(j=2) =t(i*)+dt.

6. The process of claim 2 wherein the comparing step is modified to determine the first available combination of a predetermined number of i value pairs i_a, i_b ;

i_c, i_d ;

. . . i_n, i_m corresponding to time intervals dt₁, dt₂, . . . dt_n, wherein dt₁ +dt₂ +. . . dt_n >

/=dt.

7. The process of claim 2 including performing with a computer the steps of "ordering the array of multidimensional vertices D_q ", "ordering the array of multidimensional vertices R_q " and "comparing R_p and D_q ".