Seite - 154 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 The advantage of themethod is its simple programming. Krylov-Chernousko’smethod is less dependent on the initial allowable control, as comparedwith the above-mentionedmethods. Inaddition, control inputsmaybediscontinuous functions. This isnoteworthyasmostMSresources areallocated inarelaymode. However, thesimplesuccessiveapproximationsmethod(SSAM)candiverge. Several modifications of SSAM were proposed to ensure convergence and the monotony of some SSAM modifications was proved in [40] for two-point linear boundary problems with aconvexareaofallowablecontrolsandconvexgoal function. LetusconsideronevariantofSSAM convergence improvement. In thiscase,Equation(22) isappliedoversomepartσ′=(t′, t′′]of the intervalσ=(T0,Tf], andnot over thewhole interval, i.e., u(r+1)(t)= ˜˜N(u(r)(t)), t∈ (t′,t′′];u(r+1)(t)=u(r)(t), t /∈ (t′,t′′] (22) wheretheoperator ˜˜Nproduces[seeformula(19)]anewapproximationofasolutionforeachallowable controlu(t). The interval (t′, t′′] is selectedasapartof (T0,Tf], inorder tomeet thecondition: J(r+1)ob < J (r) ob where J(r+1)ob , J (r) ob are thevaluesof thequality functional for thecontrolsu(r+1)(t),u(r)(t), respectively. Theselectionof timepoints t′and t′′ isperformedinaccordancewithproblemspecificity. Inour case, thesetofpossiblepoints (t˜′<e,(r+1)>, t˜ ′′ <e,(r+1)>), e=1, . . . , Er for the iteration (r+1) is formed during iteration rduring themaximizationofHamiltonian function (19). Theset includes the time pointsatwhich theoperationsofmodelMare interrupted. This idea for interval (t′, t′′]determination wasusedinacombinedmethodandalgorithmofMSOPCconstruction. Themethodandthealgorithm arebasedon jointuseof theSSAMandthe“branchandbounds”methods. 4.CombinedMethodandAlgorithmforShort-TermSchedulinginMSs Thebasic technical ideaof thepresentedapproachonthebasisofpreviousworks ([13,19,33,34,41]) is thecombinationofoptimalcontrolandmathematicalprogramming.Optimalcontrol isnotusedfor solvingthecombinatorialproblem,but toenhance theexistingmathematicalprogrammingalgorithms regardingnon-stationarity,flowcontrol, andcontinuousmaterialflows.Asthecontrolvariablesare presentedasbinaryvariables, itmightbepossible to incorporate theminto theassignmentproblem. Weapplymethodsofdiscreteoptimizationtocombinatorial taskswithincertain timeintervalsanduse theoptimalprogramcontrolwithall itsadvantages (i.e., accuracyofcontinuoustime, integrationof planningandcontrol, andtheoperationexecutionparametersas timefunctions) for theflowcontrol within theoperationsandfor interlinkingthedecomposedsolutions. Thebasiccomputational ideaofthisapproachis thatoperationexecutionandmachineavailability are dynamically distributed in time over the planning horizon. As such, not all operations and machinesare involvedindecision-makingat thesametime. Therefore, itbecomesnatural to transit fromlarge-sizeallocationmatriceswithahighnumberofbinaryvariables toaschedulingproblem that is dynamically decomposed. The solution at each time point for a small dimensionality is calculatedwithmathematicalprogramming.Optimalcontrol isusedformodelingtheexecutionof theoperationsandinterlinkingthemathematicalprogrammingsolutionsover theplanninghorizon with thehelpof themaximumprinciple. Themaximumprincipleprovides thenecessaryconditions suchthat theoptimalsolutionsof the instantaneousproblemsgiveanoptimalsolutionto theoverall problem([21,27,42]). Wedescribe theproposedmethodandalgorithmfor twoclassesofmodelsbelow: • modelsM<o>ofoperationprogramcontrol; 154