• Graph-Theoretic Generation of Assembly Plans


  •   
  • FileName: kedar1.pdf [read-online]
    • Abstract: Graph-Theoretic Generation of Assembly PlansPart I: Correct Generation of Precedence GraphsKedar S. NaphadeBell Labs, Lucent TechnologiesPrinceton, New JerseyRobert H. Storer and S. David WuLehigh University

Download the ebook

Graph-Theoretic Generation of Assembly Plans
Part I: Correct Generation of Precedence Graphs
Kedar S. Naphade
Bell Labs, Lucent Technologies
Princeton, New Jersey
Robert H. Storer and S. David Wu
Lehigh University
Bethlehem, Pennsylvania
Abstract
Automatic generation and selection of assembly plans is a problem of great practical importance with many
significant cost implications. In this paper, we focus on the constraint satisfaction aspects of this problem which
involve the determination of a correct assembly precedence graph from an arbitrarily complex set of design constraints,
physical restrictions and pre-established design conditions. We prove that this constraint satisfaction problem (CSP)
is NP-complete and provide a graph-theoretic scheme for the generation of assembly plans. Our scheme involves
decomposing the CSP into polynomially solvable subproblems, mapping the subproblems onto a “decision graph,” then
partitioning the decision graph to obtain correct assembly plans. We then describe a procedure that systematically
generates all assembly sequences. In this paper, we focus on key theoretical properties of the proposed framework
including its correctness, completeness and inherent computational complexity. To illustrate main elements of the
framework we include a simple example in bicycle assembly. In a subsequent (Part II) paper , we discuss
computational issues related to decomposition as well as the generation of optimal assembly plans, where optimality
is defined in terms of sequencing and scheduling objectives, line balancing metrics, or other graph computable
measures.
1. Motivations
Assembly is the process of joining separate components and subassemblies together to form a single final
assembled unit (e.g. mechanism, device, building etc.). A single assembly task involves joining two or more
components or subassemblies together. In many cases, the order in which these tasks are performed is an important
consideration. Firstly, many such orders may not be feasible because of physical constraints such as accessibility and
1
stability of assembly. For example, while changing a car tire, one cannot feasibly install the lug nuts until after the tire
has been mounted on to the hub. It is also common that many feasible sequences exist, but some are more desirable
than others according to criteria such as the need for jigs or fixtures, the number of tasks that can be performed
simultaneously and so forth. We define assembly planning as the process of identifying an assembly plan, which defines
either a complete or partial order in which the assembly tasks can be performed.
Assembly Planning problems have received much attention over the past fifteen years. The problems
encompass modeling and representation of assembly constraints, (e.g. Bourjalt, 1984), generation of feasible assembly
plans (Homem de Mello and Sanderson, 1990) and selection of assembly plans for final assembly (Bonneville et. al.,
1995). Any mechanical assembly process can be decomposed into a set of tasks, where each task involves joining two
or more components or subassemblies together. The sequence generation problem involves generating one or more
feasible sequences. These are sequences in which all the tasks in this set can be performed in order to feasibly assemble
the product. The precedence graph generation problem (Chen and Henrioud, 1994), involves generating precedence
graphs such that all assembly sequences generated from these graphs are feasible.
The sequence in which assembly tasks are performed can have a significant impact on cost and efficiency
through both quantitative and qualitative measures. Quantitative measures may include resource allocation, line
balancing objectives, scheduling objectives, the number of re-orientations required and the number of tool changes
required. Qualitative measures, (or perhaps measures difficult to quantify), may include ease and stability of assembly,
fixturing requirements and complexity of operations. Different assembly sequences may require different resources,
may lead to different resource utilizations and different tooling and fixturing requirements.
The assembly planning process is typically performed by industrial or manufacturing engineers. Typically, the
decisions made are subjective and depend heavily on the expertise and experience of the person involved. Though most
experienced engineers devise good sequences intuitively, much could be gained by the systematic generation of
sequences. Systematic generation ensures that no good sequences are overlooked, facilitates automation of the assembly
planning process and provides a means to evaluate alternatives which better utilize resources in a flexible environment
(Homem de Mello and Sanderson, 1991b).
In this paper, we develop a method which instead of generating fully specified assembly sequences, generates
2
a set of correct and complete precedence graphs. The word complete refers to the generation of a set of precedence
graphs from which all possible assembly sequences can be derived. The word correct implies that all these sequences
are feasible, i.e. they satisfy all assembly constraints.
We believe that the precedence graph has greater merit as an assembly “plan” than a fully specified single sequence,
for the following reasons:
1. In many cases, it is possible to perform several assembly tasks simultaneously. In order to take advantage of
this, specification of a partial order (not a complete order) of tasks that satisfies all stated assembly constraints
is needed. This partial order is represented by a precedence graph. By specifying a full sequence we lose the
opportunity for simultaneous execution of tasks.
2. In cases requiring dynamic decision making during actual assembly operations, a precedence graph is a much
more valuable plan than just a sequence. We describe two cases where such decision making is required:
(i) Consider a flexible assembly shop or a flexible job shop where one task can be performed on several
different machines. In addition to dispatching decisions, such a shop also introduces routing
decisions into the problem. Problems like the job shop scheduling problem are extremely difficult
even in the absence of such flexibility - solving them optimally in the presence of flexibility is nearly
impossible. Hence they may be solved using heuristic routing rules and dispatching rules in real
time. We claim that in such scenarios, the precedence graph is much more valuable as an assembly
plan than a single assembly sequence. This is because at any decision point, the precedence graph
supplies a set of schedulable tasks as against just the single task that a sequence would supply. This
argument is mirrored by Homem de Mello and Sanderson (1991b) where they mention that one of
the benefits of generating all sequences is that it provides alternate sequences for better resource
utilization in a flexible environment.
(ii) Consider the common situation in which there is significant uncertainty related to either task
durations or resource availabilities. The precedence graph is again a much more valuable “plan”.
This is because a precedence graph represents in a compact fashion, a large number of possible
assembly task sequences. As a result, in the event of a disruption, it is easily possible to switch to a
3
different sequence if the shop floor controller has access to the precedence graph (Wu et al., 1999).
Consider the following scenario as an example. Task i is the task supposed to be performed next and
the machine m that task i requires, breaks down. If the shop floor controller only knows one feasible
sequence, he or she has to wait until the machine is up again. On the other hand, if he or she has
access to the precedence graph, several other tasks may be executed while machine m is being
repaired.
3. Chen and Henrioud (1994) mention that in order to design an assembly line, a precedence graph is first
required. Generation of this precedence graph is handled empirically in most factories, which may be a viable
option if the new product is to be manufactured by modifying an existing line or if the new product is simple.
However for complex new products, generation of all precedence graphs or at least a set of good precedence
graphs is extremely useful information for assembly line design.
4. In many real assembly environments, quantitative assembly line balancing methods are still not being used
because it is difficult to come up with one precedence graph - different design engineers have different
perspectives of the assembly product and come up with different precedence graphs. Here we present a
framework that can be used for generating one correct precedence graph or all precedence graphs.
In this paper, we are primarily concerned with the generation of a feasible or correct assembly plan rather than
the selection of an “optimal” one. Methods for complete generation and selection of assembly plans are discussed in
the subsequent (Part II) paper (Naphade, et. al. 1999). The remainder of the paper is organized as follows: In Section
2, we provide a brief review of the relevant assembly planning literature. In Section 3, we define and characterize the
problem of interest. Sections 4,5,6 each discuss various steps of the methodology developed. Section 7 contains an
analysis of the computational complexity. Section 8 contains an illustrative example. In Section 9, we conclude the
paper with a discussion of the shortcomings and contributions of this work and directions for future research.
2. Review of Literature
Bourjalt(1984) started research in assembly sequence generation. He obtained the constraints or establishment
conditions providing the relationships between liaisons through a question and answer method. DeFazio and
4
Whitney(1987) improved Bourjalt’s method by reducing the number of questions needed. They devised a “diamond
graph” method to generate all assembly sequences through a directed state-transition graph in which the nodes
represent partial assembly states. Later Baldwin et. al.(1991) developed an integrated computer aid to generate and
evaluate sequences using the method provided by DeFazio and Whitney (1987). Homem de Mello and Sanderson(1990)
introduced the use of AND/OR graphs to solve the sequence generation problem. This representation required fewer
nodes compared to the diamond graph of DeFazio and Whitney (1987) and simplified the search for feasible plans.
This representation essentially evaluates the possibility of a transition from a certain assembly to all possible sets of
two or more feasible child subassemblies. A similar approach is also provided by Lee et. al. (1993). On this graph, a
tree represents one assembly sequence. Homem de Mello and Sanderson (1991b) further present an algorithm for
correct and complete generation of assembly sequences using AND/OR graphs. Tsao and Wolter (1993) and Huang
and Lee (1991) use predicate calculus methods for assembly sequence generation.
In our opinion, the challenge of assembly planning arises out of the presence of disjunctive constraints (“or”
constraints) and the consequent need of predicate calculus to model the constraints. An example of an “or” constraint
is “1 or 2 Ú 3” where 1 ,2 and 3 are assembly tasks. This constraint implies that either task 1 or task 2 must be
performed before task 3 can be performed. For many simple assemblies, there may be no “or” constraints. There is a
significant volume of literature that concentrates on automated sequence generation for assemblies without “or”
constraints. The important contributions of such work (e.g. Ben-Arieh and Kramer (1994), Li and Hwang (1992a,
1992b), Lin and Chang (1993) etc.) lie in computer-aided constraint identification and computer-aided sequence
generation methods using constraint based modeling, or geometric feature based modeling of the assembly. There has
also been a lot of research on designing computer-aided assembly planning systems (expert systems or decision support
systems). For instance Ye and Urzi (1996) try to capture the heuristic strategies used by design engineers to generate
good assembly plans in their decision support system. Delchambre (1992) give an extensive review of techniques used
in such systems. A more recent review can be found in Ye and Urzi (1996). Delchambre and Wafflard (1991) develop
software that extracts precedence constraints from a liaison graph. Delchambre and Gaspart (1992) use this method
to develop prototype software for generation and selection of assembly plans. They however do not consider the case
of complex disjunctive constraints. Also selection of plans is manually done by a user through a user-friendly interface,
5
as opposed to a systematic implicit/explicit enumeration for quantitative selection of assembly plans.
We assume that the establishment conditions which are input for our method are already available. Generation
of these conditions has been dealt with in Baldwin et. al. (1991), Bourjalt (1984), DeFazio and Whitney (1987).
Homem de Mello and Sanderson(1991a) demonstrate the equivalence between different representations of assembly
constraints and also provide mappings of the different representations onto one another.
3. Problem Definition and Characterization
We first define the constraint satisfaction problem or CSP. The CSP determines a “correct” precedence graph
- a precedence graph given a specified set of assembly constraints. Note that given a correct precedence graph, it is easy
to extract from it at least one, and typically a multitude of correct sequences. Two related problems can be defined
in the context of assembly planning - Precedence-graph Optimization Problems (POPs) and Sequence Optimization
Problems (SOPs). The POPs deal with Precedence graph Optimization - obtaining assembly plans or precedence graphs
that optimize a certain performance measure in addition to satisfying all constraints. The SOPs are concerned with
identification of optimal assembly sequences for specified performance measures such as typical resource constrained
project scheduling objectives or assembly line balancing objectives. POP and SOP are the subjects of discussion in the
Part II paper and in (Naphade, 1997). We now define the CSP more formally. Suppose that the product to be
assembled contains m parts. A typical assembly task connects (or establishes a liaison between) two or more of these
m parts. Let us assume that there are n such liaisons or assembly tasks that need to be performed to fully assemble the
product. However, all possible sequences in which n tasks may be performed or all precedence graphs that can be drawn
on n nodes are not always feasible. Precedence constraints arise from issues such as accessibility, stability of the
assembly during the process etc. and may render many of the sequences infeasible.
For an assembly of n tasks numbered 1 through n, the question and answer procedures of Bourjalt (1984) and
DeFazio and Whitney (1987) yield a set of logical statements that completely represent the complex system of
precedence constraints among these n tasks. These statements are called Establishment Conditions (Homem de Mello
and Sanderson, 1991a). Given a certain task k to be performed, these conditions specify what combinations of tasks
must be performed or cannot be performed before task k. A feasible assembly sequence must satisfy all establishment
conditions specified. For instance consider the following fictitious establishment condition for a certain task 3 :
6
(1 and (2 or 4)) or (5 and 6) Ú3 (1)
From the above condition we infer that at least one of the following sets of tasks need to be completed before task 3
can be performed : {1,2},{1,4},{5,6}. Such establishment conditions may exist for each of the tasks to be
performed.(Note that for feasibility, there must be at least one task without any predecessors). Any assembly sequence
(complete order) or precedence graph (partial order) describing a feasible assembly plan must satisfy all establishment
conditions.
Thus the CSP can be defined as follows:
CSP: Given a set of establishment conditions on the n tasks of an assembly, generate a sequence for performing
these tasks or a precedence graph of these tasks that satisfies all the establishment conditions.
Establishment conditions such as 1 can be transformed through rules of predicate calculus into standard forms
to obtain the sets of tasks mentioned above. However before we comment on what standard forms are of interest and
Ú
how the transformation can be made, we must first introduce the precedence operator ( ) (read “precedes”) into our
system of predicate calculus. For this operator we define several properties :
1. Transitivity :
Ú Ú
((A B) and (B C)) implies Ú
A C.
2. Distributive Properties :
(i) Ú
A (B and C) is equivalent to (A ÚB) and (AÚC).
(ii) AÚ(B or C) is equivalent to (A ÚB) or (AÚC)
(iii) (A or B) Ú C is equivalent to (AÚC ) or (BÚC)
(iv) (A and B)ÚC is equivalent to (AÚC ) and (BÚC)
3. Negation : We shall use the tilde (~) sign for negation in this paper.
Ú
If ~ (A B) is true, then either (B ÚA) is true or there is no constraint between tasks A and B. (They may be
performed simultaneously).
Using the distributive properties defined above, any establishment condition can be transformed so that the
precedence operator has a single task on either side rather than a logical combination of tasks. For instance equation
1 above can be written as :
7
Ú Ú Ú Ú Ú
( (1 3) and ( (2 3) or (4 3) ) or ( (5 3) and (6 3) ) ) (2)
We look upon the expressions (1Ú3), (2Ú3) (4Ú3) etc. as variables (or literals) that can take truth values T (true)
and F(false). If the variable (1Ú3) takes a truth value T, then in the sequence that results task 1 must precede task 3.
For an assembly consisting of n tasks, there are n(n-1)/2 such variables. Substituting x1, x2, x3 etc. for the expressions
in (2), the establishment condition now looks like :
(x1 and (x2 or x3) ) or (x4 and x5) (3)
A variable (x1, x2, x3 etc.) or its negation (~x1 , ~x , ~x3 etc.) is called a literal. An expression like (3) formed with
2
literals and connectives (and, or) is called a formula. A formula assumes a truth value that is dependent on the truth
values of the literals that it consists of.
It is well known that every formula can be converted into its conjunctive and disjunctive normal forms
(Nilsson(1989), Steen(1972)). For this work we are interested in the conjunctive normal form (CNF) of the
establishment conditions. The CNF of a formula is a conjunction of a finite set of clauses, where each clause is a
disjunction of literals. Any logical formula can be converted into its CNF in polynomial time (Cormen et. al., 1990).
This is done by repeatedly replacing expressions of the form x1 or ( x2 and x3 ) by ( x1 or x2 ) and ( x1 or x3 ). For
instance, the CNF of formula (3) is :
(x1 or x5 ) and (x2 or x3 or x5 ) and (x1 or x4 ) and (x2 or x3 or x4 ) (4)
The reader may verify that any set of truth values for the variables that satisfies (3) will satisfy (4) and vice-versa.
Thus every establishment condition can be represented as a formula in its CNF. A feasible assembly sequence must
satisfy all the establishment conditions. As all conditions need to be satisfied, they can all be concatenated by the and
connective leading to a larger formula in its CNF. We now need to assign truth variables to the literals in this formula
such that the formula assumes a truth value T. This is identical to the Satisfiability problem which is NP-complete
(Papadimitrou and Steiglitz, 1982). We have thus shown that CSP reduces to SAT and proved the following -
Theorem: Identifying a feasible assembly sequence is NP-complete.
This is a somewhat paradoxical result especially since the difficulties in assembly planning typically arise out of an
unmanageably large number of assembly sequences: finding one or more feasible sequences is rarely difficult. This is
8
because, for many products, the establishment conditions are short, constituting a system of constraints that is a
polynomially solvable special case of the general problem (Details in the next section). Hence at first glance the above
result appears to have only theoretical value. However this result has a very important algorithmic consequence: Any
procedure or algorithm that guarantees to generate a feasible assembly sequence (or a complete and correct set of
assembly sequences) must have a worst case complexity that is not polynomial.
The method developed in this
paper solves this NP-complete CSP Establishment
Conditions
using three basic steps: Problem (3-SAT)
Decomposition, Mapping and Problem
Decomposition
Partitioning (Figure 1). In the
2-SAT 2-SAT 2-SAT
Problem Decomposition step, the
Generalization Generalization Generalization
CSP (3-SAT) problem is
Mapping
decomposed into a number of
Decision Decision Decision
linearly solvable subproblems. Graph Graph Graph
These subproblems are a
Partitioning
generalization of the 2-SAT
problem, but are still linearly
PREC PREC PREC PREC PREC
GRAPH GRAPH GRAPH GRAPH GRAPH
solvable. In order to solve the
subproblems, we map each Figure 1
The Hierarchical Framework
subproblem on to a graph, which
we call the “decision graph”. This mapping is the second step in the solution methodology. On the decision graph, the
subproblem is posed as a graph partitioning problem. The third step involves partitioning this decision graph to obtain
a set of decisions which represents a feasible precedence graph for the original CSP. In the subsequent sections, we
describe these three steps in detail.
4. Problem Decomposition
9
The 2-SAT problem is a special case of the SAT in which every clause in the CNF is of length two - two literals
connected by the “or” connective. It is well known (Papadimitrou and Steiglitz, 1982) that the 2-Satisfiability problem
is a polynomially solvable special case of the general satisfiability problem. In this section we decompose the CSP or
the satisfiability problem (P) into N simpler instances (Q i ) of a generalized 2-Satisfiability problem. In the 2-
Satisfiability problem, all clauses in the CNF are either single literals or a disjunction of two literals. Our problem is
a generalization of the 2-SAT for the following reason: In the 2-SAT problem, a literal can have only two values, 0
or 1. However the methods developed in this paper can be used to solve a problem in which a literal can take an
arbitrary number of values. This will become clearer in subsequent sections.
It is important to note that this decomposition is necessary only if the original CSP contains one or more establishment
conditions that have disjunctions of 3 or more literals in their CNF. If this is not the case, the CSP is already a 2-SAT
and hence does not need to be decomposed. In such a case, the CSP is linearly solvable as we will prove in the next
section.
The decomposition satisfies the following properties:
(a) A solution that is feasible for P is feasible for at least one Qi. i
{1,...,N}
(b) A solution that is feasible for any Qi is feasible for P. i = 1,....,N
In other words the set of all solutions for all the 2-Sat problems Qi is identical to the set of solutions of the
original satisfiability problem P. Hence a correct and complete generation of solutions for each of the subproblems will
constitute a correct and complete generation of solutions for the original problem. Consider the following instance of
problem P :
(x1 or x5 ) and (x2 or x8 or x5 ) and (x3 or x6 ) and (x2 or x4 or x6 or x9) (5)
Clause I Clause II Clause III Clause IV
There are two clauses in P (II and IV) with more than two literals. In order to decompose the problem, each
clause containing three or more literals is broken up into several sub-clauses each of which contains at most two
literals. This is done such that a literal in the original clause is present in one and only one of the new subclauses. For
instance the clause (x2 or x8 or x5) is broken up into two sub-clauses : (x2 or x8 ) and (x5). Now suppose the problem
10
P is replaced by two problems P´ and P´´. The problem P´ contains clauses I, III and IV of P and the sub-clause (x2
or x8 ). The problem P´´ contains clauses I, III and IV of P and the sub-clause (x5).
P´ : (x1 or x5 ) and (x2 or x8 ) and (x3 or x6 ) and (x2 or x4 or x6 or x9) (6)
P´´ : (x1 or x5 ) and (x5) and (x3 or x6 ) and (x2 or x4 or x6 or x9) (7)
It is clear that any solution that is feasible for either P´ or P´´ is feasible for P. It is also fairly simple to see that
all feasible solutions of P can be obtained by solving both P´ and P´´. This is because any solution of P that has a truth
value T for literal x2 or literal x8 will be generated as a feasible solution of problem P´ and any solution of P that has
a truth value T for literal x5 will be generated as a feasible solution of problem P´´. Thus the problems P´ and P´´
satisfy properties (a) and (b) above. Clause IV of problem P can be similarly decomposed into two sub-clauses. To now
obtain a set of 2-Sat problems that satisfy properties a and b, we take all possible combinations of the sub-clauses as
follows :
Q1 : (x1 or x5) and (x2 or x8 ) and (x3 or x6 ) and (x2 or x4 ) (8)
Q2 : (x1 or x5 ) and (x5) and (x3 or x6 ) and (x2 or x4 ) (9)
Q3 : (x1 or x5 ) and (x2 or x8 ) and (x3 or x6 ) and (x6 or x9 ) (10)
Q4 : (x1 or x5 ) and (x5) and (x3 or x6 ) and (x6 or x9 ) (11)
The above four problems satisfy properties (a) and (b) with respect to problem P. In summary, any clause j of P
that contains kj (kj>2) literals is decomposed into Mkj/2N sub clauses, such that all literals xi from the original clause
are part of one and only one subclause. If kj is even, each subclause is a disjunction of two literals. If kj is odd, all but
one subclause are a disjunction of two literals and one subclause contains one literal. All clauses of P that contain more
than two literals are decomposed as mentioned above. A problem Qi is formed by taking a combination of subclauses
one subclause derived from each of the parent clauses. The total number of such combinations and hence the total
number of problems Qi equals  = - (Mk /2N). As properties (a) and (b) are satisfied by this decomposition scheme,
j j
solving all Qi leads to correct and complete generation of all the assembly sequences.
Several insights are noted here:
1. The concept of constraint elimination may be used to simplify a problem. Assume that each establishment
11
condition is a disjunction of several literals. If there are two establishment conditions with the same task on the
right hand side and if the literals on the left hand side of condition 1 are a subset of the literals on the left hand
side of condition 2, then condition 2 can be eliminated, as condition 1 automatically satisfies condition 2.
e.g. condition 1 : (3 or 4) Ú6
condition 2 : (3 or 4 or 5) Ú6
condition 1 : 1 Ú8
condition 2 : (1 or 3) Ú8
Condition 2 can be eliminated in both above cases. This is a useful property since the longer establishment
condition can be eliminated whenever possible. If the condition eliminated has a length of 3 or more literals, there
is a significant reduction in the number of subproblems obtained after decomposition.
2. The decomposition scheme may lead to a non-polynomial number of subproblems. To solve a subproblem, we
provide a method which has a worst case complexity that is linear. In other words, for every subproblem, we
obtain a feasible solution (or establish the fact that none exists) in linear time. However, in the worst case, all
subproblems may need to be investigated before one feasible solution is found. Thus for the overall problem,
finding a feasible solution may take non-polynomial time - which is consistent with the NP-completeness result.
3. The decomposition method involves partitioning a constraint of length > 2 into constraints of length  2.
However there is no restriction on which literals need to be in the same subproblem or which literals need to be
in different subproblems. A given constraint may be split in several different manners, and so for a given
problem, we may have several alternative decompositions (possibly an exponential number), each of which is
correct and complete. In this paper we arbitrarily select any correct and complete decomposition. Choice of
decomposition has little effect on determination of a correct solution, however it has a significant effect on
generation of all solutions or identification of optimal solutions (POP, SOP etc.). These issues are discussed in
further discussed in the Part II paper.
We have decomposed the CSP into a number of subproblems. In subsequent sections, we describe the mapping
and partitioning steps that provide a solution to these subproblems.
12
5. Mapping the Subproblem onto a “Decision Graph”
Any disjunction of two literals can be represented as a set of if ... then statements. For instance the clause (x1 or
x5 ) can also be written as : if (~x1 ) then (x5 ); if (~x5 ) then (x1 ). For the assembly planning problem, each of the literals
is a precedence relation. We introduce the expression (ab) to indicate the absence of any precedence constraints
between tasks a and b. In other words, if ab, tasks a and b may be performed in any order or performed
Ú Ú
simultaneously. Suppose x1 represents 1 3 and x5 represents 5 3 then the clause (x1 or x5) can also be expressed as
the following set of if .. then constraints:
Ú Ú
if (3 1) then (5 3) ; Ú Ú
if (3 5) then (1 3)
if (13) then (5Ú3) ; if (35) then (1Ú3)
Thus the subproblems Qi can now be represented as a combination of two types of constraints. The first type is
Ú
straight precedence constraints of the form “A B” ; and the second type which we shall call the decision dependent
constraints are of the form :
“if (A 8 B) then (CÚD)”
where A, B, C etc. are tasks and 8 is either a precedence relationship(Ú) or a temporal equivalence relationship().
Before a solution to the problem is obtained, the relative sequence of tasks a,b,c,d is not fixed: they are decisions that
need to be taken. However the decision associated with the sequence of a and b influences the decision associated with
sequencing tasks c and d. Hence the term decision dependent constraint.
The subproblem that results from the decomposition can be represented on a disjunctive graph G as in Figure 2.
The nodes on the graph represent tasks. There are three types of arcs on the graph : Conjunctive Arcs, Disjunctive arcs
and Hyperarcs. The conjunctive arcs represent fixed precedence relations between tasks : precedence constraints that
have to be met and are not subject to the decision making process. For instance in any assembly sequence that results
from the graph in Figure 2, Task 2 shall always precede task 5.
The disjunctive arcs have a slightly different interpretation than that of the disjunctive graph representation of machine
scheduling problems. In machine scheduling problems, disjunctive arcs represent a resource conflict - the constraint
that the two tasks connected by a disjunctive arc cannot be performed at the same time. Hence resolving a disjunctive
arc will result in a conjunctive arc in one of the two possible directions. In this case, the resolution of a disjunctive arc
13
between tasks a and b may lead to
Conjunctive Arc
three results: a conjunctive arc from A
Disjunctive Arc
Ú
to B (A B), a conjunctive arc from B
The "no-arc" decision
to A (BÚA) or no arc between A and Hyperarc
B (AB). This is because the
2 5 8
constraint here is not a resource
3 6 10
1
constraint. It may arise out of physical
factors such as stability, reachability
4 7 9
and so on. Hence it may indeed be
6 or 7 3
possible to perform both tasks a and b
simultaneously. Thus the “no-arc”
Figure 2
resolution of a disjunctive arc is very Disjunctive Graph Representation
much an alternative that needs to be actively considered.
The “” relationship plays an important role in generating precedence graphs. Explicit inclusion of this
relationship allows us to omit an arc from the precedence graph if feasible. In general a precedence graph that is sparse
or has a small number of precedence arcs makes it easier to use resources efficiently and lends more flexibility to the
scheduling problems that may need to be solved once the precedence graph is designed. Also in this case, the
disjunctive arcs may not be independent of each other. Resolution of one arc may affect the resolution of another
through if...then constraints. This dependence is indicated by the hyperarc between the two disjunctive arcs.
In order to identify a feasible solution (i.e. a completely conjunctive precedence graph), the disjunctive arcs must
be resolved such that all the decision dependent constraints are satisfied. We represent these decision dependent or
“if - then” constraints on a decision graph which is later partitioned in order to obtain a feasible set of alternatives. The
problem is mapped on to a decision graph G* from a disjunctive graph G in the following manner:
For every disjunctive arc (AB) in G there are three nodes in G*. Each of these nodes represents a different resolution
Ú Ú
of the disjunctive arc ( AB, A B, B A). Thus these nodes represent three mutually exclusive alternatives. If there
are d disjunctive arcs in G, there are 3d nodes in G*.
14
Ú
The arcs in G* represent the decision dependent precedence constraints as follows : If an alternative A B forces
Ú Ú
an alternative C D, then there is an arc in G* from the node representing A B to the node representing C D. Ú
Consider as an example the following set of constraints for the disjunctive graph in Figure 2:
Ú Ú
if (1 2) then (5 8)


Use: 0.4647