Page - 149 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 In this case, theMS jobshopschedulingproblemcanbe formulatedas the followingproblem ofOPC: it isnecessary tofindanallowable controlu(t), t∈ (T0,Tf ] that ensures for themodel (1) meetingofvectorconstraint functionsq(1)(x,u)=0,q(2)(x,u)≤0andguides thedynamicsystem (i.e.,MS job shop schedule) . x(t) = f(t,x(t),u(t)), from the initial state to the specifiedfinal state. If there are several allowable controls (schedules), then the best one (optimal) should be selected tomaximize (minimize) Jϑ. The formulatedmodel is a linear, non-stationary, finite-dimensional, controlleddifferential systemwith the convex area of admissible control. Note that the boundary problem isastandardOPCproblem([21,36,37]). Thismodel is linear in thestateandcontrolvariables, andtheobjective is linear. The transferofnon-linearity to theconstraintensuresconvexityandallows useof intervalconstraints. In thiscase, theadjoint systemcanbewrittenas follows: . ψl=− ∂H ∂xl + I1 ∑ α=1 λα(t) ∂q(1)α (x(t),u(t)) ∂xl + I2 ∑ β=1 ρβ(t) ∂q(2)β (x(t),u(t)) ∂xl (2) Thecoefficientsλα(t),ρβ(t) canbedeterminedthroughthe followingexpressions: ρβ(t)q (2) β (x(t),u(t))≡0, β∈{1,. . . , I2} (3) graduH(x(t),u(t),ψ(t))= I1 ∑ α=1 λα(t)graduq (1) α (x(t),u(t))+ I2 ∑ β=1 ρβ(t)graduq (2) β (x(t),u(t)) (4) Here,xl areelementsofageneral statevector,ψl areelementsofanadjointvector. Additional transversalityconditions for the twoendsof thestate trajectoryshouldbeaddedforageneral case: ψl(T0)=− ∂Job ∂xl ∣∣∣∣ xl(T0)=xl0 ,ψl(Tf)=− ∂Job ∂xl ∣∣∣∣ xl(Tf)=xlf (5) Letusconsider thealgorithmic realizationof themaximumprinciple. Inaccordancewith this principle, twosystemsofdifferential equationsshouldbesolved: themainsystem(1)andtheadjoint system(2). Thiswillprovide theoptimalprogramcontrolvectoru∗(t) (the indices«pl»areomitted) andthestate trajectoryx∗(t). Thevectoru∗(t)at time t=T0 under theconditionsh0 (x(T0))≤0and for thegivenvalueofψ(T0) shouldreturnthemaximumtotheHamilton’s function: H(x(t),u(t),ψ(t))=ΨTf(x,u,t) (6) Herewe assume that general functional ofMS schedule quality is transformed toMayer’s form[21]. The received control is used in the rightmembersof (1), (2), and thefirst integration step for themainand for theadjoint systemismade: t1 =T0 + δ˜ (δ˜ is a stepof integration). Theprocessof integration is continueduntil theendconditionsh1 ( x(Tf) ) ≤ → Oare satisfiedandtheconvergence accuracy for the functionalandfor thealternatives isadequate. This terminates theconstructionof the optimalprogramcontrolu∗(t)andof thecorrespondingstate trajectoryx∗(t). However, the only question that is not addressedwithin the described procedure is how to determineψ(T0) foragivenstatevectorx(T0). Thevalueofψ(T0)dependsontheendconditionsof theMSscheduleproblem.Therefore, the maximumprinciple allows the transformationof aproblemofnon-classical calculusofvariations toaboundaryproblem. Inotherwords, theproblemofMSOPC(inotherwords, theMSschedule) construction is reducedto the followingproblemof transcendentalequationssolving: Φ=Φ(ψ(T0))=0 (7) 149