System integration based on time-dependent periodic complexity6701205Abstract A processing system having time-dependent combinatorial complexity is converted into a system having time-dependent periodic complexity. Consequently, system reliability is increased and system design is generally simplified. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
PT.sub.i or CT.sub.Y Number of MvPk.sub.i MvPl.sub.i
Station (sec) machines (sec) (sec)
IN -- 1 5 --
X
a 30 1 5 5
b 40 1 5 5
c 50 1 5 5
d 80 2 5 5
Y 80 1 -- 5
(a) Constant Cycle Times for Subsystem X and Subsystem Y Referring to the part-flow timing diagram of FIG. 3, process times PT.sub.a, PT.sub.b, PT.sub.c, PT.sub.d for subsystem X are constant and the cycle time CT.sub.Y for subsystem Y is also constant. Thus, there are no variations in the fundamental period of the system. The horizontal axis represents time and the vertical axis (row) represents different parts processed by subsystem X. In particular, the first row represents the flow of a first part processed by subsystem X, the second row represents the flow of the second part processed by subsystem X, etc. An incoming part is received by subsystem X every 90 seconds, i.e., at the fundamental period FP.sub.Y. Two transport conflicts repeatedly occur in subsystem X, one between transports (1,2) and (3,4) and a second between transports (5,6) and (9,10). The pick-up schedule for subsystem X is determined according to which part is picked up first by the robot at the moment of the transport conflict. Thus, the number of possible routes for the robot increases as additional decisions are made at the time of the conflicts. The system 10 is therefore subject time-dependent combinatorial complexity. However, if waiting times are appropriately selected, the complexity of the subsystem X can be converted into a time-dependent periodic complexity. FIG. 4 shows that an additional 10 seconds of post-process waiting time in machine M.sub.b and another 10 seconds post-process waiting time in machine M.sub.d resolves the transport conflicts without the need for real-time decision-making and maintains a 90 second sending period for the system 10. FIG. 5 illustrates another steady state solution for operation of subsystem X for the same example. The part-flow timing diagram illustrates the evolution of the subsystem X from an empty state without enforcing the sending period for incoming parts. In other words, the next part is provided to subsystem X whenever possible. After an initial transient period during startup, subsystem X enters a steady state. The lengthy delay times, however, result in a longer cycle time (i.e., the full time necessary for subsystem X to process a part) than that achieved according to the part-flow timing diagram of FIG. 4. (b) Variable Cycle Time of Subsystem Y If the cycle time CT.sub.Y of subsystem Y varies between 75 seconds and 85 seconds due to non-deterministic processes, subsystem Y can only take a part from subsystem X once every 85 seconds to 95 seconds. Thus, the delay times used for steady state operation are not valid and the schedule for robot motion must be recomputed each time subsystem Y picks up a semi-finished part from subsystem X. In this illustrative example, there are two constraints on subsystem X. First, the part just processed at machine M.sub.c must be immediately picked up for transport. Second, a part must be available for subsystem Y when it is ready to take one. In this case, the pattern for the part-flow timing diagram is not the same for each period and, depending on the temporal distribution of variation in the cycle time CT.sub.Y and the inherent conflict pattern, the task of scheduling can be significantly complex. In particular, the difficulty in scheduling results from the randomness in the transport conflict pattern. As previously described, when a time-dependent combinatorial complexity problem is converted into a periodic complexity problem, the design of the operations schedule is simplified. The conversion requires that a period FP be imposed on the system 10. In such a period FP, the same set of tasks is performed cyclically in a pre-determined way and, therefore, a limited number of scheduling possibilities exists. The period is initiated by an internal or external key event. A basic constraint on the system 10 is that delivery of a part to subsystem Y must be completed as soon as possible. In this example, a part request from subsystem Y is chosen to be the key event for starting a new fundamental period FP for multiple reasons. First, subsystem Y limits the pace of the total system 10. Also, the pace of the system 10 has to be adjusted to accommodate the variations in the cycle time CT.sub.Y of subsystem Y. Because a part request issued by subsystem Y is treated as the key event, the length of each period FP depends on CT.sub.Y. Even though the length of each period FP is generally different, the same set of functions is performed by the subsystem X and the robot completes all required transport tasks so that steady-state operation is maintained. In order to manage the present case in accordance with the principles of the invention, the functional requirements of the system 10 are determined and mapped into a physical domain so that design parameters can be determined. This process proceeds from a determination of high-level functional requirements down to a more detailed level required for implementation. High-level functional requirements include the need to re-initialize subsystem X when subsystem Y requests a new part for processing; transporting parts whenever transport is requested and possible; and setting the various process times. Constraints on the system 10 include the need to transport a part from machine M.sub.c immediately once process c is completed and to provide a part from subsystem X to subsystem Y whenever subsystem Y requests a part. As described earlier, the current state of subsystem X (i.e., which machines are available and the process times of occupied machines) is determined at the time of re-initialization. Appropriate delay times are then calculated for each of the occupied machines. First, to ensure that the robot is always available during the timeslot of the next renewal event, a no-transport-time is determined as No_transport_time={t.vertline.t.epsilon.[(MvPk.sub.Y-1 +MvPl.sub.Y)+min(CT.sub.Y),(MvPk.sub.Y-1,+MvPl.sub.Y).multidot.2+max(CT. sub.Y)]} (9) where t=0 at the moment of the current key event. Second, assign all transport tasks which are determined at the instant of re-initialization (i.e., prefixed transport tasks). Prefixed tasks include transport (1,2) by the definition of the key event, and possibly transport (3,4) due to the need to move a part quickly from machine Mc. Remaining transport tasks are then allocated. FIG. 6 depicts a part-flow timing diagram for the steady state operation shown in FIG. 5 with a change in the cycle time CT.sub.Y for subsystem Y. The vertical lines indicate the time when subsystem Y 30 requests a part from subsystem X and therefore represent the moments of re-initialization. As shown in the second full period, due to the variation in cycle time CT.sub.Y, subsystem Y requests a finished part from subsystem X at some time at least 85 seconds but no more than 95 seconds after the re-initialization (10 second transport time plus .about.75-85 second cycle time CT.sub.Y). Therefore, the transport task is scheduled so that the robot is available for the period from 85 seconds to 105 seconds after the re-initialization. After a part request is issued by subsystem Y (vertical line), a renewal signal is generated to re-initialize the database of processes. First, the state of each machine M is identified as busy or idle, and empty or occupied. At the onset of the second re-initialization (second vertical line), it is determined that machines M.sub.a, M.sub.b, M.sub.c, and M.sub.d2 are busy (and therefore occupied) and that machine M.sub.d1 is occupied and idle. FIG. 7 depicts the remaining process times for the busy machines. Based on this information, the transport schedule is constructed. In this example, transport tasks (1,2) and (3,4) are prefixed tasks. Transport task (1,2) occurs 0 to 10 seconds after the moment of the re-initialization. Another task, (3,4), must occur from 15 to 25 seconds after re-initialization because the part in machine Mc must be removed as soon as process c is complete. The allowable transport timeslots are computed and the remaining transport tasks are assigned in the timeslots. One possible schedule is shown in FIG. 8 in which the x's signify the no-transport-time period. Transport task (5,6) is delayed for 20 seconds due to the no-transport-time condition. Transport tasks (7,8) and (9,10) simply follow task (5,6) at the earliest possible time according to fundamental conditions for part transport (i.e., the current machine is finished, the next machine is empty, and the robot is available). The next period (not shown) can be determined regardless of when subsystem Y picks up the part exiting subsystem X. FIG. 9 depicts multiple intervals with different cycle times CT.sub.Y for subsystem Y. Each interval is independent from the previous intervals except for the immediately preceding interval. In other words, the effect from the variation of the cycle CT.sub.Y for subsystem Y does not propagate to a later time. Case 2: The throughput Rate of Subsystem X is Less Than That of Subsystem Y: FP.sub.X >FP.sub.Y Case 2 is directed to a system 10 in which the fundamental period FP.sub.X of subsystem X exceeds the fundamental period FP.sub.Y of subsystem Y. Consequently, subsystem Y has to wait until a next part finishes its processes in subsystem X. In other words, subsystem Y is operated in a starved mode. Thus, it does not matter when subsystem Y finishes its processing and requests a new part as long as this relationship between the fundamental periods FP.sub.X,FP.sub.Y exists. In other words, the variation of CT.sub.Y does not affect the operation of subsystem X. In this example subsystem X has only one machine M.sub.c for process c. The process times for processes a, b, c, d, the cycle time CT.sub.Y for subsystem Y, the number of machines for each process, and the associated transport times are shown in Table 2. From equations (6) and (7), the fundamental period FP.sub.X for subsystem X is 80 seconds and the fundamental period FP.sub.Y for subsystem Y is 70 seconds. Consequently, the fundamental period FP of the total system 10 is 80 seconds. As in case 1, the actual cycle time CT.sub.Y of subsystem Y is assumed to vary within .+-.5 seconds. Under these conditions, any one of the three basic approaches (i.e., expert system, synchronous approach, and re-initialization) achieves similar results because the system 10 can be treated as having no cycle-time variation. In other words, even if subsystem Y requests a part when it is ready to process the next part, no part is available from subsystem X. As a result, subsystem Y must wait until a part is available and the variation in its cycle time need not be considered in the transport scheduling for subsystem X. FIG. 10 is a part-flow timing diagram for one possible solution based on the constant 80 seconds for the fundamental period FP.
TABLE 2
PT.sub.i or CT.sub.Y Number of MvPk.sub.i MvPl.sub.i
Station (sec) machines (sec) (sec)
IN -- 1 5 --
X
a 30 1 5 5
b 40 1 5 5
c 60 1 5 5
d 80 2 5 5
Y 60 1 -- 5
Alternatively, a re-initialization can be implemented based on the event "machine M.sub.d is ready to send a part and the robot is available." FIG. 11 shows information on the remaining process times and state of each machine at the time of re-initialization. This information is used to compute delay times and accordingly a robot schedule as shown in FIG. 12. Case 3: Both Systems are About the Same, with CT.sub.Y fluctuating about its mean: min{FP.sub.Y }<FP.sub.X <max{FP.sub.Y } Case 3 is a hybrid version of case 1 and case 2 because the cycle time CT.sub.Y of subsystem Y is sometimes less than the cycle time CT.sub.X of subsystem X and at other times is greater than that the cycle time CT.sub.X of subsystem X. Unfortunately, the faster cycle times CT.sub.Y cannot be used to directly offset the slower cycle times CT.sub.Y for subsystem Y because the duration of the next cycle time CT.sub.Y of subsystem Y is not known a priori. In other words, since it is not known when subsystem Y will request its next part, subsystem X has to be ready to deliver a part at the earliest possible request time by subsystem Y if it is to keep pace. The process times, number of machines and associated transport times are shown in Table 3. According to equation (6), the fundamental period FP.sub.X of subsystem X is 70 seconds. Based on a variability of 5 seconds in the cycle time CT.sub.Y of subsystem Y, its fundamental period FP.sub.Y is 65 to 75 seconds.
TABLE 3
PT.sub.i or CT.sub.Y Number of MvPk.sub.i MvPl.sub.i
Station (sec) machines (sec) (sec)
IN -- 1 5 --
X
a 30 1 5 5
b 40 1 5 5
c 50 1 5 5
d 80 2 5 5
Y 60 1 -- 5
FIG. 13 depicts one mode of steady state operation of subsystem X with a fundamental period FP of 70 seconds. Limited to the illustrated instance, subsystem X appears capable of providing a part to subsystem Y even if subsystem Y has a cycle time CT.sub.Y of 55 seconds. In particular, the fundamental conditions for part transport are satisfied because a part is ready at machine M.sub.d2, the robot is available, and subsystem Y is ready to accept a part. Referring to FIG. 14, however, it can be shown that subsystem X cannot sustain a high system throughput over many intervals. FIG. 14 includes a series of part-flow timing diagrams arranged in chronological order. FIG. 14b immediately follows FIG. 14a in time, FIG. 14c immediately follows FIG. 14b in time, and so on. Each row in the figures is numbered according to a specific part number and the horizontal axis represents increasing time. An interval is defined as the period of time between a "Y finish" and the immediately following "Y finish". In FIG. 14a, subsystem Y requests a part after a cycle time CT.sub.Y of 55 seconds (see (1). Subsystem X is able to deliver a part for this early request because machine M.sub.d2 has completed its process and waits for part number 2 to be picked up (see (2). Thus, when subsystem Y completes its cycle CT.sub.Y, part number 2 is immediately provided. As a result, the throughput time (from "Y finish" to the next "Y finish") is 65 seconds. In FIG. 14b, CT.sub.Y is shown as 65 seconds. There are only four transport tasks, i.e. (1,2), (3,4), (5,6), and (7,8) in the first interval. It is required that a no-transport-time duration of 20 seconds (indicated by two vertical lines and the x's) be available to handle variations in the cycle time CT.sub.Y of subsystem Y. Consequently, transport task (9,10) cannot be performed during the first interval of FIG. 14b and is instead delayed to the next interval (see 3). The effect of the incomplete interval is first manifested in the elongation of subsequent sending periods as well as immediate increase shown in FIG. 14b. Some of the subsequent sending periods are longer than the 75 second fundamental period FP based on the 65 second cycle time CT.sub.Y of subsystem Y. Unless there is a sufficient number of short sending periods to compensate for the effect of the long sending periods, the system 10 will not be able to produce parts per its nominal FP of 75 seconds due to the shortage of parts introduced into the system 10. For the intervals up to and including FIG. 14d, subsystem X manages to follows the rate of requests from subsystem Y. In FIG. 14e, however, there is no part in subsystem X ready to satisfy a parts request from subsystem X (see (4). As a result, subsystem Y must wait for its next part. In the first interval shown in FIG. 14f, subsystem X regains its ability to immediately satisfy a parts request from subsystem Y (see (5). However, the no-transport-time condition in the next interval produces a long sending period of 100 seconds (see (6), which returns the system 10 back to the shortage state. FIG. 14g illustrates another instance of delay in part delivery from subsystem X to subsystem Y (see 7). FIG. 14g is the same as FIG. 14e, thus it is apparent that the system 10 achieves a steady state and that an extension of the part-flow timing diagrams of FIG. 14 is simply a repetition of FIGS. 14f and 14g. Subsystem X is faster than subsystem Y when the cycle time CT.sub.Y of subsystem Y is 65 seconds (FP.sub.Y =75 seconds). Thus it might be expected that subsystem X 20 would evolve to a steady state operation such that the fundamental period FP of the system 10 is 75 seconds. This is the case if the cycle time CT.sub.Y is 65 seconds without exception. FIG. 15 shows the steady state operation under such a condition. Location of the no-transport time is fixed relative to the other robot moves, thus the same part-flow pattern is established in steady state. FIG. 14 demonstrates, however, that a single occurrence of a 55 second cycle time CT.sub.Y combined with an attempt to run subsystem X above its maximum speed results in a degradation of system performance. As a result, the system 10 cannot even maintain a fundamental period FP of 75 seconds at which it otherwise can operate. Every fourth interval, subsystem Y must wait for an additional 25 seconds. Thus its average throughput time in steady state is 81.25 seconds (i.e., (75+75+75+100)/4 seconds). Since the system is in steady state, the average sending period is the same as the average throughput time. In the immediately preceding example, the longer interval of subsystem Y does not compensate for the shorter interval of subsystem Y. Even in the longer period, in order to cover the full range of variation in cycle time CT.sub.Y, subsystem X should complete its cycle (process and transport) within the minimum cycle time CT.sub.Y of subsystem Y, leaving enough time to accommodate the no-transport time. If subsystem X cannot complete a cycle CT.sub.X within one interval of CT.sub.Y, the scheduling problem becomes a time-dependent combinatorial complexity problem lacking periodicity. As a result, opportunities for non-optimal scheduling decisions increase and the overall system performance can degrade. To establish time-dependent periodic complexity in the case of the present example, subsystem X is initialized upon a request by subsystem Y if the request occurs at or after the expiration of the fundamental period FP.sub.X of subsystem X. If the request occurs prior to the completion of the fundamental period FP.sub.X, subsystem X is initialized at the expiration of the fundamental period FP.sub.X. In other words, if subsystem Y requests a part at a pace faster than pace of subsystem X, initialization must wait until the fundamental period FP.sub.X has ended. Under this limitation, the scheduling procedures used in cases 1 and 2 can be applied to the present example. FIG. 16 shows the remaining process times and state of each machine at the moment of initialization (see 0 (in FIG. 14a). The no-transport time is determined to be the duration between 70 seconds and 85 seconds after the moment of re-initialization. The time from 65 seconds to 70 seconds is excluded from the no-transport-time because, as previously described, the re-initialization cannot occur before the fundamental period FP.sub.X of 70 seconds has expired. Prefixed transport tasks (1,2) and (3,4) are allocated within the no-transport-time interval. The other transport tasks are assigned based on the fundamental conditions of part transport. If necessary in the later part of interval, a finished part in machine M.sub.d2 does not leave until another part request is issued by subsystem Y. One possible schedule is shown in FIG. 17. The invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The foregoing embodiments are therefore to be considered in all respects illustrative rather than limiting on the invention described herein. The scope of the invention is thus indicated by the appended claims rather than by the foregoing description, and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein.
|
Same subclass Same class Consider this |
||||||||||