Page - 156 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 Thebranchingof theproblemГoccursduring theprocessofHamiltonianmaximizationat some time t˜∈ (T0,Tf] if theoperationD(i)æ isbeing interruptedbythepriorityoperationD(ω)ξ . In thiscase, theproblemГ is split into twosub-problems(P(i)æ ,P (ω) ξ ). Within theproblemP(i)æ , theoperationD (i) æ isexecutedinaninterrupt-disablemode. Forother operations, this restriction is removedandtherelaxedschedulingproblemissolvedvia themethodof successiveapproximations. Letusdenote thereceivedvalueof thegoal function(23)by J(1)p0 .Within the problemP(ω)ξ , the previously started operationD (i) æ is terminated, andD (ω) ξ begins at time t˜. TheresourcesreleasedbytheoperationD(i)æ andnotseizedbyD (ω) ξ canbeusedforotheroperations if anyarepresent. Reallocationof resourcesshouldbeperformedaccordingto (19). Subsequently,after completionofoperationD(ω)ξ , therelaxedschedulingproblemissolved. In thiscase, thevalueof the goal function (23) isdenotedby J(1)p1 . Therecord Jp isupdated if J (1) p0 < Jpor/and J (1) p1 < J (1) p [weassume that the functional (23) isminimized]. If only J(1)p0 < J (1) p , then Jp = J (1) p0 . Similarly, if only J (1) p1 < J (1) p , then Jp = J (1) p1 . If both inequalities are true, then Jp =min{J (1) p0 , J (1) p1 }. In the latter case, the conflict resolution isperformedas follows: if J(1)p0 < J (1) p1 , thenduringthemaximizationof (19)D (i) æ isexecuted inan interrupt-disablemode.Otherwise, theoperationD(i)æ isentered into theHamiltonianatpriority D(ω)ξ atarrival time t˜. Afterconflictresolution, theallocationofresources iscontinued,complyingwith(19)andwithout interruptionofoperationsuntil anewcontention is similarlyexamined. Theconsideredvariantof dichotomousdivision inconflict resolutioncanbeextendedto thecaseofk-adicbranching,wherek is thenumberof interruptedoperationsat sometime t. The iterative process of the optimal schedule search is terminated under the following circumstances: either the allowable solution of the problem Г is determined during the solving ofarelaxedproblemorat the fourthstepof thealgorithmafter the integrationwereceive:∣∣∣J(r+1)p − J(r)p ∣∣∣< ε1 (24) where ε1 is a given value, r= 0, 1, . . . If the condition (24) is not satisfied, then the third step is repeated,etc. Thedevelopedalgorithmissimilar to thoseconsidered in [20,37].Here, thesetof timepoints in which theHamiltonian is tobemaximized is formedontheprevious iteration. Thesearepointsof operations interruption.Computational investigationsof theproposedalgorithmshowedthat therate ofconvergence ispredominantly influencedbythechoiceof the initialadjointvectorψ(t0). In its turn, ψ(t0)dependsonthefirstallowablecontrol that isproducedat thefirst step.Duringthescheduling process, themachinesareprimarilyassignedtooperationsofhighdynamicpriority. To illustrate themain ideasof thealgorithm, letusconsiderasimpleexampleofascheduling problemwith two jobs, three operations, and a singlemachine, (T0,Tf] = (0, 14], a (o) iæ = 2 (I=1,2; æ=1,2,3);Θiæj(t)=1∀ t; ε11(t)=1at t∈ (0, 14], ε21(t)=0 for0≤ t<1, ε21(t)=1 for t≥1. In thiscase, themodelcanbedescribedas follows: M= {→ u ∣∣∣ .x(o)iæ = εi1u(o)iæ1; .z(o,1)iæ1 =u(o)iæ1;.z(o,2)iæ1 = z(o,1)iæ1 ; . z(o,3)iæ1 =w (o) iæ1;u (o) iæ1(t),w (o) iæ (t)∈{0,1}, 3 ∑ æ=1 2 ∑ i=1 u(o)iæ1(t)≤1;u(o)i21 ( a(o)i1 −x(o)i1 ) =0;u(o)i31 ( a(o)i2 −x(o)i2 ) =0; w(o)iæ1 ( a(o)iæ −z(o,1)iæ ) =0;T0=0 : x (o) iæ (t0)= z (o,1) iæ1 (t0)= z (o,2) iæ1 (t0)= z (o,3) iæ1 (t0)=0;Tf =14 : x (o) iæ (tf)=2; z(o,l)iæ1 (tf)∈R1, l=1,2,3 } . (25) Theschedulingqualitymeasure isdefinedbytheexpression: 156