Page - 173 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 35 Therefore, foranyaccuracy levelε,wecanselect thenumberofacut s1 forwhich H(s1−1)−H(s1) H(0)−H(s1) < ε Thetruncatedpartof theSCcontainingonly layersof thecut (s1−1)possesses therequiredlevel of theentropyvariation. Thetheoremisproved. Thetheorempermits thedecisionmaker todefinethedecreasedsizeof theSCmodel, suchthat thedecreasednumberof the layers in theSCmodel is sufficient forplanningandcoordinating the knowledgeabout therisks in therelationsbetweentheSCcomponents,without the lossofessential informationabout therisks. 4. Entropy-BasedAlgorithmforComplexityAssessment Thissectionsummarizes theoreticalfindingsof theprevioussections forobtainingadecreased SC model on which planning and coordination of supplies can be done without loss of essential information. Inputdataof thealgorithm: • thegivennumberNofriskdrivers, • weight functions c(s) selectedbythedecisionmaker, • probabilities pfprime(s) = Pr (Af prime(s)) that the riskdriver f is thedirect source of the supply failure/delay in layer s,whicharecausedbyriskdriver f, • probabilities pfsecond(s) = Pr (Af second(s)) that the risk driver f is the source of the supply failure/delay in layer s, which is a result of the indirect effect on the f by the risk drivers f ′ ofsupplydelay in layer s+1; theseprobabilitiesare termedas secondary. • transitionprobabilitymatricesM(2)(s)= ( p(2)ij (s) ) N×N , s=0,1,2, . . . ,k. Step1.UsingtheentropyFormulas (11)–(17), calculateentropyof the layer0: H∗(L0)=− N ∑ j=1 pj(0) log ( pj(0) ) H(0)=H∗(L0) Step2.UsingFormulas (2)–(9), compute thematrix Mˆ(1)(0), andvectorp(1)=(p1(1),p2(1), . . .pN(1)) Step3.Compute thecorrectedvectorofprobabilities for the layerL0,usingFormula pc(0)=p(1) ·Mˆ(1)(0)andcorrectedentropyfor layerL0 HC∗(L0)=− N ∑ j=1 pcj(0) log ( pcj(0) ) Step 4. For s=2,3, . . . , usingmatrix Mˆ(1)(s), vector p(s) = (p1(s),p2(s), . . .pN(s)) compute sequentially thecorrectedvectorsofprobabilities for the layersLs−1: pc(s−1)=p(s) ·Mˆ(1)(s−1) Step5.ComputeHC∗(Ls−1)=− N ∑ j=1 pcj(s−1) log ( pcj(s−1) ) Step6.Compute H(0)−H(1)= = ( 1− c(1)c(0) ) H(0)−c(1)(H∗(L1)−HC∗(L0))+c(1) N ∑ i=1 ( pi(1) · N ∑ j=1 pˆ(1)ij (0) · log ( pˆ(1)ij (0) )) 173