Seite - 171 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 35 Thenthe totalentropyofallnodes includedinto thecut swillbedefinedas H(s)=∑uH(u)xu, (17) whereH(u) isdefinedin(15). Computationsofps(u, f)aswellas thesummationoverrisk factors f are takenin theriskevent protocols forall theevents related tonodesu fromTs. As faras entropyvaluesare found foreach node, thevulnerability torisksover thesupplychain ismeasuredasa totalentropyof the s-truncated supplychainsubject to therestricted losses. Definetheweightedentropyforeachcut sas H(Cs)= c(s)H∗(Cs) (18) where H∗(Cs)=− N ∑ j=1 pj(Cs) logpj(Cs) is theentropyofcutCs Weassumethat theweight c(s) satisfies the followingconditions: (i) c(s) isdecreasing; (ii) c(0)=L; (iii) lim s→∞c(s)=0. Definethe“variationof relativeentropy”dependinguponthecutnumber is REV(s)= H(s−1)− c(s−1)c(s) H(s) H(1)− c(s−1)c(s) H(s) . (19) Thefollowingclaimisvalid: Theorem. For theprocessofsequentiallycomputingof therelativeentropyvariation(REV), forany fixedvalue ε, thereexists the layernumbers* forwhich itholds: |REV(s∗)|< ε. Proof.Forsimplicity,weassumethat theentropyofany layerdependsonlyuponthe informationof theneighbor layers, that is, H∗(Ls|Ls+1,Ls+2, . . .Lk)=H∗(Ls|Ls+1), s=0,1,2, . . . ,k−1 Letusexploit the followingFormula for theentropyofcombinedsystem(see [21]): H(X1,X2, . . .Xs)=H(X1)+H(X2|X1)+H(X3|X1,X2)+ . . .+H(Xs|X1,X2, . . . ,Xs−1), Applying it for theentropyH∗(Cs)ofcutCs.Wehave H∗(Cs)=H∗(Ls,Ls−1,Ls−2, . . . ,L0)= =H∗(Ls)+H∗(Ls−1|Ls)+H∗(Ls−2|Ls−1,Ls)+ . . .+H∗(L0|L1,L2, . . .Ls)= =H∗(Ls)+H∗(Ls−1|Ls)+H∗(Ls−2|Ls−1)+ . . .+H∗(L0|L1) (20) Usingthe latterFormula forcutCs−1,weobtain H∗(Cs−1)=H∗(Ls−1)+H∗(Ls−2|Ls−1)+H∗(Ls−3|Ls−2)+ . . .+H∗(L0|L1) (21) 171