SAND 2000-1436

Unlimited Release

Printed June 2000

An Evaluation of Optimization Formulations for\
Production Planning at Pantex

William E. Hart and Cindy Phillips

Optimization/Uncertainty Estimation Department

Craig Lawton

Critical Infrastructure Surety Department

Sandia National Laboratories

P.O. Box 5800

Albuquerque, NM 87185-1110

> Abstract

We reconsider the production planning problem that is solved by the
Evaluation Planning Module (EPM), which is used to project how
facilities and technicians will be used at Pantex. We describe a general
formulations of this production planning problem that can be solved with
general-purpose optimizers. Further, we describe a mixed-integer
formulation of the problem that can be solved with branch-and-bound
methods. We evaluate the solutions currently provided by the EPM, and we
illustrate the utility of these problem formulations by applying
general-purpose optimizers to generate globally optimal solutions.
Finally, we evaluate the problem formulation used by the EPM.

# Introduction

Sandia National Laboratories has developed and implemented the Pantex
Process Model, (Kjeldgaard, et al, 1998) a computerized model to support
the planning and scheduling activities at Pantex, a US Department of
Energy production plant in Amarillo, Texas. The plant simultaneously
supports three major DOE programs---nuclear weapon disposal, stockpile
evaluation, and stockpile maintenance--- which share its facilities,
technicians, and equipment. The model incorporates modern management
science techniques to optimize production planning and scheduling in the
complicated production system at Pantex.

The Evaluation Planning Module (EPM) is one of the core tools in the
Pantex Process Model. This module provides production planning tools
that are used to project how facilities and technicians will be utilized
over a given planning horizon (typically a year). Kjeldgaard et al.
\[2,3,4\] describe formulations of this planning problem.

In this report we describe recent progress with new formulations of the
EPM production planning problem that have been developed in the
Mathematics, Computational and Computer Sciences Center at Sandia
National Laboratories (9200). We present a generic formulation of the
EPM production planning problem and argue that the formulations
previously developed are derivatives or approximations to this basic
formulation. We reformulate the problem to develop formulations that can
be solved by general purpose solvers: direct search methods and
mixed-integer linear branch-and-bound. Direct search methods do not rely
on the gradient of the objective function and they do not estimate the
gradient. Branch-and-bound methods recursively partition the search
domain to find provably optimal global solutions. Both of these classes
of general-purpose optimization methods are quite diverse, so a wide
range of optimizers can be applied to these new formulations.

To illustrate the utility of these formulations, we provide some
preliminary experiments of the application of general-purpose solvers to
the production planning problem. We applied a simple evolutionary
algorithm (EA) to perform global optimization for the EPM. This methods
was able to solutions within 1% of the global optimum in 46% of the
random trials. We also applied a simple pattern search method to refine
the final solution provided current EPM (the $v$-variable formulation
\[[23](#_Ref468597866)\]). This study shows that the final solution
generated by the EPM is not particularly close to a local optimum.
Further, the refined solution is a global optimum, so the solution of
the$v$-variable formulation is in the general neighborhood of a global
optimum.

Additionally, we have updated the mixed-integer program (MIP) to better
reflect the PPM model. We have resolved lingering data modeling issues
so the MIP can use data from the PPM database. We have begun working on
the translation of the continuous-time solutions generated by the
v-variable formulation and evolutionary algorithms to a discrete-time
formulation, which is necessary to perform formulation comparison
studies.

These results clearly illustrate the utility of general-purpose
optimization techniques for these production planning problems. They
also point to the need to more carefully examine the algorithmic
difficulty and problem formulation for this class of problems. We
evaluate several different aspects of the EPM problem formulation,
noting weaknesses in the formulation and describing one way that the
formulation could be tightened to provide a more accurate model of
resource availability.

# Problem Description

A substantial portion of the Pantex workload relates to tests of weapons
in the active stockpile. Each of these jobs involves partial disassembly
of the weapon, one or more tests, and then re-assembly and return of the
weapon to the active stockpile. The jobs are generally referred to as
***evaluations***, and their planning and scheduling fits a job-shop
paradigm. Each job consists of a ***set of tasks***. Some pairs of tasks
have precedence constraints, where one job must complete before the
other begins. The tasks vary widely in duration. Timing restrictions
must be met: e.g., the earliest times when tasks can start, and the
latest times when they can finish. The EPM planning problem is
formulated using time periods, which are typically comprised of six
consecutive eight-hour days. Because of uncertainties in the duration of
tasks used in the planning problem, solutions to this problem are
typically provided with an hourly time resolution.

![](media/image1.wmf)

Figure 1. Illustration of an evaluation job, including a parent and
daughter job. Arrows between tasks indicate precedence constraints.

Figure 1 shows a typical evaluation job. Tasks *P-1* through *P-6*
represent the ***parent*** job, while tasks *D-1* through *D-4*
represent a ***daughter*** job. Daughter jobs begin only after their
enabling task is completed in the parent job*.* In this case, Task *D-1*
can commence only when *P-3* is complete. Daughter jobs may themselves
have daughter jobs. Consequently the precedence constraints between
tasks form a tree structure, but they are highly chainlike. The duration
of each task is depicted by the width of the boxes; tasks can be as
short as an hour or as long as several months. Tasks are assumed to have
a fixed duration for purposes of the EPM planning problem.

Each task can have an ***earliest allowable start time*** **(EAST)** and
a ***latest allowable finish time* (LAFT)**. The first task in a parent
job often has an EAST that is tied to the arrival of the weapon. The
task for the test itself often has a LAFT because the test has to be
conducted on or before a certain date to avoid tying up external
resources (e.g., off-site engineers).

The evaluation of each task requires a specific facility type (e.g., a
Task Bay with 220 electricity) and a qualified crew (e.g., 2--3 people
holding a specific certification). Facilities are hierarchically
arranged to reflect how one facility can be replaced by another, more
general facility. Each technician has a list of certifications to which
(s)he can be assigned. The availability of each technician and the
number of facilities of a given type varies by time period.

In a schedule, each job would be assigned to a specific facility and
given a specific team of qualified technicians. However, for planning
future technician/facility needs, it is currently sufficient to assign
tasks to a pool of facilities and technicians. Each technician is
assigned to certifications by specifying the amount of time that will be
devoted to each certification during each time period. No technician is
assigned more time units for a particular certification during a time
period than the sum of the task lengths (within that period) of tasks
requiring that certification. For example, if there is only one task
assigned to the time period and it requires 3 technicians for 2 units
each, then no technician can have more than 2 units assigned to that
certification during that time.

A production plan assigns a start time and facility to each task.
Preemption is not allowed, so a task will occupy that facility for its
entire duration beginning at its start time. A production plan is
feasible if:

1\) All precedence constraints, release dates, and deadlines are obeyed.

2\) Each task is assigned to an acceptable facility (type matches
requirement).

3\) The total amount of work scheduled for each facility type during any
particular time period does not exceed the availability of such
facilities.

4)  In each time period the requirements for technicians are matched by
    technician assignments and the total time assigned to each
    technician is not greater than an entire time period.

5)  For each time period, no technician is assigned to a particular
    certification for more time units than the sum of the task lengths
    (within that period) of tasks requiring that certification (in the
    example above, constraint (4) could be satisfied by a single
    technician for 6 hours).

Typically, an EPM planning problem spans a year and involves at least
500 jobs and 1000 tasks. Each job has from one to six tasks. About 28
facility types are involved along with 300 technicians, each of whom
holds 2--3 of the 80 possible certifications. In practice, these
planning problems are often infeasible. Consequently, the EPM module
formulates the EPM planning problem using ghost facilities and ghost
certification hours that reflect the number of additional resources that
are required by a production plan. Thus the only constraints on a
production plan are the scheduling constraints, which are much easier to
satisfy. With this formulation, production plans are evaluated by
summing the total number of hours of ghost facilities and ghost
technicians that are required in each time period. These two factors are
weighted equally.

# Mathematical Problem Description

In this section we provide a mathematical formulation of the EPM
planning problem described in the previous section. This general
formulation defines the underlying problem that is being solved by the
EPM. As such, it is qualitatively different from previous formulations
\[1,2,3,4\], which have been developed in the context of specific
solution techniques. Thus this general formulation provides a basis for
evaluating and comparing the previous formulations as well as the other
formulations described later in this report. Specifically, comparisons
with this mathematical formulation provide a basis for describing how
the formulations used in various solution strategies approximate or
simply reformulate the EPM planning.

For simplicity, we assume that technicians are available on all working
days and all certifications are valid for the entire planning horizon.
The granularity of the time dimension is a single workday that contains
eight hours of work, and each time period contains six days. Thus the
duration of a time period is 6. We have also ignored the facility
hierarchy structure that allows a one facility type to function as
another at a penalty; the data sets that have been used to benchmark
solution techniques for the EPM planning problem do not include facility
hierarchy information.

Formally, the general EPM formulation is as follows. Suppose we have

*J* tasks, indexed *j,i* = 1, 2, ..., *J* (with task *J* being a
termination task)

*K* facility types, indexed by either *k* = 1, 2, ..., *K*, or *i*= 1,
2, ..., *K*

*E* technicians (employees), indexed by *e* = 1, 2, ..., *E*

*C* certifications, indexed by *c* = 1, 2, ..., *C*

*T* time periods, indexed by *t* = 1, 2, ..., *T*,

and for each task, technician, and facility we have the following
inputs:

Task Inputs

> *d~j~* = duration of task *j* in days
>
> *r~j~* = the release date for task *j* (*i.e*. its EAST) in days
>
> *~j~* = latest time for completion of task *j* (*i.e*. its LAFT) in
> days
>
> $K_{j}$ *=* the set of possible facility types for task $j$
>
> *L~c~* = set of tasks requiring certification *c*

Technician Inputs

> *h~j~* = number of technicians (crew size) required for task *j*
>
> *H~et~* = days of availability for technician *e* in period *t*
>
> *C~e~* = set of certifications held by technician *e.*

Facility Inputs

> $M_{\text{kt}}$ = days of availability for facility type $k$ in period
> *t*

Let $j \prec i$denote that task $j$immediately precedes task $i$. The
decision variables in the general EPM formulation are:

> $x_{j}$ = the time at which task $j$ starts
>
> $f_{j}$ = the facility type used by task $j$.

The following variables are also used to define the objective function:

> *y~ect~* = number of days that technician *e* uses certification *c*
> in period *t*
>
> *f~kt~* = number of days of shortage for type *k* facilities in period
> *t*
>
> *q~ct~* = number of days of shortage for certification *c* in period
> *t*
>
> $p\left( j,x_{j},t \right)$ = number of days spent processing task
> $j$in time period t when it is started at time $x_{j}$
>
> $\Theta$ = Weight of the facilities overage in the objective
>
> $\Omega$ = Weight of the technician overage in the objective.

We are now prepared to define the general EPM formulation (Formulation
I):

minimize
$\Theta\sum_{k,t}^{}f_{\text{kt}} + \Omega\sum_{c,t}^{}q_{\text{ct}}$

subject to

$x_{j}³r_{j}$ $\text{j\} \{}$ (1)

$x_{j} \leq t_{j} - d_{j}$ $\text{j\} \{}$ (2)

$x_{j} + d_{j} \leq x_{i}$ $\forall j \prec i$ (3)

$f_{j}{ÎK}_{j}$ $\text{j\} \{}$ (4)

$\sum_{j:f_{j} = k}^{}{p\left( j,x_{j},t \right)} \leq M_{\text{kt}} + f_{\text{kt}}$
$\text{t,k\} \{}$ (5)

$\sum_{{cÎC}_{e}}^{}y_{\text{ect}} \leq H_{\text{et}}$ $\text{e,t\} \{}$
(6)

$\sum_{j:j \in L_{c}}^{}{p\left( j,x_{j},t \right)h_{j}} \leq \sum_{e}^{}y_{\text{ect}} + q_{\text{ct}}$
$\text{t,c\} \{}$ (7)

$y_{\text{ect}} \leq \sum_{j:{jÎL}_{c}}^{}{p\left( j,x_{j},t \right)}$
$\text{c,t,e:cÎC rSub \{ size 8\{e\} \} \} \{}$ (8)

$f_{\text{kt}}³0$ $\text{t,k\} \{}$ (9)

$q_{\text{ct}}³0$ $\text{t,c\} \{}$ (10)

Constraints (1), (2) and (3) enforce EASTs, LAFTs, and precedence
constraints respectively. Constraints (4) ensure that an appropriate
facility has been chosen, and constraints (5) ensure that there is
sufficient facility capacity in each time period. Constraints (6) ensure
that each technician is not used longer than his availability, and
constraints (7) ensure that there are enough technicians (by
certification) assigned to the work in each time period. Constraints (8)
ensure that no technician is assigned more time units for a
certification during a time period than the sum of the task lengths
(within that period) of tasks requiring that certification. Finally,
constraints (9) and (10) ensure that the shortages are nonnegative
quantities.

The current formulation used by the EPM is the
![](media/image2.wmf)-variable formulation. To compare the
![](media/image3.wmf)-variable formulation with Formulation I, note that
the solution process used by the EPM is broken into two stages \[1\]. In
the first stage, a heuristic method is used to find solutions to the
![](media/image4.wmf)-variable formulation[^1]. The
![](media/image5.wmf)-variable formulation is a linear formulation that
models tasks by an activity measure that reflects how much of the task
is being processed in a given time period. The solution to the
v-variable formulation is then processed to generate starting times for
tasks. In the second phase, these starting times are used by a linear
program to compute the facility and technician overages. Consequently,
the first phase is responsible for finding a start times that satisfy
constraints (1), (2) and (3) and for assigning tasks to facilities,
while the linear program in phase two simply computes the objective
function given these inputs subject to the remaining constraints in
Formulation I. This approach is similar to what we describe in the next
section, though we describe how to use a network flow algorithm \[7\] to
compute the technician allocation variables, which should be faster
compute than a general linear program.

# Optimization Formulations

This section describes three formulations of the EPM planning problem
that revise Formulation I to allow solution by general-purpose
optimization methods. In each of these formulations, the set of feasible
plans is the same as that in Formulation I. The difference is the manner
in which the linear constraints in Formulation I are managed.
Formulations II, III and IV are bound-constrained formulations that hide
the linear constraints through different penalty and
problem-transformation methodologies.

We begin by revisiting Formulation I to take note of how the structure
of the constrained region can be exploited to simplify this formulation.
The definition of Formulation Ia is given below. The objective of
Formulation Ia differs from Formulation I in that the constraints on the
technicians implicitly form a network flow problem that is solved
separately. Figure 2 illustrates this network flow problem. A network
flow problem is solved for each time period to compute $q'_{\text{ct}}$,
the shortage for certification $c$ in period $t$ (we use $q'$ to
indicate that the shortage is computed by the network flow subproblem).
The flow goes from node $s$ to node $t$. The technician assignments to
certifications are represented as flows from technician nodes to
certification nodes. The capacities on the edges of this network are set
as follows:

$$\begin{matrix}
e_{\text{se}} & & H_{\text{et}} \\
e_{\text{ec}} & = & \left\{ \begin{matrix}
\sum_{j:{jÎL}_{c}}^{}{p\left( j,x_{j},t \right)} & ,{cÎC}_{e} \\
0 & ,\text{else}
\end{matrix} \right.\  \\
e_{\text{ct}} & = & \sum_{j:{jÎL}_{c}}^{}{p\left( j,x_{j},t \right)h_{j}}
\end{matrix}$$

The value of $\varepsilon_{\text{se}}$reflects the upper bound on the
total time available for a technician (constraint (6)), the value of
$\varepsilon_{\text{ec}}$reflects the upper bound on the total time that
a technician can spend on a given certification (constraint (8)), and
the value of $\varepsilon_{\text{ct}}$reflects the total time required
(work) for certification $c$ in time period $t$. If this flow problem
can be solved such that the flow along each of the
edges$\varepsilon_{c,t}$is maximized, then all of the certification
demand for this time period can be met without additional technicians.
More generally, this may not be the case, and the value of
$q'_{\text{ct}}$ is the *residual capacity*, the amount of additional
flow that would be needed to maximize the flow along
$\varepsilon_{c,t}$.

![](media/image6.wmf)

Figure 2: Illustration of the network flow problem that is used to
compute $p'$.

We are now prepared to define the revised general EPM formulation
(Formulation Ia):

minimize
$\Theta\sum_{k,t}^{}{\text{max}\left( \sum_{j:f_{j} = k}^{}{p\left( j,x_{j},t \right) - M_{\text{kt}},0} \right) +}\Omega\sum_{c,t}^{}{q'_{ct}}$

subject to

$x_{j}³r_{j}$ $\forall j$ (11)

$x_{j} \leq t_{j} - d_{j}$ $\forall j$ (12)

$x_{j} + d_{j} \leq x_{i}$ $\forall j \prec i$ (13)

The only difference in terms of the space of solutions between
Formulation I and Ia, is the assumption that $\left| K_{j} \right| = 1$
for all j. This assumption was made here and in subsequent formulations
because the initial data set used in our computational experiments has
this property. We revisit the implications of this assumption in the
discussion section.

Formulation Ia can be transformed to a bound-constrained formulation by
observing that constraints (11) and (12) are simple bound constraints.
Formulation II simply folds the violation of precedence constraints into
the objective function with a simple penalty methodology. Let $P(x)$
equal ![](media/image7.wmf) if ![](media/image8.wmf)and zero otherwise.
Then Formulation II is:

minimize
$\Theta\sum_{k,t}^{}{\text{max}\left( \sum_{j:f_{j} = k}^{}{p\left( j,x_{j},t \right) - M_{\text{kt}},0} \right) +}\Omega\sum_{c,t}^{}{q'_{ct}} + \sum_{j \prec i}^{}{P\left( x_{j} + d_{j} - x_{i} \right)}$

subject to

$x_{j}³r_{j}$ $\text{j\} \{}$ (14)

$x_{j} \leq t_{j} - d_{j}$ $\text{j\} \{}$ (15)

For large problems, it may be difficult to satisfy all of these
precedence constraints. We can trade off the feasibility of precedence
constraints for the feasibility of the bound constraints by considering
a reformulation that defines $x_{j} = \Delta_{j} + z_{j}$, where
$z_{j} = r_{j}$if $x_{j}$ has no predecessors and
$z_{j} = \text{max}\left( r_{j},x_{k} + d_{k} \right)$ otherwise, where
k is the index of the predecessor. If we restrict ourselves to
$D_{j}³0$and $\Delta_{j} \leq \tau_{j} - (r_{j} + d_{j})$then $x_{j}$ is
feasible with respect to precedence constraints, though it may violate
its upper bounds. Formulation III uses a simple penalty method to
penalize violations of the upper bounds on $x_{j}$:

minimize ![](media/image9.wmf)

subject to

$0 \leq \Delta_{j} \leq \tau_{j} - (r_{j} + d_{j})$ $\text{j\} \{}$ (16)

$x_{j} = \Delta_{j} + z_{j}$ $\forall j$ (17)

The equality constraints (17) can easily be folded into the calculation
of the objective for this problem, so this problem is essentially
bound-constrained.

For problems with long chains, the upper bound on $\Delta_{j}$ may be
rather weak, leading to many feasible points in the bounded region that
violate the upper bounds on $x_{j}$. Consequently, we revised this
formulation to only allow plans that are feasible with respect to the
constraints in Formulation I. This formulation extends the notion of a
delta offset from Formulation III to a percentage offset, where a
percentage offset captures an offset through the percentage of remaining
feasibility. Specifically, we consider decision variables
${p\Delta}_{j} = \left( x_{j} - z_{j} \right)/\left( \tau_{j} - d_{j} - z_{j} \right)$
subject to the constraints ${pD}_{j}³0$ and ${pD}_{j} \leq 1$. Using
these variables, the upper and lower bounds on $x_{j}$ are immediately
satisfied. Consequently, Formulation IV contains no penalty terms:

minimize
$\Theta\sum_{k,t}^{}{\text{max}\left( \sum_{j:f_{j} = k}^{}{p\left( j,x_{j},t \right) - M_{\text{kt}},0} \right) +}\Omega\sum_{c,t}^{}{q'_{ct}}$

subject to

$0 \leq {pD}_{j} \leq 1$ $\text{j\} \{}$ (18)

$x_{j} = \left( \tau_{j} - d_{j} - z_{j} \right){p\Delta}_{j} + z_{j}$
$\forall j$ (19)

As with Formulation III, the equality constraints (19) can easily be
folded into the calculation of the objective for this problem, so this
problem is essentially bound-constrained. Since this formulation does
not contain any penalty terms, all solutions to Formulation IV represent
feasible solutions to Formulation I. However, this formulation may be
difficult to solve with a general-purpose optimization strategy since
the variables ${p\Delta}_{j}$ for tasks at the beginning of a job can
limit the sensitivity of a solution to values for later tasks by
allowing for a small absolute range of feasible values for the later
start times.

# Mixed Integer Linear Program Formulation

This section describes a mixed-integer linear-programming (MIP)
formulation of the EPM planning problem. This formulation differs from
Formulation I in that the time horizon is discretized to facilitate the
linearization of the formulation (in particular, constraints (5), (7)
and (8)).

The time horizon is broken into time periods, and each period is
decomposed into a fixed number of units (currently hours). Task lengths
are given in units. The MIP also considers an intermediate length of
time called a slot (currently a day). There are a fixed number of units
per slot and a fixed number of slots per period.

A schedule assigns a start time and facility type to each task using a
0-1 variable $x_{\text{jk}\tau}$that is 1 if task $j$ uses facility
type$k$ beginning at time slot $\tau$. Thus the time granularity for
scheduling in this model is time slots and not time periods. As in
Formulation I, each technician $e$ is assigned to certification $c$in
time period $t$ by specifying $y_{\text{ect}}$, the (fractional) number
of time units.

To limit the size of the MIP, \"big\" tasks with length at least a slot
are aligned with slots (days) by starting them at the beginning of a
slot. Short tasks (strictly less than a slot long) can start on unit
boundaries. This introduces less unforced idle time and makes the MIP
output more comparable to output from the PPM. This is implicitly
represented in the MIP with the $b\left( j,\overline{j} \right)$
function. Start times are specified as slots, but understood to be
mid-slot if (1) a predecessor is running at the start of the slot, and
(2) the task can finish before the end of the slot while obeying
precedence constraints. That is, a short task will never be split across
two slots.

To be more explicit, there are two types of precedence constraints:
packed and normal. In a normal precedence constraint, the successor
cannot start until the slot after the completion of the predecessor. In
a packed precedence constraint, the (short) successor can "pack" into
the remaining time in the slot where the predecessor finishes (without
going into the next slot). Therefore, long tasks have only normal
predecessor constraints with their single immediate ancestor (if it
exists).

If a short job has a packing precedence constraint with its immediate
ancestor, we may need to add one more (normal) constraint with a
nonadjacent predecessor. For example, if there is a chain of many
unit-sized jobs, each pair can share a slot, but the entire chain may
not fit into a single slot. Specifically, let the precedence chain for
short job *j* be *p~1~, p~2~, ..., p~d~*, where *p~1~* is job *j*'s
immediate ancestor, *p~2~* is *p~1~*'s ancestor and so on. There is a
constraint between job *j* and job *p~d~* if all the following
conditions are met:

1)  job *j* and jobs *p~1~* through *p~d-1~* all fit in a slot,

2)  adding job *p~d~* to the group in (1) would overflow a slot, and

3)  Jobs *p~1~* through *p~d~* all fit in a slot.

The first condition implies there are no extra constraints required
between job j and predecessors jobs p~1~ through p~d-1~. The second
condition implies a normal constraint between job j and p~d~. However,
if the third constraint is not met, then there will already be a
(nonadjacent) constraint earlier in the chain (e.g. between *p~1~* and
*p~d~*) and therefore adding one between *j* and *p~d~* would be
redundant.

The following variables are also used to define the MIP formulation:

> $T(j)$ = the set of time slots at which task $j$ can begin
>
> $b\left( j,\overline{j} \right)$ = 1 if $\overline{j} \prec j$ and
> task $\overline{j}$ can be "packed" with $j$

We are now prepared to define the MILP formulation (Formulation V):

minimize
$\Theta\sum_{k,t}^{}f_{\text{kt}} + \Omega\sum_{c,t}^{}q_{\text{ct}}$

subject to

$\sum_{tÎT(j)}^{}{\sum_{{kÎK}_{j}}^{}x_{\text{jk}t}} = 1$
$\text{j,k\} \{}$ (20)

$\sum_{k \in K_{\overline{j}}}^{}{\sum_{r_{\overline{j}} \leq \tau' \leq \tau}^{}x_{\overline{j}k\tau'}}\sum_{k \in K_{j}}^{}{\sum_{r_{j} \leq \overline{\tau} \leq \tau - d_{j} + b\left( j,\overline{j} \right)}^{}x_{\text{jk \{}\overline{\tau}}}$
$\text{tÎT left (j right ), \{ bar  \{j\}\}pj\} \{}$ (21)

$\sum_{j:{kÎK}_{j}}^{}{\sum_{tÎT(j)}^{}{p(j,t,t)x_{jtk}}}M_{kt} + f_{\text{kt}}$
$\text{t,k\} \{}$ (22)

$\sum_{{cÎC}_{e}}^{}y_{\text{ect}} \leq H_{\text{et}}$ $\text{e,t\} \{}$
(23)

$\sum_{j:{jÎL}_{c}}^{}{\sum_{tÎT(j)}^{}{\sum_{{kÎK}_{j}}^{}p(j,t,t)x_{jtk}}h_{j}}\sum_{e}^{}y_{\text{ect}} + q_{\text{ct}}$
$\text{t,c\} \{}$ (24)

$y_{\text{ect}} \leq \sum_{j:{jÎL}_{c}}^{}{\sum_{tÎT(j)}^{}{p(j,t,t)x_{jtk}}}$
$\text{c,t,e:cÎC rSub \{ size 8\{e\} \} \} \{}$ (25)

$f_{kt}³0$ $\text{t,k\} \{}$ (26)

$q_{\text{ct}}³0$ $\text{t,c\} \{}$ (27)

Constraints (20) assure that every task is completed. Constraints (21)
assure that a task is not started until all predecessors are completed.
One could assure some separation of start times by enforcing only one
such constraint on the mid-points of each (predecessor, successor) pair,
but this formulation is likely to be tighter. Constraints (22) ensure
that there is sufficient facility capacity in each time period.
Constraints (23) ensure that each technician is not used longer than his
availability, and constraints (24) ensure that there are enough
technicians assigned to meet the demand for certification hours in each
time period. Constraints (25) ensure that no technician is assigned more
time units for a certification during a time period than the sum of the
task lengths (within that period) of tasks requiring that certification.
Finally, constraints (26) and (27) ensure that the shortages are
nonnegative quantities.

# Data Characteristics and Preparation

To ensure that data input was consistent across all formulations, the
PPM pre-processor was used to generate data files. This also allowed the
PPM to perform the translation of data from the data repositories used
in practice at Pantex (Access databases), to a format that could be
easily interpreted for experimentation by the various experimental
formulations. The result was a set of ASCII files containing indexed
data (e.g. job, task, facility, technician, and certification
information).

The initial test data set was generated based on the Pantex database
containing information specific to the 62 and 87 system operations
performed during fiscal year 1998. The team felt that this was the most
refined Pantex data set. This data set does not include facility
hierarchies, and each task can be assigned to single facility type.

The ASCII files contained indices referring to individual elements (e.g.
the index of a task), indices of associated elements (e.g. the facility
and certification indices required by a given task), and information
specific to various data elements. For example, the EAST and LAFT
fractions associated with a task, or the quantity available of a given
resource. See the appendix for specific examples of these details and
technical comments elaborating on the exact contents of these input data
files.

The quantities contained in the ASCII files assume a base unit of one
day. Start times, EASTs, LAFTs, and task durations are represented as
fractions of days. An EAST is assumed to be the first day of the EAST
period and LAFTs are assumed to be the last day of the LAFT period for a
given task. Two versions of this dataset were used in our experiments:
(1) EASTs are rounded down and LAFTs are rounded up, and (2) the EASTs
and LAFTs are left as fractional values. The first data set reflects how
the EASTs and LAFTs are processed within the PPM, while the raw
fractional values reflect how more recent algorithms for the PPM have
been applied (e.g. see \[6\]).

We computed a lower bound of the optimal objective value for these two
data sets by considering the 43 tasks that require a type 2 facility;
preliminary studies indicated that the shortage of type 2 facilities was
a constraining factor in this data set \[6\]. We sorted these tasks in
ascending order according to LAFT, from which we computed the total
amount of work that must be accomplished with facility type 2 before
each time period. There are two type 2 facilities available, so we
compared the worked required with the available resources at each time
period. The maximum amount of work that cannot be scheduled in for type
2 facilities was 648 for the rounded problem set and 712 for the second
problem set. This analysis indicates that objective for these two
problems cannot fall below these values when $\Omega = \Theta = 1$.
Thus, the analysis indicates the importance of finding a way to increase
the amount of facility type 2 time available, or to decrease the overall
required workload.

Finally, data validation between the experimental formulations and the
EPM module was accomplished by fixing the start times of the tasks in
the data set (setting start time equal to EAST) and computing resource
utilization using both implementations. The resulting objective function
values were compared to validate the experimental formulations.

# Computational Experience

This section describes computational experience with Formulations II,
III and IV using a standard evolutionary algorithm. We have also
evaluated the final solution generated by the $v$-variable formulation
to determine whether or not it is locally optimal. These optimizers were
taken from the SGOPT optimization library, and the resource overage was
computed with a problem formulation that was carefully benchmarked
against the EPM $v$-variable formulation.

##  Evolutionary Algorithms

We have done a preliminary evaluation of the applicability of
evolutionary algorithms (EAs) to Formulations II, III and IV. The goal
of this effort was to evaluate whether or not the domain-specific
methods developed by the PPM team (particularly the $v$-variable and
$s$-variable formulations) provide significantly better solutions than a
general-purpose global optimization heuristic like an EA. The EA used in
this work is a method similar to evolutionary programming \[1\], a
standard class of EAs used to optimize over continuous domains. This EA
uses an intermediate crossover operator and a self-adapted normally
distributed mutation operator. No effort was made to tune this method
for these formulations, and bound constraints were implemented with a
penalty method that biases the search towards feasible points.

In Formulations II and III, the EA had difficulty identifying feasible
points. Even when allowed to run for an extended period of time, this EA
was unlikely to find a single feasible point. In Formulation IV, all
points are feasible but the search is highly sensitive to some
parameters more than others. The EA was used to optimize with
Formulation IV with a time limit of 10,000 function evaluations; a
function evaluation consists of computing the resource overage for a
single production plan. On code compiled *without* compiler optimization
turned on (and in fact, with debugging flags set on), this took about 20
minutes on a Sun Sparc 20. The EA was run with a set of 15 random seeds
on both the rounded and unrounded data sets, and the distribution of
final solutions generated by the EA had the following characteristics:

  --------------- --------------- ------------ ------------- -------------
  Statistic       Minimum         Median       Mean          Maximum

  Rounded         3269            3722         3728          4226

  Unrounded       3560            3615         3666          3920
  --------------- --------------- ------------ ------------- -------------

This should be compared with the solution generated by the $v$-variable
formulation, which was 4281 and 4479 for the rounded and unrounded data
sets respectively. Thus in all of these trials the EA found better
solutions than the solution generated by the $v$-variable formulation,
and the average solution generated by the EA is at least 12% lower than
the $v$-variable solution. Finally, from our lower bound on the optimal
solution value, we can determine that in the unrounded data set the EA
found solutions within 1% of the global optimum in 46% of the trials;
for the rounded data set the EA found such a solution in only one of the
trials. Consequently, these results indicate that general-purpose
optimization strategies may be effective for this application

##  Local Refinement

We evaluated the degree to which the final solution generated by the
$v$-variable formulation is locally optimal by applying a simple direct
search procedure to this solution. We applied a simple pattern search
method \[5\] to this solution using Formulation II with a penalty factor
of 100,000 for violated precedence constraints. This algorithm was run
until the step length parameter fell below ![](media/image10.wmf); this
required approximately 10,000 function evaluations, and the pattern
search method finished within 25 minutes. This optimizer was able to
refine the initial ![](media/image11.wmf)-variable solution for both the
unrounded and rounded data sets to a globally optimal point. This shows
that our bound on the global optimum is tight for these problem sets.
Further, this result strongly suggests that the $v$-variable formulation
does not generate locally optimal solutions, and that refining the
solutions generated for different formulations could substantially
improve their quality.

# Evaluating the EPM Problem Formulation

Our reformulation of the EPM production planning problem has led to
several insights into our current formulations of this problem. This
section discusses these insights and provides suggestions for
strengthening the problem formulation

## An Optimistic Approximation

Formulations I and Ia are approximations to the actual scheduling
problem faced by Pantex. The use of such an approximate model is
appropriate because these models are being used for broader planning
purposes. Thus data uncertainties in the model are less important
because it does not aim to provide a true schedule to Pantex.

Because these problem formulations are approximations, it is important
to understand whether they provide an optimistic or pessimistic
evaluation of the resources needed to complete a set of tasks. In fact,
these formulations offer an optimistic evaluation because the assignment
of technicians to tasks is not exact. Consequently, solutions to these
forms of the EPM production planning problem are best used for arguing
that too few resources are available to meet a set of production goals.

It is also important to note that the granularity of the time period
over which technicians are assigned to certifications impacts the
accuracy of these formulations. Specifically, solutions with longer time
periods are more optimistic than solutions with shorter time periods.
This is unfortunate because the use of longer time periods is very
desirable since this reduces the number of variables in the problem.
Thus we need to evaluate the trade-off between the desired level of
accuracy and the time-frame for solving problems, and it might be
interesting for the PPM toolkit to allow users to explicitly control
this trade-off (e.g. to get more accurate predictions once a reasonable
approximate solution was found).

## Evaluating the Network Flow Subproblem

The network flow subproblem used in Formulations Ia-IV captures the
assignment of technicians to certifications. The following example shows
how adding more work to a time period can actually lead the network flow
subproblem to ***reduce*** the predicted technician overage. Consider
the following set of tasks that are run in a given time period:

  --------------- --------------- ---------------------- -----------------
  Task \#         Crewsize        Duration (Days)        Certification

  1               7               2                      1

  2               1               1                      1

  3               1               1                      1

  4               1               1                      1

  5               4               6                      2

  6               1               1                      1
  --------------- --------------- ---------------------- -----------------

Further, suppose we have seven technicians all of which have
certification one and four of which have certification two. The
following figure illustrates the corresponding network flow problem that
can be used to determine the overage when tasks 1-5 are scheduled for a
six-day time period:

![](media/image12.wmf)

This network has a minimum cut with a flow of 40, which means that two
additional technician days are needed (in particular, to meet the demand
for certification one). Now consider the following network flow when the
sixth task is also included:

![](media/image13.wmf)

In this case the network has a minimum cut with a flow of 42, which
means that no additional technician days are needed. Thus by adding a
task to a time period we have reduced the amount of technician overage!

The reason for this discrepancy is the fact that technician resources
are constrained on the granularity of a time period, and because
technicians are assigned to certifications rather than tasks. We expect
that assigning technicians to tasks will eliminate this problem, and it
will provide a tighter formulation; that is, it will provide a closer
estimate of the true resource overages. We can augment Formulation I
using the variable

> *Y~ejt~* = number of days that technician *e* works on task *j* in
> period *t*

to get the following formulation (Formulation VI):

minimize $\sum_{k,t}^{}f_{\text{kt}} + \sum_{c,t}^{}q_{\text{ct}}$

subject to

$x_{j}³r_{j}$ $\text{j\} \{}$ (28)

$x_{j} \leq t_{j} - d_{j}$ $\forall j$ (29)

$x_{j} + d_{j} \leq x_{\overline{j}}$ $\text{jp \{ bar  \{j\}\}\} \{}$
(30)

$f_{j}{ÎK}_{j}$ $\text{j\} \{}$ (31)

$\sum_{j:f_{j} = k}^{}{p\left( j,x_{j},t \right)} \leq M_{\text{kt}} + f_{\text{kt}}$
$\text{t,k\} \{}$ (32)

$Y_{\text{ejt}} \leq p\left( j,x_{j},t \right)$ $\text{t,e,j\} \{}$ (33)

$y_{\text{ect}} = \sum_{j:{jÎL}_{c}}^{}Y_{\text{ejt}}$ $\text{e,t\} \{}$
(34)

$\sum_{{cÎC}_{e}}^{}y_{\text{ect}} \leq H_{\text{et}}$ $\text{e,t\} \{}$
(35)

$\sum_{j:{jÎL}_{c}}^{}{p\left( j,x_{j},t \right)h_{j}} \leq \sum_{e}^{}y_{\text{ect}} + q_{\text{ct}}$
$\text{t,c\} \{}$ (36)

$y_{\text{ect}} \leq \sum_{j:{jÎL}_{c}}^{}{p\left( j,x_{j},t \right)}$
$\text{c,t,e:cÎC rSub \{ size 8\{e\} \} \} \{}$ (37)

$f_{kt}³0$ $\text{t,k\} \{}$ (38)

$q_{\text{ct}}³0$ $\text{t,c\} \{}$ (39)

$Y_{\text{ejt}}³0$ $\text{t,e,j\} \{}$ (40)

Constraints (33), (34) and (40) are the principle changes from
Formulation I. Constraint (33) ensures that a technician can only work
on a task as many hours as that task is scheduled for the given time
period. Constraint (34) explicitly relates *y~ect~* to *Y~ejt~*, which
was implicitly done earlier by the definition of *y~ect~*. Finally,
constraint (40) simply ensures that technicians work a nonnegative
number of hours on each task.

Formulation VI is tighter than Formulation I and its derivatives because
of the additional constraint on the *Y~ejt~* variables. Further, we can
revise this formulation like Formulation Ia to assume that
$\left| K_{j} \right| = 1$ for all j and to formulate a network flow
subproblem. Formulation VIa requires a network flow subproblem that
represents technician assignments to task as flows from technician nodes
to task nodes. The weights on the edges of this network are set as
follows:

$$\begin{matrix}
e_{\text{se}} & & H_{\text{et}} \\
e_{\text{ej}} & = & \left\{ \begin{matrix}
p\left( j,x_{j},t \right) & ,{cÎC}_{e} \\
0 & ,\text{else}
\end{matrix} \right.\  \\
e_{\text{jt}} & = & p\left( j,x_{j},t \right)h_{j}
\end{matrix}$$

This network is illustrated in Figure 3. Note that instead of
certification nodes we now have task nodes. Since the total hours of
certification overage equals the number of hours that tasks are not
scheduled, this network flow problem captures the same information as
the previous network flow problems. Further, the values of the
certification overate,$q'_{\text{ct}}$, could be computed explicitly to
accommodate an objective function that weighted them differently.

![](media/image14.wmf)

Figure 3: Illustration of the network flow subproblem in Formulation
VIa.

## Smoothness

The resource overage objective function used for the EPM is piecewise
linear because the underlying network flow problem is linear. This is a
particularly nice class of problems. For example, subgradient or
bundling optimization methods would probably be a better choice than the
pattern search method used in our study. However, using a subgradient
method requires a more explicit solution to the network flow problem,
since this method would need to be reformulated to provide gradient
information with respect to the decision variables.

As a first step in this direction we analyze the derivatives of
Formulation I. We now compute the change in the objective function (sum
of facility and technician overages, all equally weighted) as a single
job is moved infinitesimally forward or backward in time. For each time
slot, we have a flow network as illustrated in Figure 2. For a
particular certification C, technician assignments are represented by
the flow through the subnetwork consisting of nodes *s, C, t,* and those
workers *E*~i~ with certification *C*.

The gradient with respect to a job *J* with certification *C* depends
upon the structure of the flow and the *residual graph*. Given a flow
*f(i,j)* over each edge *(i,j)* in a graph where each edge has capacity
ε*~ij~*, the residual graph has the same topology as the original graph,
but the new capacities
$e_{\text{ij}}^{'} = e_{\text{ij}} - f_{\text{ij}}$. This is a directed
graph. In the networks we use to assign technicians, capacity is only
positive in the forward direction (from *s* to *E~i~*, from *E~i~* to
*C~j\ ~*and from *C~j\ ~*to *t*), and backward capacity is *0*. Flow is
antisymmetric (*f~ij~* = -*f~ji~*). Thus for one of the forward edges,
the residual capacity represents the amount of extra flow an edge can
carry forward. For a backward edge, (*j,i*), the residual capacity is
*f~ij\ ~*(the amount of flow going forward). This represents the ability
to "send" flow from node *j* to node *i* by holding it back at node i.
An *augmenting path* is an *s*-to-*t* path in the residual graph. A flow
is maximum if and only if there are no augmenting paths in the residual
graph. In particular, for a maximum flow, every path from *s* to *t* in
the network has at least one *saturated* edge, that is, an edge where
the flow is equal to the capacity of the edge (and hence the forward
residual capacity is zero).

We now consider the subnetwork representing the technician assignment to
certification C and distinguish the direct *s*-to-*t* paths based upon
the pattern of saturated edges in the maximum flow. In the following
diagrams, the hatched edges are saturated. The simplest case is the type
0 path where the (*C,t*) edge is the only saturated edge (recall there
is only one (*C,t*) edge for each certification *C*).

![](media/image15.wmf)

If there is a type-0 path, then the gradient is 0. If the work is
slightly increased, then employee E can do the extra work (additional
capacity on the rest of the path), so there is no overage created. If
the work is slightly decreased, the overage for certification *C*
remains zero. There is no opportunity to use this decrease in work for
certification *C* to increase work in another unfinished certification.
If any employee could shift work from *C* to another (unfinished)
certification *C*'', then they would in any maximum flow (employee E
could complete the extra work on certification *C*).

There are 3 possible saturation patterns for the direct paths from *s*
to workers *E* having certification *C*. We associate the type with the
path and the worker represented on the path. The dashed line on edge
(*C,t*) indicates that edge could be saturated or not. First consider
the case where (*C,t*) is not saturated.

If a job of certification *C* is shifted slightly into the time period
(work increase δ), then the capacity of edge (*C,t*) increases by *H~j~*
δ, where *H~j~* is the crew size for job *j*, and the capacity of edge
(*E,C*) increases by δ. The flow over edge (*C,t*) can increase δ for
each *s*-to-*E* augmenting path in the residual graph, where worker *E*
has certification *C*. For type-1 workers, this augmenting path is
trivial (edge (*s,E*)). These paths cannot exist for type-2 workers,
since their existence would imply an augmenting path in the original
residual graph. For type-3 workers, there must be a more complicated
augmenting path such as the one illustrated below. Such a path is not
ruled out, since in the previous max flow, edge *(E,C)* was saturated
and therefore not in the residual graph. Augmenting along this path
shifts work on certification *C*~2~ originally done by worker *E* to
worker *E~2~* and work on certification*C~3~* from worker *E~2~* to
worker *E~3~*. Essentially, such an augmenting path makes a type-3 path
effectively type 1. Thus the work-increasing gradient for this time
period is $H_{j} - n_{\text{SE}}$, where *n~SE~* is the number of
workers E with s-to-E augmenting paths. More explicitly we have
$n_{\text{SE}} = n_{1} + n_{3a}$, where *n~1~* is the number of type-1
paths for certification C and *n~3a~* is the number of type-3 paths with
an augmenting path to E. Note that these augmenting paths could share
edges, so we could not **maximally** augment them all simultaneously.
However we could augment them all for sufficiently small δ.

We now consider the gradient when shifting work of certification *C* out
of the time period. The capacity on edge (*C,t*) now decreases by
$H_{j}d$ and the capacity of edge (*E,C*) decreases by δ. However, δ
flow is maintained for each path with an *E*-to-*t* augmenting path in
the residual graph. This corresponds to worker E shifting work from
certification *C* to another. Paths of type 1 cannot have such an
augmenting path because it would imply an augmenting path in the
original residual graph. Type-2 paths have a trivial augmenting path
along edges (*E*,*C*) and (*C*,*t*), corresponding to worker *E*
maintaining the same level of effort on certification *C*. Type-3 paths
can have more complicated augmenting paths (representing a
perhaps-cascading shift of assignments among workers to ultimately
increase effort on another certification with overage). Sliding a job
out of the time period decreases work available for certification *C* by
*H~j~*δ and the amount of work assigned by $(H_{j} - n_{\text{Et}})d$,
where *n~Et~* is the number of workers *E* with an *E*-to-*t* augmenting
path. Therefore the work-decreasing gradient for this time period
(change in total overage) is$n_{\text{Et}}$.

Now consider the case where there is no overage for certification *C*
(edge (*C,t*) is saturated). Increasing work is identical to the case
where it is not saturated except that we cannot create negative overage
for certification *C*. Therefore the work-increasing gradient for this
time period is $\text{min}(H_{j} - n_{\text{SE}},0)$. Note that now
type-2 workers can have *s*-to-*E* augmenting paths. If work is
decreased, the overage can decrease by at most$H_{j}d$. This must all
come from workers shifting to work on other certifications. Type 2 paths
no longer have an automatic augmenting path. The work-decreasing
gradient for this time period is $\text{min}(n_{\text{Et}},H_{j})$.

Because the flows for the time periods are independent, the total
gradient is the sum of a work-increasing gradient on one end of the
moving job and a work-decreasing gradient on the other.

# Discussion

Our formulation of the general EPM production planning problem in
Formulation I provides a basis for comparison between different
formulations for this problem. Formulation Ia illustrates how this
problem can be reformulated to facilitate the application of
general-purpose optimization methods. Furthermore, Formulations II, III
and IV reformulate this problem so that simple bound-constrained
optimizers can be used to solve it. The MIP formulation can be viewed as
an approximation to Formulation I to the extent that the discretization
of time creates (a) a discrete set of starting points for jobs and (b)
the packing of short jobs into time slots approximates the scheduling of
these jobs together within a day.

Our empirical results with EAs offer evidence that general-purpose
optimizers can be effectively applied to this application both for
finding near-optimal solutions, but also for generating a distribution
of good solutions. Further, our refinement experiment highlights the
fact that the formulations that we consider for the EPM planning problem
need to include a final refinement step. The MILP formulation of the EPM
planning problem (Formulation V) is still being developed, but
preliminary experiments with this formulation suggest that the bound
derived from this linear model may not be particularly strong.

We are extending this work in several directions. First, we have begun
to develop EAs and pattern search methods that can be applied to
linearly constrained problems like Formulation Ia. We expect that
general-purpose optimizers that appropriately account for linear
constraints can be more effectively applied to Formulation Ia than the
methods that are applied to Formulation IV. The sensitivity of the
variables along the precedence chains is a worrisome feature for this
formulation, and we expect that it will be particularly problematic for
problems with long precedence chains.

We have also begun to reconsider the simplifications made to develop
Formulations II, III, IV. In particular, these formulations assume that
every task can only be assigned to one facility type; this
simplification was made to facilitate benchmark comparisons between the
EPM solutions and the methods developed within 9200. Limiting the
facility assignments reduces the set of decision variables in
Formulations II, III and IV to the scheduling start times for tasks.
However, if this simplification were not made then the decision
variables would also include the facility assignments, which would make
the planning problem a mixed-integer nonlinear optimization problem. We
expect that these problems would be significantly harder to solve,
especially if the facility hierarchy was also included in the
formulation.

# Acknowledgements {#acknowledgements .unnumbered}

We thank Justin Brickel for his work analyzing the derivative properties
of the EPM problem formulation and for bring to our attention the
example in Section 8.2. We also thank the members of the PPM team for
their helpful discussions.

# Bibliography

1.  D.B. Fogel, *Evolutionary Computation*. IEEE Press. Piscataway, NJ.
    1995.

2.  []{#_Ref468597866 .anchor}E.A. Kjeldgaard, D.A. Jones, G.F. List,
    M.A. Turnquist, J.W. Angelo, R.D. Hopson and Hudson, "Swords into
    Plowshares: Nuclear Weapon Dismantlement, Evaluation, and
    Maintenance at Pantex", *INTERFACES*, 1999. To appear.

3.  D.A. Jones, C.R. Lawton, G.F. List, G. F. and M.A. Turnquist, "The
    Pantex model: Formulations of the evaluation planning module\",
    Sandia National Laboratories, SAND99-2095, 1998.

4.  E.A. Kjeldgaard, D.A. Jones, G.F. List, M.A. Turnquist, "Planning
    and Scheduling for Agile Manufacturers: The Pantex Process Model",
    Sandia National Laboratories, SAND98-0030, 1998.

5.  J.E. Dennis and V.J. Torczon, "Derivative-free pattern search
    methods for multidisciplinary design problems", *Proc Fifth AIAA
    Symp on Multidisciplinary Analysis and Optimization*. Pp. 922-932.
    1994.

6.  L.K. Nozick, M.A. Turnquist, C.R. Lawton, G.F. List, D.A. Jones,
    "Production Planning for a Project Job Shop, with Application to
    Disassembly, Evaluation and Maintenance of Nuclear Weapons",
    Submitted to *J Production Planning and Control*. Nov, 1999.

7.  R. Ahuja, T. Magnanti, and J. Orlin, "Network Flows: Theory,
    Algorithms, and Applications", Prentice Hall, Englewood Cliffs, NJ,
    1993.

# Appendix

\##

\## Database of tasks

\##

\## Format:

\## integer id

\## char string description

\## integer east (units are time periods)

\## integer laft (units are time periods)

\## double duration (units are time periods)

\## integer predecessor ID

\## integer child_flag (1 if true)

\## integer number of technicians

\## integer certification ID

\## integer facility type

\##

130

1,432,2.333333,8.5,2.5,-1,0,2,6,1

2,489,.3333333,7.5,1.666667,-1,0,1,8,2

3,521,0,29.66667,4.166667,-1,0,2,6,1

.

.

.

\##

\## Database of facility availability by time period

\##

\## Format: each row indicates the number of each of the

\## facilities that are available. The order is assumed to follow that

\## given in the facilities database;

\##

42

4,2,4,4,4,1,2,2

4,2,4,4,4,1,2,2

4,2,4,4,4,1,2,2

.

.

.

\##

\## Database of facility hierarchy

\##

\## Format:

\## integer facility ID

\## char string description

\## integer facility predecessor in hierarchy

\##

8

1,1,-1

2,2,-1

3,10,-1

.

.

\##

\## Database of technicians

\##

\## Format:

\## integer technician ID

\## char string description

\## integer number of certifications

\## integer,\...,integer certification (in sorted order)

\##

47

1,7,1,10

2,15,1,10

3,17,1,10

.

.

.

**DISTRIBUTION:**

George List

Department of Civil Engineering

Rensselaer Polytechnic Institute

Troy, NY 12180-3590

Linda Nozick

Cornell University

School of Civil and Environmental Engineering

Hollister Hall

Ithaca, NY 14850

Mark Turnquist

Cornell University

School of Civil and Environmental Engineering

Hollister Hall

Ithaca, NY 14850

1 1110 David Womble 9222

1 1110 Cindy Phillips 9211

10 1110 William Hart 9211

1 0451 Craig Lawton 6235

1 0451 Dean Jones 6235

1 0451 Ed Kjeldgaard 6235

1 0451 Steven Wright 6235

1 0451 Jennifer Nelson 6235

1 1089 Central Technical Files, 8940-2

1 0899 Technical Library, 9616

1 0612 Review & Approval Desk, 9612

For DOE/OSTI

[^1]: ^\*^ The current algorithm implemented for stage one in the Pantex
    Process Model is actually a slight variation of the formulation
    documented in \[3\]. The formulation documented in \[3\] has a set
    of constraints that ensure start times are not computed in a way
    that violates precedence. In the variation of the algorithm
    implemented in the Pantex Process Model, primarily to decrease
    computation time, these constraints have been relaxed for those
    tasks that are shorter than one time unit. Our comparative results
    reflect what is implemented in the Pantex Process Model.