Seite - 152 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 whereγr (0≤γr≤1) is selectedtomeet theconstraint: Δu ( ψ(r)(T0) ) <ΔH ( ψ(r−1)(T0) ) (14) First, thevalueγ(r) =1 is tried. Thenvalues1/2,1/4,andsoonuntil (14) is true. Theselectionof γ(r) isbeingperformedduringall iterations. Theentiresolvingprocess is terminatedwhenΔu ( ψ(r)(T0) ) < εu,where∑u isagivenaccuracy. ThemainadvantagesofNewton’smethodanditsmodificationsareasimplerealization[there isnoneedto integrateadjoint system(2)], a fast convergence (if the initial choiceofψ(T0) isgood), andahighaccuracysolution. Themaindisadvantageisthedependencyofaconvergenceuponthechoiceofψ(T0). Intheworst case (absenceofagoodheuristicplanofMSoperation), thesemethodscanbedivergent. Inaddition, if the dimensionality of the vectorρ(Tf) is high, then computational difficulties can arise during calculationaswellasan inversionofmatrices (12). Themethodofpenalty functionals. Touse thismethodfor theconsideredtwo-pointboundary problem,weshoulddetermine theextendedquality functional: J˜ob.p= Job+ 1 2 n˜ ∑ i=1 Ci ( ai−xi(Tf) )2 (15) whereCi arepositive coefficients. If the coefficients are sufficiently large, theminimalvalueof the functional is received in the case ofρi(Tf) = 0. Therefore, the followingalgorithmcanbeused for the solvingof theboundaryproblem. The control programu(r)(t) is searchedduringall iterations withfixedCi (Newton’smethodcanbeusedhere, forexample). If theaccuracyofendconditions is insufficient, thenthelargervaluesofCiaretried.Otherwise, thealgorithmisterminatedandasolution is received. Although themethodseemsdeceptively simple, it doesnotprovideanexact solution. Therefore, it isadvisable tocombine itwithothermethods. Thegradientmethods. Therearedifferentvariantsof thegradientmethods includinggeneralized gradient (subgradient)methods.Allgradientmethodsuse the followingrecurrence formula: ψ(r)(T0)=ψ(r−1)(T0)+γ(r)Δ(r−1) (16) Here r=1,2,3, . . . isan iterationnumber;Δ(r−1) isavectordefiningadirectionofashift from thepointψ(r−1)(T0). Forexample, thegradientof the functionΔu canbeused: Δ(r−1) =gradΔu ( ψ(r−1)(T0) ) =‖ ∂Δu ∂ψ<1,(r−1)> , . . . , ∂Δu ∂ψ<n˜,(r−1)> ‖ T Themultiplierγ(r) determines thevalueof the shift indirectionofΔ(r−1). In the subgradient, methodsvectorsΔ(r−1) in (16)aresomesubgradientsof the functionΔu. In theMSOPCproblems,a feasiblesubgradientcanbeexpressedas: Δ<i,(r−1)>= ai−x<i,(r−1)>(Tf) Then, themainrecurrence formulacanbewrittenas: ψ<i,(r)>(T0)=ψ<i,(r−n)>(T0)+γ<i,r> ( ai−x<i,r>(Tf) ) (17) whereγ<i,r> canbeselectedaccordingtosomerule, forexample: γ<i,r>= { 1 2γ<i,(r−1)>, if signdxi = signdx1i = signdx2i; γ<i,(r−1)>, ifnot, 152