Page - 153 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 Here dxi = ai− x<i,r> is a residual for end conditions at the iteration r. Similarly, dx1i = ai− x<i,(r−1)> anddx2i= ai−x<i,(r−1)> are residualat iterations (r−1)and (r−2). Themainadvantage of thesealgorithmsoverclassicalgradientalgorithmsisasimplercalculationof thedirectionvector duringall iterations.However, this results inslowerconvergence (sometimes indivergence)of the general gradient (subgradient)methods as comparedwith classical ones. The convergence of all gradientmethodsdependsonthe initialapproximationψ(0)(T0). The analysis of the existingmethods of optimal programcontrol demonstrates that only the combineduseofdifferentmethodscompensatesfor theirdisadvantages. Therefore, thevectorψ(0)(T0) shouldbedeterminedintwophases ([36,37]). In thefirstphase, theMSOPCproblemisconsidered withoutstrict endconditionsat the time t=Tf. Thesolutionof theproblemwitha free rightend is someapproximation ψ˜(r)(T0) (r=1,2, . . . ). Then, in the secondphase, the receivedvector isusedas the initial approximation ˜˜ψ(0)(T0)= ψ˜(r)(T0) forNewton’smethod, thepenalty functionalmethod,or thegradientmethod. Thus, in the secondphase, theproblemofMSOPCconstructioncanbesolvedoverafinitenumberof iterations. Letusnowconsideroneof themosteffectivemethods,namelyKrylovandChernousko’smethod forOPCproblemwithafreerightend[39]. Step1.Aninitialsolution(anallowableprogramcontrol)ud(t),∀ t∈ (T0,Tf],ud(t)∈M isselected. Step2. ThemainsystemofEquation (1) is integratedunder theendconditionsh0(x(T0))≤ 0. This results in the trajectoryxd(t)∀t∈ (T0,Tf]. Step3. Theadjointsystem(2) is integratedover the timeinterval from t=Tf to t=T0 under the endconditions: ψ<i,d>(Tf)= 1 2 ∂ ( ai−x<i,d>(Tf) )2 ∂x<i,d> , i=1,. . . , n˜ (18) where theconstraints (18)are transversalityconditions for theoptimalcontrolproblemwitha freeend. The integrationresults in functionsψ<i,d>of timeandparticularly inψ<i,d>(T0). Step4. Thecontrolu(r)(t) is searchedforsubject to: H ( x(r)(t),u(r+1)(t),ψ(r)(t) ) = max→ u(r)∈M H ( x(r)(t),ψ(r)(t),u(r)(t) ) (19) where r=1,2, . . . isan iterationnumber.Aninitial solutionbelongs to the iteration r=0.Apart from themaximizationof theHamiltonian(19), themainandtheadjointsystemsofEquations (1)and(2) are integratedfrom t=T0 to t=Tf. Notably, several problemsofmathematical programmingare solved for each timepoint (the maximalnumberof theproblems isequal to thenumberofMSOPCmodels). Theseproblemsdefine componentsofHamilton’s function. This is theendof thefirst iteration(r=1). If theconditions∣∣∣J(r)ob − J(r−1)ob ∣∣∣≤ ε1 (20) ‖u(r)(t)−u(r−1)(t)‖≤ ε2 (21) aresatisfied,whereconstants ε1 and ε2 definethedegreeofaccuracy, thentheoptimalcontrolu∗(r)(t)= u(r)(t)andthevector ψ˜(r)(T0)arereceivedat thefirst iteration. Ifnot,werepeatStep3andsoon. Inageneralcase (whenthemodelM isused), the integrationstepfordifferentialEquations (1) and(2) is selectedaccordingto the feasibleaccuracyofapproximation(substitutionof initial equations forfinitedifferenceones)andaccordingtotherestrictionsrelatedwiththecorrectnessof themaximum principle. Ifwe linearize theMSmotionmodel (M<g,Θ>), thenall the componentsof themodelM (M<o,Θ>,M<k,Θ>,M<p,Θ>,M<n,Θ>,M<e,Θ>,M<c,Θ>,M<ν,Θ>)willbefinite-dimensional,non-stationary, lineardynamical systemsorbi-linearM<k,Θ>dynamicsystems. In this case, thesimplestofEuler’s formulascanbeusedfor integration. 153