Page - 155 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 • modelsM<ν>ofauxiliaryoperationsprogramcontrol. Thesemodelsweredescribed in [13,19,33–38].Alongwith the initialproblemofprogramcontrol (marked by the symbolГ), we consider a relaxed one (marked by P). The latter problemhas no constraintsof interruptiondisabilityoperationsD(i)æ (whereD (i) æ isanoperationæwithobject i. See, forexample, [36,37]). Let thegoal functionofproblemГbe: Jp= ⎧⎨⎩Job+ n∑i=1 si ∑ æ=1 m ∑ j=1 l ∑ λ=1 [ z(o,1)iæjλz (o,3) iæjλ+ (aiæ) 2 2 −z(o,2)iæjλ ]2( z(o,1)iæjλ )2⎫⎬⎭ ∣∣∣∣∣∣ t=Tf (23) where the auxiliary variables z(o,1)iæjλ(t), z (o,2) iæjλ(t), z (o,3) iæjλ(t) are used for operationswith interruption prohibition. More detailed information about these auxiliary variables and themethods of their utilizationcanbefoundin[20]. The following theorem expresses the characteristics of the relaxed problem of MS OPCconstruction. Theorem1.LetPbea relaxedproblemfor theproblemГ.Then (a) If theproblemPdoesnothaveallowable solutions, then this is true for theproblemГaswell. (b) Theminimalvalueof thegoal function in theproblemPisnotgreater than theone in theproblemГ. (c) If theoptimalprogramcontrolof theproblemPisallowable for theproblemГ, then it is theoptimalsolution for theproblemГaswell. Theproofof the theoremfollowsfromsimpleconsiderations. Proof. (a) If theproblemPdoesnothaveallowable solutions, thena controlu(t) transferringdynamic system(1) fromagiveninitial statex(T0) toagivenfinalstatex(Tf)doesnotexist. Thesameend conditionsareviolated in theproblemГ. (b) It canbeseen that thedifferencebetween the functional Jp in (23)andthe functional Job in the problemPisequal to lossescausedbyinterruptionofoperationexecution. (c) Letu∗p(t), ∀ t∈ (T0, Tf] be anMS optimal program control in P and an allowable program control inГ; letx∗p(t)beasolutionofdifferential equationsof themodelsM<o>,M<ν> subject tou(t)=u∗p(t). If so, thenu∗p(t)meets therequirementsof the local sectionmethod(maximizes Hamilton’s function) for theproblemГ. In thiscase, thevectorsu∗p(t),x∗p(t) return theminimum tothe functional (1). Theschemeofcomputationcanbestatedas follows. Step 1. An initial solutionug(t), t∈ (T0,Tf] (an arbitrary allowable control, in otherwords, allowableschedule) is selected. Thevariantug(t)≡0 isalsopossible. Step2. ThemainsystemofEquation (1) is integratedsubject toh0(x(T0))≤ 0andu(t)=ug(t). Thevectorx(o)(t) is receivedasa result. Inaddition, if t=Tf, then the recordvalue Jp= J (o) p canbe calculated,andthe transversalityconditions (5)areevaluated. Step3. Theadjoint system(2) is integratedsubject tou(t)=ug(t)and(5)over the interval from t=Tf to t=T0. For time t=T0, the first approximationψ (o) i (T0) is received as a result. Here the iterationnumber r=0iscompleted. Step4. Fromthepoint t=T0 onwards, thecontrolu(r+1)(t) isdetermined(r=0,1, 2, . . . is the numberof iteration) throughtheconditions (19). Inparallelwith themaximizationof theHamiltonian, themainsystemofequationsandtheadjointsystemare integrated. Themaximization involves the solvingofseveralmathematicalprogrammingproblemsateachtimepoint. 155