Seite - 150 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 At this stage,weconsider themostcomplicatedformof theMSOPCconstructionwithMSinitial stateat time t=T0. Theendpointof the trajectoryandthe timeintervalarefixed: x(Tf)=a (8) where a=||a1,a2, . . . ,an˜||T is agivenvector; n˜ is thedimensionalityof thegeneralMSstatevector. Hence, the problemof optimalMSOPCconstruction is reduced to a search for the vectorψ(T0), suchthat: Φ=Φ(ψ(T0))=x(Tf)−a (9) TheproblemofsolvingEquations (9) isequivalent toaminimizationof the function: Δu(ψ(T0))= 1 2 ( a−x(Tf) )T( a−x(Tf) ) (10) Themain feature of theproblems (9), (10) is that the interdependencyofψ(T0) andρ(Tf) =( a−x(Tf) ) isdefinedindirectlyvia thesystemofdifferentialEquation(1). This feature leads to the useof iterativemethods. 3.ClassificationandAnalysesofOptimalControlComputationalAlgorithmsforShort-Term SchedulinginMSs Real-worldoptimalcontrolproblemsarecharacterizedbyhighdimensionality, complexcontrol constraints, andessentialnon-linearity. Prior to introducingparticular algorithmsandmethodsof optimalcontrol computation, letusconsider theirgeneral classification(Figure2). Twomaingroupsaredistinguished: thegroupofgeneraloptimalcontrolalgorithmsandmethods and the group of specialized algorithms. The first group includes direct and indirect methods and algorithms. Thedirectmethods imply searchprocesses in spaces of variables. Thefirst and mostwidelyusedmethodsof thisgroupare themethodsof reduction tofinite-dimensional choice problems.Anothersubgroupincludesdirectgradientmethodsofsearchinfunctionalspacesofcontrol. Toimplementcomplexconstraints forcontrolandstatevariables, themethodsofpenaltyfunctionsand ofgradientprojectionweredeveloped.ThethirdsubgrouprepresentsmethodsbasedonBellman’s optimalityprincipleandmethodsofvariation instatespaces. Themethodsof thissubgrouphelpto considervariousstateconstraints. Unlike themethods of thefirst group, the indirectmethods andalgorithms are aimedat the acquisition of controls that obey the necessary or/and sufficient optimality conditions. Firstly, themethodsandalgorithmsfor two-pointboundaryproblemscanbereferenced. Particularmethods are used here: Newton’smethod (and itsmodifications), Krylov andChernousko’smethods of successiveapproximations,andthemethodsofperturbationtheory. Methodsbasedonsufficientconditionsofoptimalityarepreferable for irregularproblemssuchas optimalzero-overshootresponsechoice. Thethirdgroupincludesspecializedmethodsandalgorithms for linearoptimalcontrolproblemsandapproximateanalyticalmethodsandalgorithms. The latter methods imply that thenonlinearcomponentsofmodelsarenotessential. Letus limit adetailedanalysisof computationalprocedures to two-pointboundaryproblems withfixedendsof the state trajectory x(t) andafixed time interval (T0,Tf ]. For this systemclass, thefollowingmethodscanbeconsidered([23,24,33]):Newton’smethodanditsmodifications,methods ofpenalty functionals,gradientmethods,andtheKrylov–Chernouskomethod. Let us consider the possible implementation of the above-mentioned methods to the statedproblem. 150