Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-05-11
2001-02-06
Gordon, Paul P. (Department: 2786)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S096000, C700S101000, C705S002000
Reexamination Certificate
active
06185469
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to manufacturing systems and assembly lines, and more particularly, to methods and apparatus for designing and controlling the operation of flexible manufacturing systems and assembly lines.
2. Description of the Related Art
Some structures and concepts that are useful for describing manufacturing systems are defined as follows:
Work pieces are objects and materials that are changed and combined to make a finished product;
Jobs are operations that change or combine the work pieces;
Resources are machines, humans with tools, fixtures, transport devices, and buffers that perform the jobs on the work pieces;
Assembly line is a circuit that the work pieces follow between the resources that perform the jobs;
Workcell is a physical portion of the manufacturing system; and
Flexible manufacturing systems (FMS) are assembly lines or workcells, wherein the timing of the jobs or assignment of the resources is flexible.
The design and operation of a workcell involves two steps. First, decisions are made on the sequencing of jobs to be performed on individual work pieces. Normally, the job sequence is based on, at least, some considerations external to the form of the workcell. Second, decisions are made on the control of the workcell that will perform the predetermined job sequence. These control decisions involve the assignments of particular resources to the jobs of the predetermined sequence. The control decisions entail starting jobs and releasing resources when jobs are done. The control decisions may also entail choosing among different resource assignment possibilities when several resources can perform a job, and resolving priorities when several jobs are simultaneously assigned to the same resource.
FIG. 1
shows a simple workcell
6
whose operation involves such control decisions. Work pieces
8
follow a fixed circuit
10
from an input
12
for raw work pieces
14
to an output
16
for finished products
18
. At the input
12
, the raw work pieces
14
are attached to pallets
20
that facilitate handling. The pallets
20
are removed from the finished products
18
at the output
16
and automatically returned to the input
12
. First and second machines
22
,
26
perform jobs. For example, the first and second machines
22
,
26
may drill holes and cut the work pieces
8
, respectively. The input of the second machine
26
is a buffer
24
that can hold up to two work pieces
8
simultaneously. The raw work pieces
14
are moved automatically from the input
12
to the first machine
22
, and from the buffer
24
to the second machine
26
by conveyers
28
,
30
. A robot arm
32
transports the work pieces
8
from the first machine
22
to the buffer
24
and from the second machine
26
to the output
16
. The resources of the workcell
6
of
FIG. 1
are the first and second machines
22
,
26
, the buffer
24
, the robot arm
32
and the pallets
20
.
Though the illustrative workcell
6
of
FIG. 1
is simple, its operation involves non-trivial control decisions. First, the robot arm
32
performs several jobs
34
,
36
. The first job
34
is to transport the work pieces
8
from the first machine
22
to the buffer
24
, and the second job
36
is to transport the work piece
8
from the second machine
26
to the output
16
. The first and second jobs
34
,
36
of the robot arm
32
are mutually exclusive, i.e. cannot be performed simultaneously. Thus, the operation of the robot arm
32
can encounter conflict situations where both the first and second jobs are requested simultaneously. Second, the buffer
24
and pallets
20
are resources in multiple copies. The buffer
24
has two spaces
38
for holding the work pieces
8
, and there are several pallets
20
. Multiple copies complicate controlling the assignment of the resources to the jobs. The multiple job and multiple copy resources introduce flexibility into the control decisions and make the workcell
6
of
FIG. 1
a FMS.
A FMS is a discrete event (DE) system. DE systems are defined by a set of event-states and transitions between the event-states. In the workcell of a manufacturing system, the event-states are the states of the resources, i.e., rest states and job performance states, the inputs for raw work pieces and outputs for finished products. The transitions are the acts of starting and stopping resources, i.e., transitions from rest states to job performance states and vice versa. The transitions involve the substantially simultaneous movement of the work pieces between inputs, resources, and outputs. The event-states and transitions of the DE system can be represented by a directed graph or Petri net (PN). In the PN, the event-states and transitions are represented by circles and vertical lines respectively. Directed lines indicate the transitions of the work pieces and of the resources between the event-states. The event-states and transitions alternate along the directed lines of the PN. While the resources of the workcell occupy two types of event-states, rest event-states and job event-states, the work pieces only occupy the job event-states, inputs or outputs.
FIG. 2
is the PN of the FMS of FIG.
1
. The job event-states of the first machine
40
, buffer
42
, and second machine
44
lie along a straight line
46
representing the circuit of work pieces
8
of FIG.
1
. The robot arm
32
has both first and second job event-states
48
,
50
along the same straight line
46
. The rest event-states of the first machine
52
, buffer
54
, second machine
56
, and robot arm
58
are off the circuit
46
of work pieces
8
. The job event-states of the pallets are the job event-states of the other resources
40
,
42
,
44
,
48
,
50
, because the work pieces
8
are attached to the pallets
20
while moving along the circuit
46
. The pallets have a rest event-state
60
between the first transition x
1
after the input event-state
62
and the last transition x
6
before the output event-state
64
. At these two transitions x
1
, x
6
, the pallets
20
are attached and removed respectively from the work pieces
8
.
In a PN, the time dependent occupation of the event-states by resources is indicated by marking the circles representing the event-state with dots. At the time represented by
FIG. 2
, the workcell
6
of
FIG. 1
has four pallets
60
, one first machine
52
, two buffer spaces
54
, one robot arm
58
, and one second machine
56
occupying rest event-states
60
,
52
,
54
,
58
,
56
. At the same time, there is one raw work piece
14
of
FIG. 1
at the input event-state
62
. The work pieces
14
make transitions x
1
-x
6
between job event-states along the directed circuit
46
. The pallets
20
of
FIG. 1
make transitions between different job event-states x
2
-x
5
except for transitions x
1
, x
6
at the input
62
and output
64
, which are transitions between rest and job event-states
60
,
40
,
50
. The other resources only make transitions between job and rest event-states. Time dependent transitions between event-states ordinarily change the markings, e.g., occupations, of the circles of the PN.
Since PN's faithfully represent all event-states, the prior art has employed PN's to the design and to analyze the operation of FMS's. The prior art use of PN's to design controllers of workcells had limitations. First, the analysis of practical FMS's through PN's is complicated. For designing automated controllers, simpler techniques are preferable. Second, the PN technique requires a separate graph to represent each time state of the workcell. Thus, PN's do not present a straightforward method for analyzing the time evolution of the workcell. Automated controllers cannot simply determine from a PN how to operate the workcell. Third, the prior art based the design and control of PN's on “top-down” and “bottom-up” designs by using rules such as series mutual exclusion, parallel mutual exclusion, and forbidden states of resource allocation. These
Gurel Ayla
Lewis Frank L.
Pastravanu Octavian C.
Tacconi Diego A.
Board of Regents , The University of Texas System
Fulbright & Jaworski LLP
Gordon Paul P.
Rodriguez Paul
LandOfFree
Method and apparatus for testing and controlling a flexible... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for testing and controlling a flexible..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for testing and controlling a flexible... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599086