Equipment scheduling at mail processing and distribution centers.

With this background in mind, we now present the basic multi-level lot sizing model for the equipment scheduling problem. The following notation is used in the developments.

Indices

i, o = indices for input and output mail streams;

n, p = indices for nodes (a unique operation is associated with each node);

g = index for machine groups;

t = index for time periods; t [member of] T = {1,..., 48}, t = 1 corresponds to 7:00 a.m.

Sets

G = set of machine groups, G = {AFCS, MLOCR, DBCS, DBCS-OSS};

G(n) = set of machine groups capable of performing the operation at node n;

I, O = sets of input and output mail streams for the facility;

N = set of nodes;

N(g) = set of nodes whose operations can be performed by machines in group g;

P(n) = set of nodes immediately preceding node n;

I(n) = set of input mail streams to node n;

O(n) = set of output mail streams from node n;

T(n) = set of periods during which an operation at node n can be performed;

T(i) = set of periods during which mail arrivals i may be processed; generally, T(i) [??] T(n) where n is the node that accepts the arrivals of input stream i.

Parameters

[u.sub.n] = amount of mail left unprocessed at node n from the previous day;

[a.sub.i](t) = amount of external mail of type i [member of] I arriving at the facility during period t, t [member of] T(i);

[m.sub.g](t) = number of machines available in group g during period t;

[[rho].sub.n] = processing rate for operation at node n (pieces/period);

[f.sub.npn] = fraction of mail processed at predecessor node p that is sent to successor node n;

[[tau].sub.1] = the amount of time required to start up a machine; currently set at 10 minutes;

[[tau].sub.2] = the amount of time required to clear a machine; currently set at 10 minutes.

Decision variables

[v.sub.n](t) = inventory level of mail at node n at the end of period t, t [member of] T;

[w.sub.ng](t) = amount of mail processed at node n by machine group g during period t, t [member of] T(n);

[Y.sub.ng](t) = number of machines devoted to the operation that is performed at node n by machine group g during period t, t [member of] T(n);

[Z.sub.ng.sup.1](t) = number of startups in machine group g for operation n at the beginning of period t, t [member of] T(n);

[Z.sub.ng.sup.2](t) = number of clearance operations performed at node n in machine group g at the end of period t, t [member of] T(n).

Constraints

[u.sub.n] + [summation over (i[member of]I(n), 1[member of]T(i))] [a.sub.i](1) - [summation over (g[member of]G(n))] [w.sub.ng](1) = [v.sub.n](1), [for all]n [member of] N, (1a)

[v.sub.n](t - 1) + [summation over (i[member of]I(n),t[member of]T(i))] [a.sub.i](t) + [summation over (p[member of]P(n))] [f.sub.pn] [summation over (g[member of]G(p))] [w.sub.pg](t - 1) - [summation over (g[member of]G(n))] [w.sub.ng](t) = [v.sub.n](t), [for all]t [member of] T\{1}, n [member of] N, (1b)

[w.sub.ng](t) + [[[tau].sub.1]/30][[rho].sub.n][Z.sub.ng.sup.1](t) + [[[tau].sub.2]/30][[rho].sub.n][Z.sub.ng.sup.2](t) [less than or equal to] [[rho].sub.n][Y.sub.ng](t), [for all]g [member of] G(n), t [member of] T(n), n [member of] N, (1c)

[summation over (n[member of]N(g))] [Y.sub.ng](t) [less than or equal to] [m.sub.g](t), [for all]t [member of] T, g [member of] G, (1d)

[Z.sub.ng.sup.1](t) - [Z.sub.ng.sup.2](t - 1) = [Y.sub.ng](t) - [Y.sub.ng](t - 1), [for all]t [member of] T(n), n [member of] N(g), g [member of] G, (1e)

[Z.sub.ng.sup.1](t) [greater than or equal to] 0, [Z.sub.ng.sup.2](t) [greater than or equal to] 0, [for all]t [member of] T(n), n [member of] N(g), g [member of] G, (1f)

[v.sub.n](t), [w.sub.ng](t) [greater than or equal to] 0, [for all]t [member of] T(n), n [member of] N, g [member of] G(n), (1g)

[Y.sub.ng](t) [greater than or equal to] 0 and integer, [for all]g [member of] G(n), t [member of] T(n), n [member of] N. (1h)

1. Inventory balance constraints of Equations (1a) and (1b). Constraint (1a) stipulates that for each operation n at the beginning of the day in period 1, the mail remaining from the previous day, plus the sum of external arrivals, minus the sum of mail processed during this period, must equal the ending inventory indicated on the right-hand side. Constraint (1b) imposes the same requirements in all other periods but with the inclusion of the mail transferred from predecessor nodes.

2. Production capacity limitation of Equation (1c). Constraint (1c) stipulates that in period t, the workload at node n allocated to group g, plus the lost capacity during startup and clearance, must be less than or equal to the processing capacity of the machines in group g assigned to operation n at time t.

3. Machine capacity limitation of Equation (1d). Constraint (1d) ensures that the number of machines in group g operating in time period t is less than or equal to the number of machines available.

4. Definition of startup and clearance activities in Equation (1e). Constraint (1e) defines the startup and clearance activities, each of which takes a certain amount of time denoted by [[tau].sub.1] and [[tau].sub.2], respectively. As mentioned, the lost production capacity associated with these activities is taken into account in constraint (1c).

5. Constraints on variables in Equations (1f), (1g) and (1h). Constraints (1f), (1g) and (1h) define the non-negative values of all variables and the integer requirement of variable [Y.sub.ng](t). Notice that the startup and clearance variables are not defined as being integer. As we will see, because we are trying to minimize a linear function of the startup variables, for a given integer value of [Y.sub.ng](t), [Z.sub.ng.sup.1](t) and [Z.sub.ng.sup.2](t) will be integer-valued in any feasible solution.

6. Additional flow management considerations. To provide more control over the pattern of work flow over the day, it might be desirable to add a constraint originally proposed by Berman et al. (1997). In specifying the constraint, let [[theta].sub.n](t') be the fraction of work associated with operation n [member of] N' [??] N that must be completed by time t' [member of] T(n). The following constraint ensures that the volume of mail processed before time t' (left-hand side) is greater than or equal to [[theta].sub.n](t') of the mail processed over the day:

[summation over (t[less than or equal to]t')][summation over (g[member of]G(n))] [w.sub.ng](t) [greater than or equal to] [[theta].sub.n](t') [summation over (t[member of]T(n))][summation over (g[member of]G(n))] [w.sub.ng](t), [for all]t' [member of] T(n), n [member of] N'. (1i)

The inclusion of Equation (1i) allows the user to better manage the workflow of each operation over the course of the day. However, it requires a somewhat arbitrary specification of the fractions [[theta].sub.n](t') for each t' [member of] T(n) and n [member of] N'. Poor choices could seriously over-constrain the model and lead to inferior, if not infeasible, results. In light of this, our recommendation is to omit Equation (1i) in the first run and, if the solutions are not satisfactory, add it in subsequent runs to achieve a more desirable workflow distribution.

4.2. Optimality criteria

Four criteria have been identified for evaluating an equipment schedule: (i) the percentage of arriving mail processed in a day; (ii) the number of 8-hour shifts required to run the equipment; (iii) the number of machine setups in a day; and (iv) the weighted sum of the number of working periods in a day. The second criterion represents an estimate of staffing costs and is the most important. The first criterion represents a commitment to service self-imposed by the USPS, the third and fourth criteria offer further opportunities to improve the equipment schedules. These criteria are explained below.

4.1.1. Minimize the ending inventory: process as much mail as possible

The fundamental requirement of an equipment schedule is to process all the mail arriving at a facility in a timely manner. Due to capacity limitations of the equipment, however, this may not be possible so some of the mail may have to be held over to the next day. To push as much mail as the constraints permit, we solve the following problem for each day of the week.

Minimize [summation over (n[member of]N)][v.sub.n](48) subject to Equations (1a)-(1h)

(objective 1).

The objective is to minimize the ending inventory. Conservation of flow at each node in the network guarantees that there will be no accumulation of mail at any upstream workstation unless the capacity of the system limits its processing.

4.1.2. Minimize the number of full-time shifts: an approximation to the daily staffing cost

As previously mentioned, the predominant cost in running a P & DC is associated with the workforce. Maintenance is minimal by comparison, and the equipment is viewed as a sunk cost. The quality of an equipment schedule, then, must be judged by the staffing cost it imposes. As such, we introduce the second criterion: the number of full-time shifts. This number represents an approximation of the daily staffing cost and, as shown presently, provides a link between equipment scheduling and staff scheduling.