Note: Descriptions are shown in the official language in which they were submitted.
WO 93/05~76 2 1 1 6 9 ~ 2 PcrJuS92/~75~4
-1 -
MErHoD OF CONST~NT RATE OF PRODU~rlON SCHEDULlNq
BACKGROLIND OF THE INVENTION
1. Field of the Invention
This invention relates generally to a method of managing repetitive tasks, and more
5 speciflcally to a process which applies th~ critical path rnethod ~o repetitive tasks
having eorlstant rates of production.
2. ~escription of R~lated Art
Complex projects consist of a plurality of interrelated tasks. Optimizing production
schedules. ~or large projects requires the synchronization of these tasks. Many of
10 these tasks are pefformed on a plurality of individual units, and may be termed
Urepetitive~ tasks. Examples of repetitive tasks are ~ound in a wide variety of settings,
including factory assembly lines and construct~on sites. Staking out individuai lots for
a tract-home subd~vislon, mounting pTcture tubes to television se~ cabinets, andbolting transmiss~ons to ~ngines illustrate var~ous b~pes of repetitive tasks within larger
1 5 proJects.
,
One method of planning production schedules consisting of a plurality of repe~itive
tasks is known as the line of balance m~thod, also referred to as the constant rate
of produc~ion m~thod. Q tw~climensional ~raph ~5 manually produced, whers ~he
axes are the n~m~er of completed unHs and time. FIGURE 1 is a graphical
20 representation of continuous rates of production fc~r a plural~ty of interreiated tasks.
The X-axis is labelled in un~s of time such as days or hours. ~rhe Y-axis is labelled
to designate the individual units on which tasks are to be parformed. The work
performed by a crew oompletin~ a task îs shown on the graph as a line havin~ a
slope proportional to the output for that task. In a factory environment, the graph
25 may be used to indicate the ou~pu~s of work stations along an assembly line.
WO 93/05476 PCr/VS92/07~04
21169~2 -2-
Unes havin~ steep slopes indicate tasks tor which the rate of completion is ralatively
rapid, whereas lines having more horizontal slopes indicate tasks for which the rate
of completion is slow. Many of these tasks have precedence relationships, meaning
that a given task canno~ b~ per~orm~d until one or more previo~ls tasks have been
5 completed.
,,
If a flrst task has a precedence relationship with a second task, the lines representing
the tasks on the constant rate of production graph must not intersect or cross. This
constraint is used to optimize schedules for multi-unit projects. Howev~r, in order to
synchronize all tasks, a large number of graphs must be anaiyzed and manipulated,
10 rendering this method tedious, complicated, and impractical for large, complex
projects.
Another example of a line~of balance calculation îs shown ~n FIGURE 2. The line of
balance specmles the types o~ components which must be available at speciflc points
in time to achieve a constant rat~ of production. A shortcoming of the line o~ balance
: 15 method is that tt is very dtfftcult to- update the graphical displays to reflect progress
that devtates from the~ original schédule, or unexpected delays. In many cases,
virtually the entire~series~of graphs has to be;redtawn to provide an accurate, updated
schedule. In pr~lce, however, line~l-balance graphs are seldom updated, due to
the dtmcu~ involved.
20 tt is possible to automate ~the calculation of line~f-balance graphs. Howevet,
currently available automated representaUons merely present graphical or tabulardisplays comparing the~ projected total units compléted at given points in time wkh
the actual number o f units completed. Thus, these displays are not used to calculate
production schedules~or to identNy which unit is scheduled at which time.
25 FIGURE 3 is a graphical representation of another prior-art method for schedule
plannin~, termed the critical path method ~CPM). CPM analyzes a compl~x project
`
WO 93/05476 2 1 1 6 9 8 2 Pcr/usg2/o7so~
by dividin~ the pro~ect into individual tasks wHh ser~al and parallel time-precedence
telationships. Serial relationships refer to interdependent tasks, where a first task
must be completad pr~or to commencTng a second task. Parallel relationships involve
tasks which may be implement~d simultaneously. The intcrrelationships between the
5 tasks may be modeled as a network. ~ach task is represented by a point or nodeon the network. A start date ~s specified for the nrst task, and a duration is assigned
to each task.
By way of back~roundj H is also important to understand two spec~al aspects of CPM.
First, there ar~ a mJmber of types of relationships be~Heen two logically~onnected
10 tasks. The standard relationship is called Finish-Start, and means that task A must
finish before task B can start. Another type of relationship ~s called Start-Start, and
means that task B can start after task A has started. A time lag can also be applied
to these relationshlps. For example, it task ~ is preceded by task A with a
precedence relat~onsh~p of type Start-Start with a time lag of 2 days, task B can start
15 2 days after task A has ~started.
The second special aspact of CPM ~s that ttlere are a number of special types ofconstraints, or plugs~t~ that~ can be applied to a work item above and b~yond the
logicai relationships.~ One of these constraints is As-Late-As-Possible (AIAP). ~ an
AlAP plug is assigned to the ear~y start~date of task A, then the early start date will
20 be delayed as much as posslble, i.e., un~il any 1urther delay would cause negative
~oat (deiay of a required due date further in the network).
The CPM ~cheduling process accepts data representing the coded netNork
- interactiveb and/or in batch mode. A forward pass and backward pass are executed
throu~h the nstwork to~ establish dates and priorities 1w ail tasks in the network.
25 During the fonNard pæs, the eariiest possible start and finish dates for sach task are
determined in a step-wise fashion. The process commences at the project startingdate and the dura~ions of individual tasks are added to the starting date, until an
WO g3/05476 PCI`/US92/07~0~
2116982
expected tinish date is determined. The earliest start date of a task is equal to the
latest startin~ date of the preceding tasks plus the duration of the preceding task.
The finish date of each task is its start date plus Ks duration, minus one working day.
In this manner, the finish date of the last task determines the completion date of the
5 project.
The backward pass through the network performs the aforementioned operations in
reverse order to establish the latest possible completion dates. The latest possible
completion date may be defined as the last date for which a task may be accom-
plished without missing the target project completion date. The difference between
10 a task's earliest poss~ble completion date and latest possible completion date is
termed "slack" or '~loat'1.
The path of work items through the network which has the longest cumulative
duration is known as the critical path and usually will be equal to the project duration.
Items along this path~will have zero float, indicaUng that delay of any one of them will
15 delay project complation. Items not on the critical path have positive total tloat. CPM
reports incll:de tabular reports (FIGURE 4j ancl Gantt or bar char~s (FIGURE ~).
The critical path method (CPM) is a comparatively recent engineering developmentparticularly adapted~for~use;in the constructioh industry ~or the planning and
scheduling of construction activities. For a detailed analysis ot CPM, reterence is
20 made to the book entitled ~PM IN CONSTRUCTION MANAGEMENT, Second Edition,
by James J. O'Brien ~McGraw-Hill Book Company, 1~71).
;
AHhough the critical path method provides a useful tool for schedul0 planning, the
amount and complexi~y of data entry required to use CPM for repetitive jobs, and the
volume ot printed reports required;to interpret the schedules, renders S::PM practical
j j ;~ 25 for only a small number o1 repet~tiv~ tasks on a small number of jobs. For example,
a typical oonstruction trac~of 100 homes requiring 150 tasks per home wouid invdve
~: :
I
wo g3/05476 2 1 1 6 9 8 2 Pcr~us92/o7so4
data entry of 15,000 tasks and determination of at least 30,000 precedence relaUon-
ships. Using the most compact reporting format available, such a report would
generate several hundred pages of data.
One method of representing CPM tasks by two dimensional geometric objects is
shown in U.S. Patent 5,016,170, iss~ed on May 14,1991 5/1991 to Pollalis. Pollalis
essenUally teaches a tool for manual optimization of resources (men per crew) across
dissimilar tasks. Although a mechanism is described for replicating templates, H is
applicable on~ to simple reproduction and uses a matrix solution and graphical
representation wh~ch is suitable only for small problems. (rhe 100 home tract
example g~ven above, with 150 tasks per home, would requir~ about 200 bytes per
task per home, requiring a matrix of 3 million bytes. This is about 50 times ~he~, maximum capacity of most compilers). Further, Pollalis teaches an iterative approach
that requires user-~nteraction to successively improve a heuristic solution. A direct
solution would bo preferable.
~, lS Another prior-art me~hod o~ production scheduling has been cmployed in environ-
ments such as factory assemb~y lines. MRP ll (Manufacturing Requirements and
Planning) for assembly line scheduling is basod on heuristic solutions of dfflerent
¦ capacity resource planning aigori~thms addressing idle machine time and uncompleted
assemb!ies. ~ This~ approach, plus tho inherent changeability of data and size of the
problems considered here, render MRP ll unsuitable for schsduling a large numberof repetitive tasks. ~
~,
~ What is needed is a pra~tical method for scheduling tasks which is adaptable to
!
relatively complex projocis having numerous repetitivo tasks. The scheduling method
should be flexible to allowfor *equent updates in accordance wdh actual job progres-
I
sion. Tho method ~should ~also provide ease of updating. The graphical o~put
should provide essential scheduling information in a concis~, easily-interpreted format.
~::
WO 93/05476 PCr/US92/07504
211~982
Furthermore, required data providing and ~ata entry operations shollld be kept to a
minimum and be capable of being performe~ with minimal traininy and expertise.
The present invention provides such a m~thod.
WO 93/05476 2 1 1 6 9 ~ 2 PCI/U592/07504
SUMMARY OF THE INVENTION
The invention provides an improved process for scheduling production tasks. The
process combines the constant rate of production method with the critical path
method, thereby providing an enhanced process for creating a production schedule.
5 The process allows a user to plan a schedule and to track progress of repetltive tasks
for large and complex pbs. The process requires minimal data entry, and may be
updated to reflect actual jol~ progress. A production schedule Is produced in a
concise, easily-interpreted format.
The process commences when a user enters task data into ~ data processing device.
10 The user nced not enter data for all ~he units of a given job; task data pertaining to
one unit is suf~cient. This data pre~erably includes the description, duration, and
preceding work items for each task~ Each task ~s assigned a unique code number.
1, Next, the user specifies the tasks which are to be repeated on additional units. For
`! these repetitive tasks, the user may also enter the number of units to be completed
15 per day, the number ot crews or work stations per task, and the minimum number of
unns required for contlnuous work. The total number of units to be producsd Ts also
i ~ speci~led.
From the entered information, the data processing device determines a sequence, for
reporUng purposes, of re~etitive tasks for a single UtemplateU unit. The sequsnce is
20 determined by starting~ at the; first task to be performed and making a forward pass
1~ ~ through subsequent tasks. The earliest possible starting dates for th6 tasks are
`l determined, based upon the duration of previous tasks and the starting date of the
ffrst task.
rhe data for the ~mplate un,,t is transforrned into a criticat path method (CPM)25 network for an entire job ~by determining the repetitive tasks with their respective
~ ~ durations and prec~den~e relationships for each additional unit in the job.
3~:
WO 93/05476 Pcr/~s92/07So4
2116982
Precedence relationships between same tasks but dfflerent units must also be
considered, These latter precedence relationships take into account the movementof crews through units and/or thc movement of un ts throu~h work stations. Special
constraints may be Incorporated ~nto the network in order to provide continuous work
5 for the crews,
The data processing device u~ilizes the CPM network to calculate earliest and latest
possible starting and ~mishing dates for each task performed on each unit, The latest
possible starting date is the last day for which a task may be started which permits
the project to be finished on time, The calculation of early and late da~es is imple-
10 mented using CPM techniques which are well-known. In particular, earliest possible
start and flnish dates are calculated by conductin~ a first forward pass through the
data, Next, ~he latest possible start and finish dates are calculated by conducting a
first backward pass through the data.
To calculate schedule dates for continuous work, a second forward and backNard
15 pass is conducted, replacing early dates with late dates, In this manner, a planning
:
schedule consisting of start and finlsh dates for each task and each unit is crcated,
The schedule is displayed~in a form which i9 an Improvement over traditional Gantt
bar charts, A time line is dbplayed o n the X-axis, and configured so that each
column can accept muiti4ign uni'l numbers. A list of work items is displayed on the
20 Y-a~aæ, and includes only~those tasks which are repetitive in na~ure. Conventional
horizon~al bars within the schedub; showing the start and finish dates for each task
have been replaced by the unit number being worked on. The unit number is aligned
to indicate the corresponding ~task at the X-axis, and the corresponding date at! th~
Y-~xis. ~ ~
25 The CPM network may be~ modified throughout the course of a job, as desired,
Completed tasks are ~ntered into the data processing device and are then removedfrom the schedule of remaining work, In this manner, an updated schedule is
~; :
WO g3/05476 PCr/USg2/07504
2~1698~
calculated which optimizes production based upon actual task progress and planned
performance rates. The up~ated schedule reflects the most efficient mann~r in which
the remaining unfinished tasks may be completed.
The present invention plans the schedule and tracks the progr~ss of repetitive work
5 for relatively complex jobs using a method that requires minimal data entry. The
schedule ~s presented and progress data are accepted ~n an intuHive and compact
form.
The method of the invenUon converts graph~cal representations from a line of balance
format into a tabular format that ~s intuitive and compaot and able to be produced by
10 automated nongraphical means ~i.e. character mode as opposed to all-points
addressable or bit-mapped mode). The method creates and utilkes an inference
machine that sccepts as ~input the ~PM n~twork for one unit and determines the
various ways to create the CPM network for mulUple unTts with the special line of
balance constra~nts. T he CPM calculation method is employed with modfflcations to
15 meet special line~of balance constraints. Progress reporting da~a is accepted in
tabular or graphical format and ;converted into ~CPM data.
!: ~ The details of the~preferred embod~ments of the pre$ent invention are set forth in the
accompanying drawings and~ the~ description below. ~ OncP thé details of the invention
are known numerous addTtional innovations and changes wUI become obvious to one
l ;~; : :
20 skilled in the art. ~
W~ 93/05476 PCI/US92~07504
2 1 1 6 9 8 2 -1 ~
E~RIEF DESCF~lPrlC~N OF THE DRAWINGS
FIGURE 1 is a prior-art manual ~raphical representation ot the constant rate of
production rnethod.
FIGURE 2 is a prior-art graphical representat~on of the line o~ balance method.
5 FIGURE 3 is a prior-art graphical represen~ation of the critical path method.
FIGURE 4 is a prior-art schedule report setting ~orth a planned scheclule for
implementing a plurality of interrelat~d tasks.
FIGURE 5 is a prior-art Gantt bar chart setting torth a planned schedule for
implementing a plurality o~ interrelated tasks.
10 FIGUP~ES 6 and 7 are flowcharts depicting the schedule planning method of the present invention.
FIGURE 8 is a chart illustra~ing the in~ormalion whish is input to the sohedule planning
method of the preferred embodimerlt of the present inv~ntion.
:
FIGURE 9 is a chart illustrating ~the information which is output by the schedule
16 planning rnethod o~ the preferred embodiment of the present invenUon.
FIGURE 10 is a tlowchar~ illustrating the process of ereating relationships be~ween
d~rent tasks to be performed on the same unit.
FIGVRE 11 is a flowchart illustfating the process of creating rela~ionships between the
s~me ~asks to be performod on dfflerent units.
WO 93/05476 2 1 1 6 9 8 2 PCI/US92/07504
FIGURE 12 is a flowchart dep~ct~ng the process of creating special constralnts for the
purpose of scheduling continuous work.
FIGURE 13 is a d~agrammat~c representat~on of exemplary relationships between a
plurality of interrelat~d tasks and a plurality of units.
5 FIGURE 1~ ~s a schedule printout which illustrates the results of the implernentation
of special cons~raints to provide continuous work.
Uke re~erence numbers and designations ~n the drawings refer to like elements.
!
: ~ '
W~ 93/05476 P~/US92/07504
211 6982 12
,
DETAILED DESCRlPrlON OF THE PREFERRED EMBODIMENT
/
Throu~hout this description, the preferred embodiments and exarnples shown should
be considered as exemplars, rather than limitations on the prcsent invention.
Ov~rview of the Inv~ntlve Process
FIGUP~E 6 illustrates the scheduling method of the present invention, which combines
the line-of-balance method with CPM. In describing FIGURE 6 and subsequent
3 drawings, a CPM network for a single "template" unit is denned as comprising a
plurality of Utasks" (e.g., Ustake lot~, Udrill toundat~on~). The term ~work item" ~WI) is
defined to be a task performed on a particular unit on a job.
10 The invention generates a CPM network from the ternplate unit CPM network in which
each Work Item (Wl) for a job is represented as a node Wly~ In this notation, j equals
the task code and I equals the unit number. Thus, WljJ represents a Work Item
; comprising task j performed on unit i (a third index, for job number, could be used,
but is generally omitted for purposes of clarity). Work Items having j ~ O indicate
15 tasks for the template~ unit. An~ example o~ the Wl codes thus formed is shown in
FI~URE 5. The Wl code~-1 002-106" refers to Task #106 (Drill Foun~ation) to be
performed on Unit #002~for Job #1 (Bush Hill development).
I
Referring now to~FlGURE 6, in step 1, a user enters the task data for a single
''templateU unit (i.e., any one of the actual units for the job~ into a computer. This data
20 includes the code, desaiption, duration, andlor preceding tasks for each task (for all
Wl0I where j = 1,....,n). ~ FIGURE 8 shows a chart illustrating an example of the
information which is~ input to the sehedule planning method of the preferred
embodiment of the pr@sent invention.~ The task data for the single template will be
used as a template for creating the~ CPM nctwQrk tor multiple units.
',
:
wo g3/0s476 2 1 1 6 9 8 2 P~/US92/o7504
In step 2I the user specifies which tasks are to be repeated ~n additional units. For
these repetitive tasks the user enters:
a. the number of units required to be produced per day if > 1;
b. the number of crews or work stations per task if ~ 1;
5 c. the minimum number of units required for continuous work if > 1 (the
minimum number o~ units required for continuous work may be deflned as the
bucket size ).
This data is shown in FIGURE 8 as being entered into correspond~ng rows with thebasic task data for the template unit.
10 In step 3 a defauK sequence for listing the repetitive tasks in reports (i.e. down the
Y-axis as shown in FIGURE 9) is determined by the computer from the data enteredin steps 1 and 2. ~A suitab~e defaun sequence ~s obta~ned by performing a CPM
forward pass on the ~template and using a sorted listing of the early start date for all
tasks to define~the~default sequence. A user rnay override the defauK listing
15 sequence if desired.
~ :
In step 4 the user~ specifles ~e number of units m to b~ produced. In step 5 a CPM
n e~rkdatabase~is~created~*omthe;inputdata. TheGPMnetworkdatabase
cQnsists of ~
a. ~a~CPM~;networkfor~the~single~template un~t (inc~uding any non^repetitive
; ~ ~ 20 - ~ tasks);~
b. the repeti'ive~;tasks vhth their durations for esch additional unit (i.e. all repetitive Work ItemS Wl~
c. ~ pr~ecedencerelationships~betweendilferenttasksperformedonthesame!unit
for all~ units (see~FlGURES ;lO and ~13);
25 d. precedence~relationships~ èen the same tasks performed in dmerent units
that take into ~consideration the movement of crews through units (or units
through work statlons) (see FIGURES 11 and 13);
e. special constraints to implement bucket size (see FlGURES 12 and 14);
... . . .. , .. , . : . . . .. , . , ., .,, ., . . , , . ., .. . , .. . ... . . , ., .. . ,, . . . ~ , .. ...
.. ..
WO 93/05476 PCI'~US92/07S04
211~ 9 8 2 -14-
t. extra intermediate sequencing to add new rows in reports where needed for
multiple crews and multiple units per day ~see FIGURES 9 and 11)
Greater detail as to the preferred m~thod for generating such information is set fonh
below in conjunction with the description of FIGURES 1~14.
Next, in step 6, the CPM method of calculation is applied in known fashlon to the
CPM network thus created ~n order to compute the early and late start and finishdates for each Work Item Wly Automated cornputation of CPM networks is well
known ~see, e g, O'Brien, "Schedulin~ Handbook", McGraw-Hill, p. 47, with references
on p. 72 and p 143). The extension to the standard CPM procedure used in the
present invention to accommodate the special ALAP cons~raints involves a second
forward and backward CPM pass in which early start and finish dates of the
constrained Work Item are replaced with late start and finish dates. In effect, this
secand pass delays the affected work items as mueh as possible For instance, refer
to FIGURE 14, where Task 134 rPour PiersU) has been delayed on units 3 and 4
:
In step 7, the computer creates a~ pdnted produotion scheduls, a copy of which is the
~tum-around" document to be lJsed by a field superintendent. The preferred ~ormat
of the~turn-around report is shown in FIGURE 9, and is an improvement to prior art
Gantt (bar) charts (see~ FIGURE 5). The preferred report format dfflers from a Gantt
char in that~
20 a the tirhe-line (X-axis)~is~ spread out so that each column can aGcspt at least a
muHi-digit unit number ~ ~
b. the lengthy list~of work items Wl,l (Y axis) has bsen raplacsd by the shorter list
of repetHive tasks ~i e., Wlo~
c the horizontal bars that showed the start and finish dates of a work item havs
been replaced by~a unit number on which the task shown on the Y-axis is to
be performed for the date shown on the X-axis;
d. the report format displays the progress required to achieve a constant rats of
production (orUlin- of balance"~.
WO 93/05476 2 1 1 ~ 9 8 2 Pc~/us92/07504
-1~
Next, at step 8, progress on the job is reported. Pre~erably, a fleld superintendent
marks the completed tasks for each unit on the turn-around document. After marking
on the report the completed work at a ~iven c Jt-off date, the report is returned to be
used for purposes of additional data entry to prepare an updated turn-around repon.
5 Step 9 involves the creation of an on-line ~i.e., viewed interactively on a computer
terminal) computer display that is essentially a visual duplicate of the turn-around
document. While the unit numbers referred to in step 7c above are depicted as
simply a row of numbers printed on paper, for interactive data entry at a computer
terminal, it is preferable to use discrete fields on discrete records for a data entry
10 clerk to rnodify
In step 10, the data entry clerk enters ~nto the computer the completed task and unit
information indicated by the entries made by the field superintendent on the turn-
around document This may be done, for example, by overwritin~ with a zero each
displayed unit number for which a task has been completed
15 In step 11, the computer updates the original database from which the CPM network
was computed by marking as completed those Work ltems Wly in the database corre-sponding to the entries made by~the data entry clerk Steps 7 ~hrough 10 associate
tasks w~h units, for compactness of presentation of the production schedule (FIGURE
9) ~ The data captured in step 10 has to be translated back to Work ltems Wlll This
20 is done by dedudng~ which Work ttem Wlq corresponds to each field that the data
entry clerk has màrked as completed Each such Work nem Wlj/ then gets its
remaining duration set to zero. When the CPM nehNork is recalculated, work Ttemswith remaining duration~equal to zero are considered completed and the updated
schedule is thus calcutated
:::
.
:: :
1, WO 93~05476 PCI~/US92/07504
2116982 -1~
~;
For exampls, r0~erring to FIGURE 9, if unit #1 on Jun~ 4 is set to .0u, then it i~ simple
to deduce that task ~100 ~Stake Lot) has bsen completed for unit ~1, meanin~ that
the network node for Work Item Wl~ 100 will have its duration set to "~'.
In step 12, steps 6 through ~2 are repcated using the modifled CPM n~twork
6 database every update, until the end of the project
Flowcharts Explaining Generation of CPM Ne~work
In further explanation of the preferred embodiment ~f the present invention, the details
of the sub-steps described above with respect to step 5 are set forth below.
FIGURE 10 is a flowchart illustrating the process of creating precedence relationships
10 between different tasks to be performed on ~he same unit The process is repeatedly
performed in a series of nested loops The innermost loop repeats the process forevery template relationship. Relationships between current work items and preceding
work items are cstablished. A mid-level loop repeats the process for every unit i from
1 to m. The ou~ermost loop ~repeats the process for every template work item j from
15 1 to n.
The program commences at block 1000, where the next preceding work rtem related
to the current work item is read from the input shown in FIGURE 9. A test is
performed at block 1002 to see~whether the current or preceding work items are
repetnive. If not, the program loops back to block 100~. If the current and/or
20 preceding work items are rep~titive, the program proceeds to block 1012, where a
test is performed to detcrmin~ whether or not the current work item is repeti~ive! but
the preceding item is~ not repetitive. n these conditions are met, a data record is
created linking thc~current itcm to thc non-repetitive precedîng item in a precedence
relaffonship, at block 1018. ll~e current work nem-preceding work item precedence
; ~ 25 relationship data record is added to the CPM network database at block 1022. The
program then loops back to biock 1000, where the next work item is read.
Wo ~3/0s476 2 1 1 6 9 8 2 PCr/US9~/07sO4
-17-
1~ the conditions at block 1012 are not met, program control transfers to block 1014,
where a test is p~rformed to determ~ne whether or not the current work item is not
repetitive but th~ preceding tims is repetitive. If these conditions are m0t, the
preceding work time is linked to the current non-repetitive item at block 1020, and the
current work item-preceding work item precedence relationship data record is added
to the CPM database at block 1oe2. The program then loops back to block 1000
where the next work item is read. The negative branch from block 1014 leads to
block 1022.
FIGURE 11 is a flowchart illustrating the process of creating precedence relationships
between the same tasks to be perf~rmed on different units. The program is executed
repeatedly within a series of nested loops, as previously described with reference to
FIGURE 10. The program commences at block 1100, where a work item data record
(~rom the input shown ~n FIGURE 9) is read, and then proceeds to block 1101, where
the program tests to see whether the current work item is repetitive. If not, the
program goes on to the next work item at block 1100. ~ so, the program continuesto block 1103, where a test is performed to determine whether or n~t the number of
crews for the work item ~s greater than 1. The affirmative branch frorn block 1103
leads to block 1105, where the relationship is identified as a start-start relationship.
The unit coun~r is incrernented, and at block 1107 the uni~ counter is divided by the
number of crews. The result is an inte~er M and a remainder BB as indicated at
block 1109. The remainder BB is placed into a unit table (table J) at b~ock 1111.
Table T is used to indicate that extra intermediate sequences of tasks are needed for
reporting pwposes, resulting in the addition o~ new rows in reports to indicate
multiple crews and multiple~ units per day. An example o~ such added rows is shown
in FIGURE 9, where tasks 100 and 140 have multiple row entries.
In block 1113, the duration of the work item is divided by the number o~ crews. The
result is an integer CC and a remainder DD, as shown in block 1115. Block 11~7
i ~ 7 ~ / ~ L J " -'
t3~ dPCTlFr~ ,4p~ ~93
2116982
tests to see whether or not the fsmainder DD is greater than zero. tf so, 1 is
added to CC at block 1119, and the program progresses to block 1121. If the
remainder DD is not greater than zero, the program progr0sses diraclly to block
1121. In block 1121, the precedence relationship time lag i~ set to CC The
5 current work Ttem-prec~ding wdrk item precedence relationship data record (which
includes the time lag) is added to the CPM database at block 1123, and the
program loops back to block 1100.
The negative branch from block 1103 leads to block 1131, where the program
checks to see whether or not the number of unU~ per day is greater than 1. If not,
10 the program jumps ahead to block 1123, where the currënt work item-preceding
work item precedenee relationship data record i~ added to the CPM database. if
the nurnber of unKs per day is greater than 1, the unit counter is incremented at
block 1135, and the counter is divided by the number of units psr day at block
1137. The resuH of the division is an integar EE and a remainder FF, as set forth
15 in block 1139. At block 114i, the remainder FF is placed into table T. A test is
performed at block 1143 to ascertain whether or not the remaTnder FF Ts greater
than zero. ff so, the pro~dence relationshlp is TdentHTed as a start-start
relationship at block 1145,~and the program then ioops to block 1123. If the
remainder FF i~ not greater than zero, the program pro~r~sses to block 1123,
20 where the curr~ent work item-precedin~ work nem precedence relationship data
record is added to the CPM database.
FIGURE 12 is a flowchart IUustrating the proce~ure fo~ crealing as-late-as-possible
(ALAP~ constraints, for ~e purpos~ of providing continuous work if ~easible. Theprocedufe is performed repeatedly, within a series of nested loops. The innermost
25 loop performs the procedure ~or every unit i = 1 to m. llle mid-level loop
performs the program~for every template relationship between a current work itemand a preceding work~ item. The ou~rmost loop perforrns the program for every
template work item trom j = 1 to n.
SUBST~TlJTE SI iEET
IPEA/US
WO 93/05476 2 1 1 6 9 8 2 PCr/US92/075~4
-19-
The program commences at block 1201, wherc a counter is initialized. Next, a~ block
1203, a test is performed to ascertain whether or not the current and preceding tasks
are both repetitive. H not, the pro~ram loops back to block 1201. Otherwlse, theprogram continues to block 1205, where the program checks to see whether or not
5 (1) the bucket size is greater than 1, and (2) the duration of the current work item is
less than the duration of the preceding work item. Bucket size refers to the minimum
number of units required to provide continuous work for a work crew. The negative
branch from block 1205 transfers pro~ram control back to block 1201. The affirmative
branch leads to block 1207, where the counter is divided by the bucket size. The10 result of this operation is an integer HH and a remainder KK, as shown at block 129.
The prograrn tests to see ~ KK is equal to zero at block 1211. If not, the program
loops back to block 1201; otherwise, the program continues to block 1213, where an
as-late-as-possible (ALAP) constraint for the current work item is added to the CPM
network database. The program then returns to block 1201.
15 FIGURE ~3 is a block diagram illustrating different groups o~ precedence relationships.
~ach block 1301, 1303, 1305, 1307, 1309, 1311, 1313, 1315, 1317, 1319 depicts a
wcrk item WljJ. Precedence reiationships between different tasks to be performed on
the same unit are denoted by arrows pointing in a horizontaî direction (e.g., between
b!ocks 1301 and 1303, blocks~ 1309 and 1311, biocks 1315 and 1317, etc.).
20 Precedence relationships b~tween the same tasks but dfflerent units are denoted by
arrows pointing downward and to the right (e.g., between blocks 1303 and 13~9,
blocks 1305 and t311~, blocks i311 and 1317, etc.).
FIGURE 14 is a diagram which illustrates the technique Qf bucketing to provide
continuous work for a work crew. In the exampîe shown, buck~ting occurs for the
25 task design~ted by~task code 134, ~pour piers"~ The work crew is schedulsd toperforrn this task on three consecutive days (June 13, 19, and 20) for three respective
units numbered 3, 4, and 5. Due to the precedence relationships bRtween the tasks,
providing contirluous work for the pier-pouring crew with respect to units 1 and 2 in
~; ~
`: :
WO 93/05476 PCl'~US92~07504
2116982 -2~
the present example would delay the job. The bucket for units 3, 4, and 5 is
implemented by startin~ work on unit 3 as late as possible without delaying the job.
Although it may be possible to perform task 134, "pour piersU~ on unit 3 earlier than
June 18, the crew would not be working continuously progressing to unHs 4 and 5.5 Therefore, these three units are Ubucket~d", so that work is scheduled so that the task
is performed on all three units continuously.
After the CPM netNork database is generated as described above, conventional CPMdata processing is applied to the database (taking into account all d~flned
precedence relationship types, time lags, and ALAP constraints) to generate a CPM
10 production schedule. From such information, plus the default reportin~ sequence
determined in step 3 and Table T, a report is generated in the format shown in
FIGURE 9. That is, each task in the CPM network database is listed at least oncealong the Y-axis in the sequence determined in step 3. Additional rows ara addedfor a task where ir~dicated by corresponding entries for that task in Table r. The work
15 item schedule dates determined when the CPM calculation was applied to the CPM
nstwork database~ provide the X-axi8 coordinates for each unit for each task.
SL~mrr.~
Thus, the present invention provides an improved process for scheduling production
tasks which ~combines~the constant rate o~ production method wHh the critical path
20 method. The method~ allows a user to ~plan a schedule and to track progress of
repetitive tasks for large ~and complex jobs. The process requires minimal data entry,
and may be readily updated to reflect actual job progress. A production schedute is
produced in a concise, easily-interpreted format.
Furthermore, the invention provides a one-step direct solution, rather than the prior
25 art iterative approach that required user-interaction to successively improve a heuristic
solutio~
WO !~3/05476 2 1 1 6 9 8 2 PCl'tUS92~075U
-21 -
/
A number of cmbodiments of the present invention have been described. Neverthe-
a less, it will be understood that various modifications rnay be made without departing
from the spirit and scope of the Invention. Accordlngly, tt is to be understood that
the tnvention is not to be limited by the specific illustrated embodiment, but only by
5 the scope of the appended claims.
,,
;l
.1 .
i .
I
J;
:
.,
~I ~
Z,~
::
'i
Z ~ ~
Z~
Z
~ ;
