 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to means and methods for allocating
resources to satisfy a time varying demand on those resources and, more
particularly, to improved means and methods for allocating manufacturing
or process resources having multiple constraints thereon to meet various
time varying manufacturing or service demands having multiple
manufacturing or service parameter requirements.
2. Background Art
There is an ongoing requirement in commerce and industry to achieve the
best possible usage of manufacturing or other resources, e.g., production
machines, computers transportation systems, controllers, testers, labor,
etc., consistent with the volume, characteristics and quality of products
or services desired to be produced using those resources. Frequently, a
particular product or service which is desired to be obtained may need
many sequential or parallel steps that must be performed using the various
resources. The particular steps or parameters of those steps may vary with
different products or services and/or during different stages of the
assembly or handling process.
At the same time, the resources intended to be used to make the products or
provide the services have certain inherent capacity. For example, the
quantity that can be produced or handled per unit time on a particular
machine or or by particular workers or at a particular stage of the
process may be fixed by physical constraints on the machine or workers or
process stage; or a given production machine or stage may only be capable
of reaching certain temperatures or lifting certain weight or only have
available only certain atmospheres or chemicals or voltages or currents;
or a given resource may only be capable of carrying out particular steps
or providing a particular sequence of steps. Those of skill in the art
will appreciate that these are only examples of the many physical
constraints that may be associated with individual production or process
resources. As used herein, the words "capacity" or "capacities" are
intended to refer collectively to the many limitations or constraints
which determine the ability of a resource to respond to a demand.
Similarly, the product or service desired will require that certain
physical steps or other conditions be provided. For example, a certain
quantity of the product must be made; or at certain stages of the process
various materials must be subjected to certain temperatures, voltages,
forming operations and/or atmospheres; or certain ingredients or
information must be added. Collectively, these demand requirements define
what it takes to obtain the desired product or service.
The problem faced by those managing the resources, is to balance in the
most desirable way, the demand on the resources against the availability
of the resources, taking into account all of the complex details and
interactions that are part of real world production or processes. This
activity is generally referred to as "scheduling" or "production control"
and has existed for many years. An important and especially complex part
of this activity, is determining how new or modified demands may be
optimally accommodated in a manufacturing or service process which is
already partially loaded by previously scheduled demands. Many possible
options may exist for accommodating the new or modified demands. Also,
resource availability is changing in real time as the previously scheduled
production lots or materials or service recipients continue to advance
through the process.
Historically, scheduling has been done by the use of what is referred to in
the art as "time buckets", that is, using fixed unit increments of time
wherein a given resource, e.g., a particular production resource, is
assigned an availability value. For example, a large chart is made on
which the production resources are listed, e.g., along the left margin and
usually in the order intended to be used. Running across the top are the
unit time increments, for example, hours, days or weeks. The intersections
of the resource rows and the time columns are the "time buckets". When a
resource is committed to perform a particular step for a particular
duration, the corresponding number of time buckets are filled in or marked
in some fashion. The start time, stop time and duration are indicated by
where on the chart and how many of the time buckets are filled in. Often,
the amount of a resource committed to a particular production lot and/or
the amount remaining that might be assigned to another production lot or
both are recorded. In a typical, sequential, time bucket scheduling chart,
the track of an individual batch or production lot appears as a staggered
series of entries extending from upper left toward lower right.
When a new or modified demand is presented to the production scheduler, he
scans the board looking for time buckets which have unused capacity and
which match the other demand requirements. If he finds a sufficient number
of available time buckets with sufficient unused capacity, he enters the
next production lot into the schedule. Various marking or identification
schemes have been used in the past to record this information and computer
programs have been written for many general purpose computers that attempt
to keep track of this time bucket allocation procedure.
A major difficulty with these and other prior art scheduling approaches is
that they become extremely unwieldy and time consuming when the number of
constraints on the manufacturing resources and/or the number of demand
requirements needed by the desired products or services rises. Very large
charts and/or data matrices are needed. Even though powerful (and
expensive) computers are employed to maintain the time bucket allocation
data and receive the input demand requirements, inordinately long times
are required with prior art approaches to achieve optimal balancing of
resources against demand. It has not been possible to achieve real-time
demand-resource allocation solutions for complex manufacturing or process
resources faced with complex product or service demands. One of the
reasons for this is the very large amount of data required to be recorded
and manipulated by prior art approaches.
Accordingly, it is a object of the present invention to provide an improved
means and method for comparing resource availability versus demand
requirements for better resource scheduling.
It is a further object of the present invention to provide an improved
means and method for resource and demand identification, coding and
reconciliation which requires less memory and computing resources than in
the prior art and/or, which can be accomplished in less time.
It is an additional object of the present invention to provide an improved
means and method for resource and demand identification, coding and
reconciliation which can provide more accurate information output than has
been previously available.
The words "scheduling interval" are used herein to denoted a period of time
extending into the future during which it is desired to be able to
schedule resources. In general, the longer the production or service cycle
time the longer the scheduling interval. Scheduling intervals of weeks,
months and years are common. In some rare cases which involve very long
process cycles, schedules can extend over one or more decades.
The words "process" or "processes" are used herein to refer generally to
the steps by which one or more resources operate on various input
materials to change their physical state to provide a product or service
that satisfies the demand. The symbol "c" is used herein to denote
capacity or capacities associated with resources, i.e., what amounts
and/or properties of the resources are available. The symbol "r" is used
herein to denote physical requirements on various resources associated
with various demands, i.e., what amounts and/or properties of the
resources are needed to meed the demand.
Those of skill in the art will appreciate that both "c" and "r" are usually
multi-dimensional. For example, a resource may have simultaneous
capacities "c" for achievable lifting range, work rate, decision making
ability, materials handled, forming ability, computation ability,
temperature, voltage and current range capability, chemicals dispensed,
impurities excluded or provided, input/output configurations, and so
forth. Similarly, a desired product or service may have simultaneous
demand requirements "r" for values of these or other capacity attributes
which must be provided. Further, those of skill in the art will understand
that both c and r can change with time and that the process for satisfying
the demand may be sequential, parallel or a combination thereof.
As used herein, the expressions "</=", ">/=" and "=/=" are intended to
indicate "less than or equal to", "greater than or equal to", and "not
equal to", respectively.
SUMMARY OF THE INVENTION
The attainment of the foregoing and other objects and advantages is
achieved though the present invention wherein there is provided a process
for allocating resources to alter the physical state of predetermined
input materials to meet a predetermined production or service demand,
comprising:
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; PG,7
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.
In a preferred embodiment, this is accomplished by a process comprising:
identifying the demands for altering the physical state of the
predetermined input materials;
identifying one or more quantifiable physical requirements r associated
with the q.sup.th physical demand, relevant to altering the physical state
of the input materials;
identifying the resources needed to provide the desired alteration of the
physical state of the predetermined input materials;
identifying one or more quantifiable physical capacities c associated with
the p.sup.th physical resource, relevant to altering the physical state of
the input materials;
providing an orderable array of multidimensional demand vertices D.sub.q
[t,r,j] for the demand d, wherein t is time, r identifies the physical
requirements associated with the q.sup.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.sub.q [t,r,j] 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.sub.q [t,r,j] corresponding to each value
of j;
providing an orderable array of multidimensional resource vertices R.sub.p
[t,c,i] for the resource p, wherein t is time, c identifies the physical
capacities associated with the p.sup.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.sub.p [t,c,i] 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.sub.p [t,c,i] corresponding to each value
of i;
comparing R.sub.p and D.sub.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.sub.p [t,c,i] for i =(i'+1) to (i"-1) by r(j=1), and
if t(i')=t(j=1) replacing c in the value of R.sub.p [t,c,i'] by
c=c(i')-r(j=1), or if t(i')<t(j=1) inserting a first new value R+.sub.p in
the ordered array of vertices R.sub.p at t(i')<t</=t(j=1), wherein the
first newly inserted value R+.sub.p has c=c(i')-r(j=1), and if
t(i")=t(j=2) leaving the value of R.sub.p [t,c,i"] unaltered, or if
t(i")>t(j=2) inserting a further new value R++.sub.p in the ordered array
of vertices R.sub.p at t(j=2)</=t<t(i"), wherein the further newly
inserted value R++.sub.p has c=c(i"-1)+r(j=1), and increasing I by the
number of newly inserted values of R.sub.p ; and
changing the physical state of the input material by applying the p.sup.th
resource to the input material of the q.sup.th demand at a beginning time
t.sub.b of t(i')</=t.sub.b </=t(j=1) until an ending time t.sub.e of
t(j=2)</=t.sub.e </=t(i").
The above described process is desirably repeated for each value of j and
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. The above described
resource allocation process also yields an updated ordered array of
resource vertices R.sub.p incorporating the newly accommodated demand.
This forms the starting vertex array for considering further demand.
In a further embodiment, 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. This is useful in the situation where
the starting time is not limited by some preceding step constraining when
the lot is available to start processing on the p.sup.th resource. If the
lot is ready to start but scheduling is constrained by the availability of
a p.sup.th resource, then this embodiment provides the first available
starting time when the p.sup.th resource has available capacities c which
meet all of the demand requirements r.
In a still further embodiment, the comparing step is modified to determine
the first available combination of a predetermined number of i value pairs
i.sub.a, i.sub.b; i.sub.c, i.sub.d; i.sub.n, i.sub.m corresponding to time
intervals dt.sub.1, dt.sub.2, ... dt.sub.n, wherein dt.sub.1 +dt.sub.2
+... dt.sub.n >/=dt. This is useful where the steps performed by the
p.sup.th resource need not be continuous in time, and is especially
helpful in maximizing resource usage.
If the foregoing process results in any pre-existing changes in c being
eliminated, then the vertices associated with these eliminated changes are
deleted, the vertex array re-ordered to reflect the deletions and the
value of I=i.sub.max correspondingly adjusted.
The above-described process provides a particularly compact data matrix so
that large numbers of resource capacities and demand requirements can be
quickly evaluated to obtain more effective resource utilization.
A physical resource management system for carrying out the above-described
process which attains the foregoing and other objectives is also provided,
comprising:
means for 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;
means for 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; and
means for 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.
The above described system desirably also includes means for applying the
resource required first in time to the input materials to change the
physical state thereof and/or means for receiving feedback from one or
more resources as to their availability status.
In a preferred embodiment, the above-described system comprises:
means for receiving a description of one or more quantifiable physical
requirements r associated with the q.sup.th physical demand relevant to
altering the physical state of the input materials, and for forming an
array of multidimensional demand vertices D.sub.q [t,r,j] for the demand
q, wherein t is time and j is an integer index running from 1 to J wherein
J is the total number of times wherein r has differing values, and for
receiving a description of one or more quantifiable physical capacities c
associated with the p.sup.th physical resource relevant to altering the
physical state of the input materials, and for forming an array of
multidimensional resource vertices R.sub.p [t,c,i] for the resource p,
wherein t is time and i is a integer index running from 1 to I wherein I
is the total number of times wherein c has differing values;
means for ordering the array of multidimensional vertices D.sub.q [t,r,j]
for increasing values of t, wherein each value of j corresponds to a value
of t where r changes value, and for ordering the array of multidimensional
vertices R.sub.p [t,c,i] for increasing values of t, wherein each value of
i corresponds to a value of t where c changes value;
means for storing the ordered values of D.sub.q [t,r,j]corresponding to
each value of j and for storing the ordered values of R.sub.p [t,c,i]
corresponding to each value of i;
means for comparing R.sub.p and D.sub.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.sub.p [t,c,i] for i=(i'+1) to (i"-1) by
r(j=1), and if t(i')=t(j=1), replacing c in the value of R.sub.p [t,c,i']
by c=c(i') -r(j=1), or if t(i')<t(j=1), inserting a first new value
R+.sub.p in the ordered array of vertices R.sub.p at t(i')<t</=t(j=1),
wherein the first newly inserted value R+.sub.p has c=c(i')-r(j=1), and if
t(i")=t(j=2), leaving the value of R.sub.p [t,c,i"] unaltered, or if
t(i")>t(j=2), inserting a further new value R++.sub.p in the ordered array
of vertices R.sub.p at t(i")>t>/=t(j=2), wherein the further newly
inserted value R++.sub.p has c=c(i"-1)+r(j= 1), and increasing I by the
number of newly inserted values of R.sub.p ; and
means for outputting instructions for changing the physical state of the
input material.
In a further embodiment of the system, the p.sup.th resource is coupled to
the outputting means for receiving therefrom starting and stopping
instructions for applying the p.sup.th resource to the input material of
the q.sup.th demand at a beginning time tb of t(i')</=t.sub.b </=t(j=1)
until and ending time te of t(j=2)</=t.sub.e </=t(i"). In an additional
embodiment of the system, various of the resources are coupled to the
system for providing real time feedback on their capacity constraints,
including for example, present loading, present physical parameter
settings (e.g., temperature, atmosphere, pressure, etc.), present status
(e.g., ready, busy, down, etc.), and the like.
In a still further embodiment of the system, the comparing means comprises
means for deleting previously existing R.sub.p vertices which, after
decrementing and inserting, no longer correspond to changing values of c,
and for re-ordering the array of vertices R.sub.p and adjusting I to
reflect such deletions.
The forgoing and other aspects and advantages of the invention will be more
fully appreciated by reference to the below-listed figures and the
detailed description thereof and the examples that follows.
BRIEF DESCRIPTION OF THE FIGURES
FIG. 1 is a simplified block diagram of a typical computer and
communication bus arrangement useful for the present invention;
FIG. 2 is a simplified block representation of the logical system of the
present invention according to a preferred embodiment;
FIGS. 3-5 and 7 are simplified plots of available resource capacity versus
time, before and after addition of various demand requirements; and
FIG. 6 is a simplified plot of a demand requirement versus time which is
combined with FIG. 5 to produce FIG. 7.
DETAILED DESCRIPTION OF THE FIGURES
FIG. 1 shows in simplified form a schematic block diagram of a physical
system embodying the present invention, comprising input unit 10 and
output unit 12 coupled to processor 14. Memory data store 16 is also
coupled to processor 14. Input unit 10 is conveniently a conventional
keyboard and CRT, but other data input means well known in the art may
also be used. Examples are, paper tape readers, magnetic tape readers,
disk readers and the like, to name a few. Output unit 12 is conveniently a
printer, but other output units will also serve, such as for example, a
modem, a CRT, a tape punch, and a tape or disk drive for recording output
information. The combination of input unit 10, output unit 12 central
processor 14 and memory and data store 16 makes up computer system 18.
Computer system 18 is desirably but not essentially coupled to interface
controller 20 which in turn is coupled to bus 22 which extends to various
physical resources 24. Interface controller 20 and bus 22 provide one or
two way communication between resources 24 and computer system 18, for the
purpose of updating computer system 18 on the status of the various
resources and/or allowing computer system 18 to instruct various resources
24 to commence or terminate work on input materials supplied thereto by
other means (not shown) or make intermediate adjustments during a
particular process step, e.g., when a demand requirement such as for
example a processing temperature is to change within a particular resource
apparatus.
As those of skill in the art will appreciate based on the description
herein, direct communication between computer system 18 and resources 24
is more desirable, but indirect communication involving the intervention
of other apparatus or humans is also effective. Those of skill in the art
will further appreciate based on the description herein, that the exact
hardware configuration of computer system 18 and/or communication system
20, 22 is not critical so long as it performs the functions to be
subsequently described.
It is convenient to use a Model TXP computer manufactured by Tandem
Corporation of Cupertino, CA which includes a central processor and a
memory data store having RAM and non-volatile magnetic storage. A type
3270 input terminal manufactured by IBM of Armonk, NY is coupled thereto
as the input device. The output is a conventional printer. Any type of
compatible printer may be used. The Tandem computer utilizes the
"Guardian" operating system which is well known in the art. The Tandem
computer is programmable in Tandem Assembly Language (TAL) which is well
known in the art, but other well known computer languages may also be
used. The Model TXP Tandem computer is a 32 bit machine with a 83.3
nanosecond micro-instruction time, I/O channel speed up to 5
megabits/second, and CPU capability to address 16 megabits of physical
memory and 1 gigabit of virtual memory.
Absent the logical programs described herein which make the computer
perform the invented process and which reconfigure the computer into the
unique logical apparatus of the present scheduling system, the computer
hardware and its operating system and programming languages are entirely
conventional. The present invention lies in the combination of hardware
and software which results in a unique system having the particular
properties described herein and which is uniquely capable of performing
the invented process.
While the Tandem computer has been used to implement the present invention,
those of skill in the art will understand that other computer hardware,
operating systems, and language choices could also be used, provided that
they have computational precision and speed suitable for the scheduling
precision and complexity desired to be provided. For example, 32 bit
single precision or 16 bit double precision machines with MIPS rates of
about 0.75 or more are believed to provide reasonable performance for many
scheduling applications. As will be subsequently explained, the unique
approach of the present invention materially reduces the speed and memory
capacity demands placed on the hardware, so that the present invention is
particularly adaptable to computers of relatively modest capability.
FIG. 2 shows in simplified schematic form, a block diagram of the planning
model of the present invention according to a preferred embodiment
thereof. The Demand Attribute Data (DAD) File 34, Resource Attribute Data
(RAD) File 36, and Current Capacity Allocation Data (CCAD) File 42 shown
in FIG. 2 are logical data store files and may be located in any physical
memory space or media. The boxes denoted by the identification numbers 32,
38 and 44 in FIG. 2 are intended to represent logical functions and may be
embodied in any physical processor unit. The logical operation of the
resource planning system depicted in FIG. 2 will now be described.
Demand Data (DD) 30 is combined in logical unit 32 with Demand Attribute
Data (DAD) stored in file 34 to obtain an arrays of demand vertices
D.sub.q [t,r,j], defined above. Demand Data generally describes the type
of product or service desired to be obtained, the quantity needed, the
desired completion (and/or starting) date, and other information
concerning special features (e.g., color, quality, authorizations,
licenses, etc.) that must be included. In short, Demand Data is a complete
description of the relevant information concerning the product or service
demanded.
The Demand Data is not by itself directly useful for scheduling. It must be
combined with information in the DAD file. The DAD file contains reference
information that-
relates particular product or service types and features to the process
used for providing it. It tells what steps must be provided and in what
order to build the product or provide the service and what resources are
needed for those steps. The DAD file is generally changed only when there
is a change in the process for making a particular product or service. It
is desirable when the DAD file information is loaded to check it against
the resource information in the RAD file to insure that the DAD file
process only asks for physically realizable resources.
The RAD file contains reference information on the resources, i.e., their
intrinsic capability, such as for example, their unloaded capacity and
achievable parameter ranges (e.g., temperature, atmosphere, forming
ability, decision making ability, etc.), and whether they are on-line and
ready for use. The RAD file generally only changes when there are changes
in the resources or their capabilities. For example, when a new machine or
service module is added, data concerning the old unit is removed and
replaced by data on the new unit. Also, when a unit is removed from
service for repair or maintenance its status would be noted in the RAD
file. Generally, there is no information in the RAD file about whether or
not the resource is actually being used. Line 35 joining the RAD and DAD
Files indicates that information from the RAD File is made available
during loading or updating the DAD File for a consistency check. This is
to insure that the process/equipment information in the DAD File is
consistent with the physical capabilities of the installed resources.
The capacity vertices R.sub.p [t,c,i] 38 are conveniently initialized using
RAD file 36 to provide information on resource characteristics (what),
unloaded capacity (how much), initial availability (when), any inherent
capacity decay information, and anticipated life (shut-down timing),
associated with each resource. Current Schedule Correction Data 40 may
also be provided to update R.sub.p vertices 38 to reflect any known
deviations from the previous schedule that affect resource availability or
capacity. Examples of Current Schedule Correction Data are, unplanned
equipment outages, strikes, production material shortages, split lots,
shortfalls in resource performance, etc. The corrected values of R.sub.p
[t,c,i] for each resource p, having available capacity c at time values t,
are ordered by increasing time values t and stored in the Current Capacity
Allocation Data (CCAD) file 42, as indicated by line 50, with an explicit
or implicit index i denoting each change in capacities c and its related
time value t.
Those of skill in the art will appreciate based on the description herein
that the logical operations required to intialize the resource vertices
R.sub.p and update the vertices R.sub.p with the Current Schedule
Correction information are similar to the operations required to update
the vertices R.sub.p with new demand information, and that the description
which follows concerning the modification of the resources vertices
R.sub.p to accommodate new demand, applies generally to the
above-described operations for obtaining the current values of the
vertices R.sub.p which are used as the starting array for scheduling the
new demand.
When the time ordered D.sub.q and R.sub.p vertex arrays are current, they
are combined and decremented in planning module 44 to provide new proposed
schedule 46 reflecting the newly accommodated demand. Confirmation input
48 is available, if desired, for confirming the new proposed schedule. The
new schedule is delivered by any appropriate means to the affected
resources to cause them to commence processing of the predetermined input
material to alter its state to obtain the desired product output or
provide the desired service.
Provision is also made to remove any pre-existing R.sub.p [t,c,i] vertices
corresponding to changes in capacities c which disappear as a result of
accommodating the new demand and to add any new vertices corresponding to
changes in capacities c required to be added by the new demand. The
vertices are re-ordered by increasing time values t, the index i for each
capacity change is altered, if needed, to reflect the relative position of
the newly ordered up-dated vertices, and the total number of vertices I
adjusted to agree with the new total. This insures that no unnecessary
information is being stored. The updated and re-ordered R.sub.p [t,c,i]
values reflecting the newly accommodated demand are obtained, as indicated
by line 50', and fed back to CCAD file 42, as indicated by lines 50. As
noted previously, the values of i and I=i.sub.max may be explicitly or
implicitly stored. In this manner, CCAD File 42 contains the current
schedule and information on all of the work in progress (WIP).
Where the demand vertices D.sub.q and resource vertices R.sub.p are such
that a complete solution cannot be found, i.e., some or all of the demand
as requested cannot be absorbed by the currently available capacity, then
an error message 52 or an alternative suggestion 54 results or both. For
example, where a demand having a specified start and/or stop time is
presented, and insufficient capacities are available at the specified
start and stop times or during the entire specified start-stop interval,
then the system will respond that the requested capacity and timing is not
available during the scheduling interval. If so desired, the system can
also respond with the p | | |
