Seite - 156 - in Algorithms for Scheduling Problems
Bild der Seite - 156 -
Text der Seite - 156 -
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
zurück zum
Buch Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Titel
- Algorithms for Scheduling Problems
- Autoren
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Herausgeber
- MDPI
- Ort
- Basel
- Datum
- 2018
- Sprache
- englisch
- Lizenz
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Abmessungen
- 17.0 x 24.4 cm
- Seiten
- 212
- Schlagwörter
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Kategorien
- Informatik
- Technik