FULL PROOFS for the MATCHUP PAPER James C. Bean John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 John Mittenthal Department of Decision Sciences and Engineering Systems Rensselaer Polytechnic Institute Troy,NY 12181 Charles E. Noon Department of Management College of Business Administration University of Tennessee Knoxville, TN 37996 Technical Report 89-17 May 1989

FULL PROOFS for the MATCHUP PAPER James C. Beant John R. Birget Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 John Mittenthal Department of Decision Sciences and Engineering Systems Rensselaer Polytechnic Institute Troy, NY 12181 Charles E. Noon Department of Management College of Business Administration University of Tennessee Knoxville, TN 37996 May 18, 1989 Below are proofs, in full detail, for the two major theorems in Bean, Birge, Mittenthal and Noon [1986]. Proof of Theorem 1: McKenzie [Lemma 1, 1976] proves the result given (a). This condition does not cover scheduling problems with xo E aXo, the boundary of Xo. Also, the interiority of Xit nlt may be difficult to verify. Conditions (b), (c) and (d) are reasonable assumptions that may be more readily verified. We show that each implies (i) and use (i) and the structure of ft to showt (ii). Condition (b) implies tlhat t1here is sufficient slack in the schedule that, at some future time, all resources will be utilized under capacity. We wish to show that Ft(xt) is subdifferentiable at xf. t The work of James Bean wass supported ill part by NSF Grant ECS-8700836 to The Universitv of Michigan.: The work of John Birge was supported in part by the Office of Naval Research under Grant ONR-N00014-86-IK-0628 to The University of Michigan and by the National Research Council under a Research Associateship at the Naval Postgraduate School. 1

Consider Xt E Xt n Yt. Let {T, r > t} attain Ft(xt) so that 00 Ft(xt) = fr(Xr, xr+1). r=t Let xt = Xt + 7 where -y is a vector of perturbations such that x E Xt n Yt. To show subdifferentiability, we show that there does not exist a y such that the one sided directional derivative of Ft with respect to 7 is -xo (Theorem 23.3, Rockafellar [1970]). For this, it is sufficient to show that Ft(x') > Ft(xt) - IKllxt - xtj, where K is a constant. If, Ftx Ft(x,) > Ft(xt), the result is trivial. If Ft(xt) > Ft(x\), construct a path, {x}r>t, with a suitable bound. Assume {x'.} is an optimal path from xn. Let T be the next hypothesized slack time following t. In the following, we use the notation J 1, if s = d(i, k) for any k 1 {=d(ik)} = 0, otherwise For T = t +1,..., T let X,(i) = -t(i) + E=t[Z ( i)- + l{s=d(ik)}p(i, k)]forall i I1 {i|y(i) >_ 0}. For i ~ I let s(i) = inf{s > tIx'+(i) - x'Z() + 1{s=d(i,k)}p(i k) > 01. Let 12 = {is(i) < T, i Ii}. For i E I' let -= f Xt(j) -E z l{=d(i,k)}P(it), k) < (i) x'( ') (). r> (i This is possible by scaling ' such that (i) < I( ( - ( + 1i)=d(ik)}p(i, ) For all i not in I = I' U P. T < T. let,(i) = xt(i)- s=1 l{s=d(i,k)}p(ik). Then we have XT(i) < x(i) - -(i) for all i. Define XT+l(i) = X++(i) for all i e I' by scaling 7 until adequate resources are available for all i E Il. This is possible 1by the slackness hypothesis. We have defined a path from xt to XT+I such that xjr+1(i) = xTr+(i) for all i E I and XT+l(i) = X+l(i)-(i) for all i ( I. Next let J' = {jjt(j) = O.j q I}. Note that J1 includes all setup states (j > n) not in I. According to the slackness hypothesis, for all j < n and j C J1, we can increase production by -'(j), remain feasible and avoid earliness costs. Let xl(j) = 2

Xr+1(J) - (j) for all r > T, j < n, j E J1. For setup states (j > n), we have state constraints, 0 < XT(j) < 1, and dynamic constraints. A feasible perturbation of {x'(j)} for all j > n, j E J1, is obtained by defining xi+l(j) = X 1(j+)-7(j) for j > n, j E J1. For r > T + 2, j > n, j E J1, define recursively, 11(j) f max{4(j),x -()}, if '(j) - xr(j) > 0 r ) r-1 (j)+ (x(j) - (r-(j)) if 4z(j) - XI(j-0) <. For all j J1, r > T+1, let xa'(j) = x'(j). This defines a feasible path since x"(j) > x(j') xr+ri ) r(j) I +0(j) - rT(j) and z() = 4(j) whenever 4x'(j) > x'Z (j) -(j). 7+17 J j ) (j ) and T Then FT+l(xT,+l) < FT+l(X"T+i) since u(j) = 0 for j E J1. We now have ZT+1(i) = XZ+"(i) for all i E IU J1. Let J2 = {j j i IU J1,s(j) < o}, and let T = max{s(j)lj J2}. Define 1' x(i), i E I U J1,r =T+1,...,T (i) r(i)- E= {=d(i,k)}P(, k), i E J2,r, T...,(j)- j xI(i) - - 1 {=d(,k)}p(i k), i U J' U J 12T = T +1, 1 T T(,)i E J2, = S(j),... T Again, this path is feasible since it requires no processing beyond xt. For all r > t, j ~ IU J1 U J2, we have r r xr(j) = xt(j) - l{8=d(j,k)}P(j k) < xt(j) - j l{8=d(j,k)}P(j k). s=t+l s=t+l Let Tj = inf{rI E7 =t+ l =d(j,.)}p(j, k ) > (j) - ()} Let J3 = {j ~ I U J1U J2 IT < oo}, the set of channels with no Iprocessing under {x'} and with demand exceeding current inventory. Let T = min{T > TJlj e J3, all resources slack for j E J3}. Define X(i x) = 7(i), i Jr > T+ 1 x ( (i ) otherwise and ( 4''(i) i E I.U J1 U JUJ2,r >T x 4"(i), E 3 > T + 1 Xt(i)- -1 l{8,=d(i,)}p(i, k), i E J3, T..., T Xt(i) - -= l{8=d(i,k)}p(i k), i ~ IU J1 U J2 U J3, > T. 3

Note that FT+l( ) < F 1+(T+ I ) + E w(j)7(j). r>T+I,jE J3 Hence, w(j) must be zero for j J3 at state on an optimal path from In the remaining case, I=t+l l{S=d(j,k)}p(j, k) def Pj < xt(j - -Y(j) = t(j). Since we can scale down 7 arbitrarily (maintaining 7y: 0), we can choose -y(j) < Pj - (j) for any j such that Pj > xZ(j). For all such j, T) < oo. Hence, we can assume Xt(j) -Pj 6(j) > 0 for all j ~ I U J1 U J2 U J3 and some 6(j) > 0. We then have Xr(j) > 6(j) > 0 for all r > t and j ~ I U J1 U J2 U J3. Note that 0 < x7'(j) < X-r(j) + 7(j) < xt(j) for all >T, T IjUJ1U J2 UJ3. Then FT+l( 1) > FT+1( + r+ (j)u(j) = oo, implying that Xt V Xt for any y(j ) > 0 and xZ E Xt. Therefore, we have IU J1 U J2 U J3 = {1,2,...,2n} and Ft(xt) < Ft(x)+KI Ix-xtI1, for some K < (:1 max{wi,ui})(T-t). A similar argument is used if (c) holds by noting that only a finite number of costs are reduced in optimal paths from x' and xt. This again implies subdifferentiability. Condition (d) can be interpreted as a generalization of (c), in which a finite cost path is eventually obtainable from every feasible path at decreasing cost. Note that -t1 fr(Xr, x,+r+i f-(XT) has a finite number of terms, each with bounded slope, and is hence subdifferentiable. Hence, there exists pK and path {x4Z, xZ2,... 4K } such that TKh-I r t 3 fr(XrXr+I) + fTK(XTKXTK+1) -PXt r=t TK -1 < fr (X It 1' i (9) f fr(x. +l )+ fTK (XTK, X +lI)-pf P (9) Tr= for all x"' E Xt. Rewrite (9) as TK - 1 TK-1 Pt (xr -,xt) < fr.(xXr+ )- fr(X,, X+l)+ r=t r=t t 7I I,. fTK XTC I X f7k (X^ * +1) - TK(XTK, XTK+). (10) Note that IFt(xt)l < oc and IFt(.r')l < 0o. Hence pt has a limit point, Pt, and by (d) pI('- X) < F(x) - Ft(x),11) ~~~~~~~~~~~~~(ii) 4

for all xt E Xt. Hence, Ft is subdifferentiable at Xt. To show conclusion (ii), we must show that (pt-i,-P4) e aft-l(x- 1,*x), where p~ Fll~3, t-l1 *, -whe(xr)e pi e aFt-l (x*-1) and Pt* e Ft(x*). From (i), Ftl(zx_l) -p-lx*-l < Ftl(zt-1) - Pt-_lt-l for all xt-i. Hence, ft-i1(xt-n, xt) + Ft(z* -P *-l i* < ft-l(xt- l, t) + Ft(xt) - p*-xt-l, (12) for all (Zt-i,Xt). For gt(xtl,Xt) = ft-l(Xt-l,Xt) + Ft(xt), (12) implies that (p*-i,0) C gt(xz_l,,x). Note that ft-1 is polyhedral. Also, note that for any Xt E ri(Xt), the point (Zt,Xt) belongs to ri(dom Ft), where Ft(y,xt) = Ft(xt) when y E R2n. Hence, dom ft-l n ri(dom Ft) $A 0. The subgradients of gt are then the sums of subgradients of ft-1 and Ft (Theorem 23.8, Rockafellar [1970]), that is, (p-,, 0)-= (qt-i, qt) + (0,pt), (13) where (qt-l,qt) E aft-l(xtIxt) and (O,p*) E aFt(Xtl,X,), or, p E dFt(x*). This completes the result.1 Proof of Theorem 2: We want to show inf II( xx + )- (t,zti)II <. (14) ( zt,(t +1 )6zt Let x' have supporting prices p' as in (ii). Let vt(zt*) = (p - p)(xt - z). By summing inequalities (ii), for all T, 7' IT+IXI (15) pT+I(. r+- XT+1 )>- (fe(xt+l) —ft(xtX~t+l )) Po(XO —o (15) t=O and T I I IIX I PT+I (XT+ - X7+1) > (ft,(x,t+i) - ft(x, t+i )) -Po(Xo - Xo). (16) t=0 From the finiteness of F~(xO) and F~(x*), both right hand sides in (15) and (16) are uniformly bounded from below for all T. Hence, we know Vt(xt) > > -oo, (17) 5

for all t and xt. The subgradient set of ft at (x,xt*+l) is ft( t+)1 = () lvi = -Wi,xx(i) > 0, or vi = ui,xt(i) 0} (18) + N(dom ft; (xt, Xt'l)), where co denotes the convex hull and, for any convex set, S, and point, x, N(S;x) = {vIvT(y - x) < 0, Vy E S}, the normal cone to S at x and, for two sets A and B, A + B = {xlx = a + b, a E A, b E B}. Equation (18) follows from noting that the subgradient set of any proper, closed, convex function is the convex hull of all limits of neighboring gradients plus the normal cone to the effective domain of the function (Rockafellar, Theorem 25.6). We use (18) to show that Z = Zt =def {(zt,zt+i)lzt(i) = Aix*(i),A- >0, if x(i) 4 0,ui $ -wi;(Zt,zt+i) E domft}. (19) First consider any vector (zt, zt+l) E Zt. There exists some (p*, -pt+l)T E 9ft(t*, x +1) such that X* * t +P*, ft(xt, xt+ ) - pt Xt + Pt+ xt+- = ft(Zt, Zt+, )-Pt t+l Zt+l. (90) Let (p*,-p*l)T = (v,O)T + (71 i12)T as in (18) where (v,O)T is in the convex hull of neighboring gradients and (n, n2)7T is in the normal cone. Write (20) as ft, Zt+ ) = ft(x.1) + l( - x*) + n( - x) + nT(zt+l - x1). (21) Note that (zt, Zt,+) E dor,7 ft since (x;, x;+) E domn ft. Since A(nl, n2)T e N(dom ft;(x, jx+,)) for all A > 0, we have nT( z, - jx)+ 7T(zt+1 - - 1Xt) < 0. If nfT(Z -x)+n(zt+1 -xr*+) < 0. then f(z,^ +l) < f(x'.x+l ) + p(zt - x) - p*i(zt+l - x*+) for some (Pt -Pt+1) E afr(x, X+ ), violating convexity of ft. Hence, n7T(zt - x) + nT(zt+l - + 1 ) = 0. From the definition of f, (, t+ ) and equation (21), 2 n '( —',iZt(i)- -+ uizt(i)+) = ft(zt,Zt+l ) i=1 6

2n =ft(x;, Xt1) - + Vi(zt(i)- xW(i)) 2n 2n = >(-wit (i)- + uix (i)+)+ E vi(zt(i) - ~(i)) i=1 i=1 2n = >vizt(i), (22) i=1 where vi -- -wi, xt(i) < 0 vi -- Ui, xt(i) > 0 -ui < Vi < Ui x (i)o0. Therefore, we have o E o+ E o {ilzt(i)<O,x- (i)<o } {i|Zt(i)>o,Xt (i)>O} + E (tu,+ u)zt(i)+ > (ui+wi)(-zt(i)) (23) {ilZt (i)>0, '(i)<O} { ilzt(i)<o0, (i)>o } + > (U,-,,)zt(()+ > (Ui + Wi)(-Zt(i)). {ilzt (i)>0,rx ( i)=o0} {ilzt (i)<o,zt (i)=O} Every term in the sum in (23) must be zero since each has nonnegative components. Hence, Z; C Zt. Note also that if (t. t+l ) E Zt, then we can choose vi = ui if zt(i) > 0 and vi = -wi if Zt(O) < 0 for all i such that x(i) = 0. In this case, we have constructed (Pt -Pt+i) CE ft (x. '1+) to satisfy (20). This proves that Z* = Zt. Suppose (14) does not hold. Tlere exists e > 0 and a sequence of times, {tj} - oc such that inf x ( t, )-(,,zt+)1 > e. (24) (:tj.:, +1 )EZO'l Suppose there exists a subserqunce. {(x/ t 4ji )}, of the sequence, {(xt {,(xt.+l)}, such that lf IItJk - Xt II - 0 (25) t:,.:, +i}EZ ' Jk Jh Jk as t jkl - c. Then. for any b > 0. ttlere exists some t,zt,(z,z t1) E Z* such that \l\ - t 11' < 6 but liz - +,1il > e - 6 for all - such that (z~, z) is feasible. However, by construction of ft, for any x,. if xt = x + p for a perturbation vector, p, with IIpll < 6, 7

then, in the worst case, we have changed by p, the level of some channel i that bounds production for all outputs. In this case, for any xt+l, feasible from *t, there exists some xt+l, feasible from xt, such that llXt+l - xt+111 < 2njlp. In particular, this is true for t = t and x = x', hence, 2n6 > liz - xzt I > e- 6 for all 6. Hence, (24) and (25) are inconsistent. Therefore, if (24) holds, we must have some 6 > 0 such that inf IJx -ztj l > 6, (26) (:t ztj +i)EZ*tj t for all {tj}. Note that (19) implies that the set of Ztj E Ztj, for some feasible Ztj+l, defines a cone, C0., corresponding to the orthant that contains xZt (i) for ui f -Wi plus all coordinate directions, i. such that lx(i) = 0 or ui = -wi. Consider z4j defined by \(i) - ~ if i E A =def {jl'X(i) $ Ax.t(i) for any A > 0 and ui: -wi}:x^tj (i) otherwise. The vector x' - z* is then normal to C0 at zt so it achieves the infimum in (26). We then have iUf Ix, - -, Ix(i) >. (2s) (:t,.t, +)EZ tZj iEA () Note that (28) implies that tlere exists some i such that ui: -wi. Let v = min{u, + Wi, itl + wi ~ 0} > 0. WeV theil havet. for aly (p,, -Pt~+l) E Oft(xtp, tj+l), f (tj(I. ' t+ -I t4 ( - t, ) + t +l(x+ - Ztj+1) 2n = ~(-,',r,, (i) ~+i,,,(,) )+ 0 - v vixt(i) ~i= l( I t,= ) ) { 1],( )} (t9 ) ^= E (-,,*,,* (,)> + u,,x (i)+) + > (u + w,)|lx(.)I {'l7 =' (')} {iz'1 'xt (i)} >ft ( -,. -+1 +' >ftj (:,. z +l ) ~ I"l. By definition of Z*. for anIL (.r.j+ ) /ft(xt^ Xt+ ) — ptt +t~4lXt+l = ft(z,Zt+l) - PtZ p + Plzt (30) 8

From (29) and (30), we have for any T, T T Zft(xx i)) - Zft(xIx+i) ft(,Xt+l)- ft(, t=t+l) t=O t=O < (P; I -po)(!o - xo)- (PT -Pr )(x - )- T){jltj <T} VIIZ*,Z I /,, I.( 1 VI(tj t it +1) - (Xtj I xtlll (1 By (17), if (14) does not hold, then the right-hand side of (31) approaches -oo as T approaches oo since the normed term exceeds 6 infinitely often. This contradicts the finiteness of F~(x').l ~F~,~,,,, ~ TOf~ \ 9

REFERENCE Bean, J., J. Birge, J. Mittenthal, C. Noon [1986], "Matchup Scheduling with Multiple Resources, Release Dates and Disruptions," Technical Report 86-37, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109. 10