Boiler Erection Scheduling Using Product Models and Case-Based Reasoning by Ren-Jye Dzeng and Iris D. Tommelein, Z Associate Member, ASCE
Boiler Erection Scheduling Using Product Models and Case-Based Reasoning by Ren-Jye Dzeng and Iris D. Tommelein, Z Associate Member, ASCE
Boiler Erection Scheduling Using Product Models and Case-Based Reasoning by Ren-Jye Dzeng and Iris D. Tommelein, Z Associate Member, ASCE
CASE-BASED REASONING
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
INTRODUCTION
Architects/engineers (AlEs) who repeatedly design facilities
of the same kind may reuse designs as a whole or in part. This
is the case, for instance, in cookie-cutter design of industrial
facilities such as power plants. When parts of a design are
copied from one project to the next, contractors who have
experience in constructing those facilities find that (parts of)
schedules can also be reused to schedule new construction
work. This saves time, which is of the essence during bid
preparation, but, more importantly perhaps, it enables them to
reuse some of their company's proven field expertise that is
reflected in those schedules.
A scheduler intent on reusing an existing schedule will try
to recall major parts from a past project's design and schedule
(including components and details, construction resource
availability, contractual agreements, environmental factors,
etc.) that recur in or in some way resemble the new project at
hand, in order to determine which (parts of) schedules could
be reused. The scheduler may then choose a single existing
schedule for adaption to the new design, contract, and construction needs, or choose parts from several existing schedules, link them, and adapt them to better suit those needs.
This problem-solving method-namely, reasoning about
past cases then retrieving and adapting them to solve a new
problem-is termed case-based reasoning (CBR). It is a
method used by schedulers who can remember salient features
about past projects and who have enough such projects to draw
upon. CBR works well when cases are organized so that the
search for and adaption of relevant cases can proceed in a
systematic way. Unfortunately, most valuable project knowledge gets buried in vast amounts of documentation of a paperbased archival system. Moreover, novice schedulers rarely
have access to relevant, historic case data because it is in the
head of their seniors and not accessible in any other way than
through verbal communication. A lot of knowledge is lost
when senior schedulers are tied up with other work, get promoted, leave the organization to take on other duties, or retire.
'Assoc. Prof., Civ. Engrg. Dept., National Chiao Tung Univ., Hsinchu,
30050 Taiwan.
2 Acting Assoc. Prof., Civ. and Envir. Engrg. Dept., 215-A McLaughlin
Hall, Univ. of California, Berkeley, Berkeley, CA 94720-1712.
Note. Discussion open until February I, 1998. To extend the closing
date one month, a written request must be filed with the ASCE Manager
of Journals. The manuscript for this paper was submitted for review and
possible publication on September 9, 1996. This paper is part of the
JourlUll of Construction Engineering and MalUlgement, Vol. 123, No.
3, September, 1997. ASCE, ISSN 0733-9364/97/0003-0338-0347/
$4.00 + $.50 per page. Paper No. 14048.
The aim of the research described in this paper was to address (I) how cases could be described in a systematic way to
facilitate classification and reuse; and (2) how a computerbased system could automate the generation of construction
schedules by reusing cases that reflect design and construction
experience.
RELATED WORK
Automated Planning Systems
Construction planning consists of defining activities with
their durations, precedence relationships, and resources,
whereas scheduling involves applying the critical-path method
(CPM) to calculate early and late activity start and finish times,
and floats. Computer tools that perform CPM calculations are
widely used but few exist that address the planning task. Plan
generation has been automated using artificial intelligence (AI)
programming techniques. Examples of such AI-based planning
systems (AI-planners, in short) are BUILDER (Cherneff et al.
1991), PLANEX (Zozaya-Gorostiza et al. 1989), GHOST (Navinchandra et al. 1988), Know-Plan (Morad and Beliveau
1991), OARPLAN (Darwiche et al. 1989), and SIPEC (Kartam and Levitt 1990). These are constructive planning systems: they always generate a plan from scratch for each new
project. Their knowledge typically comprises (1) a (usually
functional) hierarchy of components for a particular type of
project (e.g., high-rise steel construction) in which each type
of component has a construction activity associated with it
(though in principle possible, few models present alternatives);
and (2) planning rules or constraints acquired from expert
practitioners, based on rules-of-thumb, or stated in the literature. These systems use this knowledge to pick a network of
activities for each product's component based on its association in the hierarchy, and to test the preconditions of each
activity and determine its precedence relationship relative to
other activities in the plan.
Many of these AI-planners were developed to provide designers with constructibility feedback before award of the construction contract (Gray 1986). Their knowledge includes general construction principles but rarely project characteristics
and resources such as contractor equipment, material availability, or site constraints (PLANEX is an exception). In the
process of generating solution plans, these AI-planners keep
track of all possible alternatives while pruning out only those
that do not meet the constraints. Because relatively few constraints are known at design time, they typically can output
many plans that satisfy all constraints. By leaving the user
(contractor) with the largest possible set of satisfying plans,
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
Case-Based Reasoning
The knowledge base for a CBR system comprises a set of
cases plus mechanisms for retrieving cases and adapting their
solutions to suit the new problem at hand, rather than a set of
rules and facts that make up a traditional rule-based system.
CBR has played an important role in the development of AI
and expert systems (Kolodner 1993) addressing tasks such as
planning, design, explanation, diagnosis, classification, and
natural-language parsing. To our knowledge, however, there
exist no CBR systems for generating construction schedules.
A CBR system adopts three steps in solving a problem
(Dzeng 1995):
1. Identifying and retrieving useful case(s). This requires
access to cases and knowledge to assess the appropriateness for retrieval of one case over another. It is typically
assumed that the most useful case is the one most similar
to the new problem, though the notion of similarity varies; e.g., it can be based on the match between goals or,
instead, between design attributes in the new problem
versus those in an archival case. Nevertheless, matching
and ranking requires three steps: (I) determining the correspondence of matching attributes, (2) assigning an importance weight to attributes used in assessing similarity,
and (3) determining the degree of similarity between corresponding attribute values based on some similarity
measurement (e.g., semantic hierarchies, quantitative or
qualitative ranges of values, and functional roles the values play in problem solving).
2. Reusing and adapting the retrieved case(s). Solutions
from retrieved cases seldom perfectly match but need to
be adapted to solve the new problem. One may (1) reinstantiate a partial solution from an old solution, (2) adjust
some parameters, (3) transform the solution's structure
(e.g., delete old or add new parts) before applying it to
the new problem, or (4) replay the reasoning steps used
in the old case but using data and constraints in the new
problem.
3. Categorizing and storing the new problem and solution
as a case. When a new problem's solution has been validated, a new case can be created and stored for reuse.
Organizing stored cases is not mandatory, but using some
indexing scheme (e.g., articulating goals, salient attributes of the problem, or factors that caused failure during
problem solVing) may improve the efficiency and success
rate of subsequent searches.
Most CBR systems use similar concepts and approaches,
but vary in their combination thereof to suit their domain of
application. Like other systems, CasePlan uses CBR as a
means to reuse knowledge specific to individual projects
(which is lacking from existing construction planning systems)
but it is unique in that it tackles planning problems in construction and uses product models as the basis for case organization.
Product Modeling
A case-based scheduling system should not be a stand-alone
tool, but tie into existing modeling practices in design and
construction. Establishing a representation to integrate and
exchange data spanning the lifetime of a facility that is of use
to all participants involved with a common architectural/engineering!construction (AEC) project is a widely recognized
problem, exacerbated by the use of heterogeneous computer
systems. It has driven the development of an international
standardization effort that involves people in AEC practice as
well as academia, e.g., the Special Issue on Data and Product
Modeling in the Journal of Computing in Engineering (Special
1996).
Several standardization efforts were investigated for this research, namely:
1. Plant information network (PIN). The Electrical Power
Research Institute developed a comprehensive power
plant model as a guide to specifying integrated computeraided applications ("Guidelines" 1987). Twelve volumes describing this model were reviewed (unfortunately, no electronic copy could be obtained) but the PIN
model was not adopted because it appears to have been
superseded by PlantSTEP described in the following.
2. Standard for the exchange of product model data (STEP)
and general AEC reference model (GARM). The most
significant product-model standardization effort to date
has resulted in the International Standards Organization
(ISO) draft standard 10303, named STEP (ISO I994a).
STEP is an abstract model to be refined with domainspecific details in order to reflect each industry's ontology. For instance, PlantSTEP's application protocol AP277 serves the power plant industry (ISO 1994b) and is
currently under development. PlantSTEP is most relevant
to the present research, but, unfortunately, insufficient
detail had been formalized at the onset of this research
for it to be useful. However, our modeling methodology
is compatible with PlantSTEP's.
GARM, developed specifically for AEC applications,
was the next best available STEP standard, though it also
is an abstract reference model under which product-specific models must be developed. GARM entities describe
a product in terms of product definition units (PDUs),
which can be the entire product, its components and subcomponents, or relationships between PDUs.
3. Work breakdown structures (WBSs). To elicit the terminology of boiler components used in industry practice,
WBSs were obtained from boiler manufacturers Asea
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
TBC Joint-venture
Townsend & Bottum Inc.
The Christman Co.
BVTBC Trl-venture
Black & Veatch Power Development Corp.
Townsend & Bottum Inc.
The Christman Co.
(Architect/Engineer and
General Contractor)
.......
Notation
Boiler
Erection
Schedule
FIG. 1.
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
Knowledge for creating a field-executable schedule is expressed by means of constraints, which fall into six categories
(Dzeng and Tommelein 1994, after Gray 1986 and Echeverry
et al. 1991):
1. Facility components and their relationships. Components
determine which construction alternatives are feasible,
e.g., the degree of prefabrication of an economizer affects the duration of construction and the installation
equipment required. Physical and structural relationships
between design elements (support, embedment, coverage, enclosure, etc.) often govern construction sequencing, e.g., drums of a top-supported boiler cannot be in-
2.
3.
4.
5.
6.
Many AI-planners use "Facility components and their relationships" as the primary constraints and they encode some
"Regulations and specifications" into their heuristic rules for
sequencing activities. Most plan with different "Scheduling
detail and format" in that they generate hierarchical plans, but
the level of detail is predetermined and not for the user to
change. Only PLANEX considers "Resources" and "Site environment" constraints. None consider "Procurement" constraints. In contrast, CasePlan allows practitioners to account
for all these constraints so schedules can be better custom tailored.
CASEPLAN ARCHITECTURE AND COMPONENTS
Project Modeling Knowledge
The CasePlan architecture builds on the premise that a generic product model, comprising a hierarchy of classes that
represent abstract and physical components with has-a-com-
S
':I ----
ame: string
10: string
escrlptlon: text
PDU
B
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
Product
can-be-a ,. ...
,.
,.
I ,.
ProjectSpecs.
I
I
I
I
Schedule
--
--
~,.
Site
II-~
Ar\',
,,
I
\
I
,,
\
I
\
,
Ij1~s-:Cmpo~ent
~.
,. ,. .,./
1//
I
I-",.
string
Conatructlon- =!~e:
as-components:
'(component ...)
PDU
s-component-of: component
-component-network: component-network
Boller
Drums
l-
II
\ I
I--
Economizer II--
Stoker
'-
' ...
' .... 1
WW
I-I-I--
Instantiation
Product-1
Boller
1
Project- lSpecs 1. I-
....
Site
1
l-
I has-a-component
I
I
I
I-
I-I-I--
I-
I-
....
I-
Drums
1
-.
--
FIG. 2.
Economizer
1
IlI-
....
I
Stoker
1
I-
I-
....
I-
I
WW
1-1
~I
I
WW
1-2
--
Class Inheritance
Component Network
CasePlan constructs a schedule by determining a network
of activities (termed a "component network") describing the
construction process for each component in the product model
and then combining them into a single large network. A sequential link in a component network is of type start-to-start
(SS), start-to-finish (SF), finish-to-start (FS), or finish-to-finish
(FF). Dnless marked otherwise, a single line represents the
default FS link. Links that have no arrow imply that they go
from left to right.
Fig. 3(a) shows the component network for a typical erection sequence for 'Drums'. First, the steam drum (upper drum)
is raised to a height approximately equal to the length of the
generating bank while the mud drum (lower drum) is raised
just above the ground. With the drums temporarily secured,
pipefitters assemble the generating bank, which connects the
drums, near the ground. When the bank assembly (including
both drums and therefore referred to as the component 'Orums',
in the plural) is completed, it is further raised. After the drums
have been erected, pipefitters finish their piping hookups. Fig.
(a)
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
Raise
steam drum
(Drums)
10-
Ground assemble
Erect
Raise
mud drum f-- generating bank ,..- drums
(Drums)
(Drums)
(Drums)
1\
Trim
external piping
(Drums)
Trim
internal piping
(Drums)
Trim
external piping
(Drums)
(b)
Erect
Erect
mud drum f-- steam drum
(Drums)
(Drums)
FIG. 3.
lo-.
Assemble
Trim
generating bank f-- intemal piping
(Drums)
(Drums)
ified by the user directly or derived by CasePlan by combining the activity's attributes name-verb and name-noun
(e.g., "Trim external piping for Drums"). Derived
names are more amenable to reuse than user-specified
ones.
2. Sequencing, namely: predecessors, which lists the activities that immediately precede the activity, and successors, those that immediately succeed it.
3. Timing, namely scheduled times: the early and late start
and finish time, and four floats [Harris (1978) gives definitions and formulas]; and actual times: AS: actual start;
AF: actual finish; RD: remaining duration = duration (current date - AS); AD: actual duration = AF - AS.
Scheduled times are calculated using CPM based on the
sequencing and timing constraint attributes (described
next); they cannot be changed directly by the user. As a
minimum, the project start time, all activity durations,
and sequencing attributes need to be known for CasePlan
to calculate a schedule. The actual times become available only after the activity has started and possibly finished.
4. Timing constraints, namely: SNE (start no earlier than),
FNE (finish no earlier than), SNL (start no later than),
FNL (finish no later than), and others (Dzeng 1995).
They specify constraints that a contractor may impose on
an activity for a reason unrelated to network logic per
se, e.g., to reflect material delivery schedules or contract
milestones.
5. Resource allocation, namely to refer to materials (e.g.,
piping), laborers or crews (e.g., four pipefitters and a
foreman), or equipment (e.g., 30-ton PCSA class 12-105
crane) that are required to perform the activity. CasePlan
groups those resources into a 'Construction Method',
which is a class with attributes: crew, a list of individual
trades or crews and their number specified in the form:
[(crew-name crew-size) ...]; equipment, a list of equipment and its quantity specified in the form: [(equipmentname number-of-pieces-of-equipment) ...]; and productivity, the amount of work the specified crew and
equipment accomplish per day. Upon reuse of an activity,
the associated construction method is also reused, specifically, to estimate the activity duration based on the
productivity and possibly based on attributes of the associated component.
6. For-component and Use-condition (described later).
Preceding-activity.
Succeeding-activity.
Type: SS, SF, FS, or FE
Lead-time, the amount of time between the link's head
and tail.
5. Strictness, quantified as a number between a and 1, with
a default value of 0.5. A "strictness threshold" (set at
0.8 but changeable by the user) determines whether a
link is strict (strictness 2: threshold) or not (strictness <
threshold). CasePlan uses strictness to gauge whether it
should reuse a link automatically (strict) or only after
user confirmation (not strict). A link that is strict reflects
a sequencing principle that applies to all projects, e.g.,
the sequential link between activities "Install columns
on floor 1" and' 'Install beams on floor 1" is quite strict
because one supports the other and is thus built first.
Conversely, a link that is not strict reflects that it was
introduced for a project-specific reason, e.g., a sequential
link between "Install east wall" and "Install north
wall" is not necessarily reusable because this ordering
may be the result of the availability of a specific crane.
6. Use-condition (described later).
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
1.
2.
3.
4.
AUTOMATED SCHEDULING
Fig. 4 illustrates the steps CasePlan takes to automate the
planning and scheduling tasks: a double-edge rectangle represents a step for which CasePlan reuses cases; a single-edge
rectangle one for which it does not; a rounded rectangle represents information available before or after a step, and in it,
underlined text represents information generated or changed
by the preceding step.
Project
Cases
New case
Cases
t
Calculate
CPM
schedule
Determine
component
networks
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
t
Project
Cases
Component networks
Interlinks
Construction methods
Activity durations
Project
Cases
Component networks
(Construction methods)
(Activity duration specs,)
\.
II'
Calculate derived
attribute values of
activities and links
Determine
product
network
Project
Cases
Component networks
Interlinks
(Construction methods)
(Activity duration specs,)
FIG. 4.
TABLE 1
total-mass (0.2)
max-unit-mass (0.2)
number-of-generating-tubes (0.4)
is-drum-1ength-greater-than-baywidth? (1.0)
Project-1
AV'
(2)
Case-A
AV
(3)
false
1.0
AV
(5)
Determine
construction
methods
CasePlan Subtasks
Case-B
ASV'
(4)
OR
Attribute
(1)
Project
Cases
Component networks
Interlinks
Construction methods
(Activity duration specs,)
ASV
(6)
148,000 kg 0.6
45,000 kg 0.6
20,000
0.8
true
0.0
'Attribute values.
Attribute similarity values.
This specifies that the ASY is 1,0, 0.8, 0.6, 0.2, and 0,
respectively, if the difference of max-unit-mass of the project
and case being compared is between 0 (inclusive) and 4,000
kg, between 4,000 and 9,000 kg, between 9,000 and 20,000
kg, between 20,000 and 30,000 kg, and greater than 30,000
kg, respectively. Because the difference between the project
and Case-A is (34,000 kg - 30,000 kg) = 4,000 kg, Case-A's
ASY is 0.8; similarly, Case-B's ASY calculation yields 0.6.
Other ASYs are determined using different schemes but these
are not discussed here due to space limitations. The CSY of
'Drums' in each case is then calculated in the following two
equations:
1.0 = 0.31
(2)
= 0.6 x
1.0 X 1.0
1.0
= 0,93
(I)
= 0,943
0,6 X 1.0
(3)
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
CasePlan can function as a stand-alone or as a decisionsupport tool. Because CasePlan relates a product (and its components) to its schedule (and its component networks), a user
can browse and manually copy parts of existing schedules on
a component-by-component basis after choosing cases that are
similar to the project at hand. The user may modify component
networks or construction methods from selected cases or create
new ones from scratch. This allows for much more intelligent
assembly than is possible using "fragnets."
IMPLEMENTATION
CasePlan has been implemented in object-oriented lisp, Allegro CL/PC 2.0 (Allegro 1994), that runs in the Microsoft
Windows@ 3.1 environment. The model includes several
graphical display windows, examples of which are shown by
Dzeng (1995). The system includes a generic product model
for boilers of fossil-fueled power plants with a capacity ranging from 30 to 90 MW. The product model is the result of a
survey sent out to industry practitioners knowledgeable about
boiler erection and subsequently discussed with them face-toface or over the telephone. CasePlan's library currently includes seven realistic cases, including Grayling and Genesee,
with design details and preproject schedules obtained from two
boiler manufacturers.
CASEPLAN CAPABILITIES AND LIMITATIONS, AND
FUTURE RESEARCH
Downloaded from ascelibrary.org by National Chiao Tung University on 05/01/14. Copyright ASCE. For personal use only; all rights reserved.
ACKNOWLEDGMENTS
We would like to acknowledge the kindest support from and participation in this research by industry practitioners at Asea Brown Boveri
Combustion Engineering Services, Inc., Black & Veatch, Inc., The
Christman Co., Genesee Power Station, Grayling Generating Station,
Northern Boiler Mechanical Contractors, Inc., Townsend & Bottum, Inc.,
and Zurn Industries, Inc.
This research was funded by grant MSS-9215935 from the National
Science Foundation (NSF), whose support we gratefully acknowledge.
Any opinions, findings, conclusions, or recommendations expressed in
this paper are those of the authors and do not necessarily reflect the views
of NSF.
APPENDIX.
REFERENCES
construction using product modeling," PhD Dissertation, Civ. and Envir. Engrg. Dept., Univ. of Michigan, Ann Arbor, Mich.
Dzeng, R. J., and Tommelein, I. D. (1993). "Using product models to
plan construction." Proc., 5th Int. Con! Compo in Civ. and Build.
Engrg., ASCE, New York, N.Y., 1778-1785.
Dzeng, R. J., and Tommelein, 1. D. (1994). "Case storage of planning
knowledge for power plant construction." Proc., 1st Congr. Compo in
Civ. Engrg., ASCE, New York, N.Y., 293-300.
Echeverry, D., Ibbs, w., and Simon, K. (1991). "Sequencing knowledge
for construction scheduling." J. Constr. Engrg. and Mgmt., ASCE,
117(1), 118-130.
Gray, C. (1986). "Intelligent construction and cost analysis." Constr.
mgmt. and economics, London, U.K., 4, 135-150.
"Guidelines for specifying integrated computer-aided engineering applications for electric power plants." (1987). EPRI NP-5159M, Electric
Power Res. Inst., Palo Alto, Calif.
Harris, R. B. (1978). Precedence and arrow networking techniques in
construction. John Wiley & Sons, New York, N.Y.
ISO Standard 10303-1. (1994a). "Product data representation and
exchange. Part I: overview and fundamental principles." Int. Standards
Org.
ISO Standard 10303 AP. (1994b). "Project proposal for plant spatial configuration AP." Int. Standards Org.
Kartam, N. A., and Levitt, R. E. (1990). "Intelligent planning of construction projects." J. Compo in Civ. Engrg., ASCE, 4(2), 155-176.
Kolodner, J. (1993). Case-based reasoning. Morgan Kaufmann, San Mateo, Calif.
Miresco, E. (1992). "Expert system for scheduling building projects."
Proc., CIB 92 Vol. 1, Nat. Res. Council Canada, 258-259.
Morad, A. A., and Beliveau, Y. J. (1991). "Knowledge-based planning
system." J. Constr. Engrg. and Mgmt., ASCE, 117(1), 1-12.
Navinchandra, D., Sriram, D., and Logcher, R. (1988). "GHOST: project
network generator." J. Compo in Civ. Engrg., ASCE, 2(3), 239-254.
Primavera project planner for Windows 1.0. (1993). Primavera Systems
Inc., Ba1a Cynwyd, Pa.
Special issue on data and product modeling. (1996). J. Camp. in Civ.
Engrg., ASCE, 10(3).
Thabet, W. Y., and Beliveau, Y. J. (1993). "A model to quantify work
space availability for space constrained scheduling within a CAD environment." Proc., 5th Int. Can! Camp. Civ. and Build. Engrg., ASCE,
New York, N.Y., 110-116.
Tommelein, 1. D., Levitt, R. E., Hayes-Roth, B., and Confrey, T. (1991).
"SightPlan experiments: alternate strategies for site layout design." J.
Camp. in Civ. Engrg., ASCE, 5(1), 42-63.
Zozaya-Gorostiza, C., Hendrickson, C., and Rehak, D. R. (1989). Knowledge-based process planning for construction and manufacturing. Academic Press, Boston, Mass.