C O N C E R N I N G THE PROBLEM OF OPTIMAL D I S T R I B U T I O N OF A TIME R E S O U R C E

V. F. Bilyuba

UDC 519.2

1. Several papers on queueing theory ( [ 1 ] , etc.) apply to the case when the flow of requests entering a system with one server is stipulated by means o f probabilistic laws. In contrast to this, [ 2 ] - [ 5 ] considered systems in which the incoming flow o f requests at each instant o f system functioning is determined in advance on a finite time interval by means o f a fixed sequence o f time intervals [~,, [k], where tk, /~ are predicted or assigned times of arrival or departure of the k-th request from the system. The presence of requests in the system at each time during the sojourn time intervals allowed future (relative to the indicated time) analysis of problems in optimal operational planning o f servicing, including problems o f time-resource distribution [2], [3], [5]-[7]. Note problems in systems are after which Under these

that in the review [8] the closeness of the statements of problems studied in queueing theory to scheduling theory was indicated, as well as the fact that predominantly deterministic queueing associated with scheduling theory. A number o f scheduling-theory problems in which the time t k penalization o f servicing occurs is assumed known for each request was analyzed in [ 8 ] - [ 1 0 ] , etc. conditions the servicing duration for each request was usually assumed stipulated.

Let us refine the statement o f the problem considered. In a queueing system with one server assume that at time t o the time intervals It> [h!, where /h>_t~>/t,.,/e-----l,..., M , are stipulated for a fixed number M o f requests from the incoming flow. Servicing o f one request by the server is governed by the deterministic law f ( r ) if its duration r is a deterministic variable quantity, 0 < r < oo, while the servicing quality is estimated by the f u n c t i o n f i r ) . The problem of finding the optimal scheduling o f single servicing o f the indicated requests by the server can be reduced to an optimal distribution T ~ = ( , ~ , . . . , T ~ . . . . , *i~,) o f the time resource for a fixed servicing sequence (1, ..., k, ..., M) in the form of the following separable-programming problem. On the set G o f vectors

T=(x~, ...,~k ..... ~,vz)' defined by the relationships ,M

--Yk=J'ch= ?,~1- - q, S~'~ &+l - - _ tl ~ -~=l"rz

4

[/~ - -

tl,

(1.1)

k ~ 1, M - - I ,

(1.2)

% > / r , /e :~ 1, M,

(1.3)

t~ 4 t~+i, 7~ 4 [~+1, t;~+l < [h, k = 1, M - - l ,

(1.4)

it is required to find the optimal vector T O from the condition (1.5)

F (T ~ = min F (T), T,:7_G

where the criterion governing the efficiency of time-resource distribution has the form: S "?'1 t" F ( T ) - - --,'~,=!~,h/('t'h)

Ct is the weighting coefficient o f the priority o f the k-th request; C k > 0; planned servicing duration (7. /> 0). F o r monotonic convex functions f(fk), 7" = 0 and but only for a nondegenerate optimal solution T o > 0, determination o f the exact solution of this problem in a dimensionality M. The p r o o f o f the method is based on

(1.6)

;

L is the lower bound of the

equal C k (in [ 2 ] - [ 3 ] , or for arbitrary Ck in [5]), the method of b~, u-cuts is proposed for the efficient finite number o f steps that does not exceed the the corresponding necessary optimality conditions.

Translated from Kibemetika, No. 5, pp. 106-110, September-October, 1974. January 26, 1973.

Original article submitted

9 76 Plenum Publishing Corporation, 227 West 17th Street, New York, N. I1. 10011. No part o f this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without w~tten permission o f the publisher. A copy o f this article is available from the publisher for $]5.00.

864

The present problem ( 1 . 1 ) - ( 1 . 6 ) solution T O which allowed solution o f the case r /> 0.

paper studies: 1) the generalized necessary optimality conditions for the vector T O of the in the case which allows nonconvexity o f the function f0"k) for any Ck and an optimal allows degeneracy o f the solution for r_ = 0; 2) the conditions for the existence o f an the problem ( 1 . 1 ) - ( 1 . 6 ) for ~_ >t- 0, and 3) a method o f determining the solution T o for

2. The necessary conditions for optimality of the vector T o o f the problem ( 1 . 1 ) - ( 1 . 6 ) for an arbitrary function f(rk) are established by the following theorem. THEOREM 1. 0)~ = & + ~ o .

Let the function

f(r) E CEo,~), the weighting coefficients

be arbitrary, r_ = 0, and

Then the optimal vector T o is constrained to satisfy the following requirements:

1

a)

C k

if o)~=t~+~

I)

for the condition that

1) x ~ + l > 0 , kE{1 . . . . . M - - l } ,

then

Cd' (T~)> Ck+d" (~+,): 2) rT=OwhileT~ kc{1 . . . . . M _ 2 I , tE{2 . . . . . M--k},

for the condition that iE{k + 1. . . . . k + l - - l},

(2;. 1)

it follows that 0 C,.,_~,fp (T~+.) ~< rain {CJ' (0). Cff' (~)};

b)

(2.2)

if ~oi~=ihfor the condition that l) z~i.'>O, k E{1 . . . . . M - - l } .

it follows that

C j ' (rT) 4 C,_ lf' t r;<+ ~ ~); for the condition that it follows that

2~

r~=O,

~~

pE{1 . . . . .

k--l}, iE{k--~;+l

.....

(2.3)

k},

0 C~_fle (~e - - p) ~< rain {CJ' 10), C~+,It (%,+,)}:

c) if t_k+~
h for the condition that

1) %~ 0, -co,,+~> 0 , kE{1, . . . , M - - l } ,

. , (%)= o C~,f for the condition that it follows that

(7:.4)

C ,~+,f'

(2.5)

(~ i) ; ~,~

23 r f'~,__ > (J, T'~= , 0. ~+~>0, pE{0, l .... , k - - l } ,

/E l l . . . . . . 4~, - - k}, i E {k--p + 1. . . . . # + !"1}.

(2.6)

C,i' (01 >~ C ,<_J' C~_o) = C ~ + f (~+~).

Proof

Case

a)

-

the first case.

Assume that for some

k

= j

the inequality (2.1) is not fulfilled

C j ' ( 0 < C,+d' !t','_L,) for o~7:=ts+~ and

~'2+1> 0.

Let us consider the vector I 1: ok

for for

,or

i.e.,

(2.7)

T' = (TI. . . . .

"c~= /~'-~-&~

-

T~), where

k=/=,: , / + 1 , k=/, 1.

(2.8)

0 < &~ < rain {ti - - tj+. ~'i'+~b Then, checking condition ( 1 . 1 ) - ( 1 . 3 ) for the vector T', it can easily be seen that T' is allowed. Moreover, having made use o f Eq. (1.6), the property of the function f(~)EC~0.=) , and the Lagrange form for the additional term in the Taylor expansions for the function f ( r j ) at the point r ~ and the function

865

f(r]+ 1) at the point r~ allowed variable T':

we obtain the following expression for the increment o f the objective function for any

AF = F (T')--

F f T '~) = 1C y

o

., o /

+ i c y ('d/+ (!~6-c~T'-,,-.., r f"(d4-,--GS-c)l ( _ ~ 0<.[01<1 ,

(2.9)

0
From ( 2 . 9 ) i t follows that for a fairly small variation 8r and also for fulfillment of the inequality (2.7) it follows that A F < 0 ; this contradicts the optimality of the vector T o and completes the proof. Case a) -

the second

case.

Let us choose the allowed variable vector

T" = (~7. . . . .

"c;~) in the following

manner: I

0

.... , - i ,

,o,

9 ! i , 8w~ "c#= "i'6 h

i+,+1

.....

,,.

for k = l, for k =.i + 1. . . . . / + / - - 1.

! v _ , - - 6 x ~'*z for ~ = i + l.

where the index j is fixed from the set {1, ..., M - 2 } in such a way that the conditions of the second case a are satisfied for k = j. The variation is chosen to be arbitrary from the condition I ) < 6Ti+, < < r.in { t r - 9 + ) . 90r+z}, while the variations 6ri(i = j, j + 1, ..., j + l - 1) are chosen to be in the domain of /-dimensional Euclidian space defined by the relationships i4-l--1

6~ >/0,

Z 6h = 6z~+,..

(2.10)

Then the conditions ( 1 . 1 ) - ( 1 . 3 ) for the vector T are fulfilled - i.e., T" E G. i=j .....

6%=,~.6~:+,

Representing 8r i in the form

J-4-t--1,

by means o f the auxiliary variations ~i, we arrive from (2.10) at the constraints ~>/@ and ~

~i=l,

which define the set o f variations in the space o f the vectors @,. . . . . (6~; . . . . . 8~/+t) fills the simplex in /-dimensional space. 2 f(~)E C~0.~>, we transform A F to the form

(2.12)

~f--i-0.

The set o f allowed variations

With allowance for (1.6), (2.11) and the property

/§

}

ct 0 AF = ~C,.f' ('~) ~i ~ ~~,.C~I ( 0 ) - G+/ P (h+~) x

i=H-t

(2.13)

X &,+r + o (6~i+z). Since the variation 8.ri may be chosen to be arbitrarily small, it follows that from (2.13) the validity of the following necessary optimality conditions for the vector T o is demonstrated by the indirect-proof method: i,+l--I

~.C/' ('0 4- ~ g~C~ ' (0) > C._:_j' (-if+:)

(2.14)

i=i-',- i

for

/C {1 . . . . .

M--2}

and any vectors S = (~," . . . . ~;+~_~) on the bounds (2.12) of the corresponding simplex.

Then successively setting the vector S equal to all possible unit vectors (0 . . . . , 1, ..., 0) of dimensionality l for j = k, we obtain the desired necessary condition (2.2). Case b) is proved analogously. The p r o o f of case c) differs from the proofs of cases a) and b) only in that two sets o f allowed variations, rather than one, are constructed in the form of simplexes analogous to the one constructed above. Under these conditions the first type of variation corresponds to a shift of the point oo~ for the variable vector T' to the left relative to the point co~ while for the second type o f variation the shift is correspondingly to the right. Remark 1.

Since the optimal vector T O must necessarily satisfy the condition t_k+l~< o~ 4 l~

in the first

k components by virtue o f (1.2), it follows that the conditions a ) - c ) enumerated in the theorem form a complete system ( 2 . 1 ) - ( 2 . 6 ) o f necessary optimality conditions for the vector T o .

866

Remark 2.

F o r the more general case in which the objective function of the distribution efficiency of M

the time resource has the form

F (T) = ~ f~ ('%), where

2

t~ (x~)~ C~0.~l, the theory remains in force.

Under

these conditions the formulation and p r o o f may be constructed with Ckf(rk) being replaced by fk(rk). 3. Let us consider the nonlinear-programming problem (1.1)-(1.6) for the case of an arbitrary constraint r_ t> 0. Unlike the case r = 0, when the set G of allowed vectors T ~ G is nonempty by virtue o f (1.6), 'we study the problem o f the existence of an allowed solution T ~ G for r_ ~> 0. Statement. tM

For the existence o f a vector T E G for L ~> 0 it is necessary that the parameters t ~ ,

and L satisfy the relationship ~ - - t~ > M 5.

(2;.1)

The p r o o f derives from (1.1) and (1.3). THEOREM 2._ For the existence o f an allowed T E G for r the parameters t k , t k and T_ satisfy the relationship:

% + 9 ~< t~,

>~ 0 it is necessary and sufficient that

k = 1,M,

0.2)

where % = t 1, % = max{t e %_~ -k-~_}, k = 2, M,

(3.3)

.),-

(3.4) where $,~ =TM, ~k = rain {[e ~k+~--x_}, k = M - - 1,1. (3.5) Proof. Sufficiency. Let the conditions ( 3 . 2 ) - ( 3 . 3 ) be fulfilled. Let us show that there exists a vector T' E G for which the conditions ( 1 . 1 ) - ( 1 . 4 ) are fulfilled. Let us introduce the vectors g2 = ( % , . . . , %~_~) into the analysis by means o f the relationships % = t j _ q-Zx~,. k = l , M , which implement the one-to-one mapping form

T~f2.

(3.6)

Then the constraints ( 1 . 1 ) - ( 1 . 3 ) may be represented in the

~0~ = 7M,

(3.7)

tk+~ ~< % ~ tk, k = 1, M - - 1,

(3.8)

%--%-i

>~ x, k = 1, M,

(3.9)

where 6% = k l Let us fix

%=%+~,

k= 1 M--1

and establish that the vector

fl'=(%,%,...,q0Mi

satisfies the

conditions (3.8)-(3.9). Actually, the left side of the inequalities (3.8) derives from (3.3): % = %+j > tk+ ~, k = t, M---~I. The right side o f the inequalities (3.8) derives from (3.2)-(3.3):

% = %+~= t~+~V(% + ~_), where _tk+j < t ~

to the conditions (1.4), while f~. according to the conditions (3.2). - r k ' -i -_r 4 t j "or". The proof of the inequalities (3.9) derives from (3.3) and (3.6):

according

Here the logical symbol \ / denotes Tk = % - - % _ ~ = % + ~ - - % > ~.

Consequently, the vector ~ ' (and along with it the corresponding vector T') is allowed. Sufficiency of Conditions ( 3 . 4 ) - ( 3 . 5 ) is proved analogously. Necessity. Let the vector T E G. Then the relationships ( 3 . 7 ) - ( 3 . 9 ) are fulfilled for its corresponding vector ~ . Let us begin by showing that the conditions (3.2) are satisfied for the parameter ~ok. F o r this purpose we preliminarily establish the fact that %>%+j,

k=l,M.

(3.10)

867

Assume the opposite - i.e., there exists a k* E (1, ..., M} which is such that %,. "( %*+I" Then from (3.3) it follows that either

% <_tv.+~,

(3.11)

which is impossible by virtue of (3.8), or

%-- < %~ + _~"

(3.12)

Using the constraint (3.9) for k = k* and the inequality (3.12), we obtain ( 0 , . < %,., (i.e., the inequality (3.11) for a value o f k* which is one less). Carrying out an analogous cycle of reasoning (k* - 1) times, we arrive at the conclusion that either %,
Actually, from (3.8), (3,3) and (3.10)

t~ > ~,~,> %+, = max {tk+!, % § 5} >~ % + 5 ' which is what it was required to prove. The proof that (3.4) can be fulfilled for any allowed vector T is carried out analogously. Remark. In proving Theorem 2 it was established that fulfillment o f the inequalities (3.10) is required for any allowed vector g2. The inequalities % ~< %,, k ~ 1, M - i may be proved analogously. Then the constraints (1.2) or (3.8) in the original nonlinear-programming problem ( 1 . 1 ) - ( 1 . 6 ) may be replaced by the inequalities >-

%<+! ~< c~ ~< ~bk' te = I , M - - 1,

(3.13)

which in the general case narrow the allowed domain defined by the constraints (1.2) or (3.8). 4. Let the conditions (3.2) and (3.4) for the existence o f an allowed solution of the problem (1.1)-(1.6) be fulfilled, and let the parameters t~, t k in the constraints ( 1 . 1 ) - ( 1 . 4 ) be replaced by the parameters ~Ok, ~k which are defined in (3.3) and (3.5), respectively. Then the problem o f determining the optimal solution T O or fZ~ is solved by the following theorem. THEOREM 3 (concerning p, p-cuts).

Let the efficiency function ,/(~)CC~0.=~ be a decreasing function

P ( r ) < 0 and a rigorously convex function P ' ( r ) > 0; the weighting coefficients C k = 1; the constraint r_ satisfies the conditions (3.2) and (3.4);

tt< ~ rain ,tt/<, k C {2 . . . . . v~ =- rain v~,, kE{1 . . . . . d.~

.44}; M--l};

-

, k=

1,M:

~k, ~k are determined from the recursive relationships (3.3) and (3.5); ~o is the optimal solution T o of problem ( 1 . 1 ) - ( 1 . 6 ) after it has been transformed according to the relationships (3.6). Thus, if 1)

pj ~> 0 and Pi ~ 0, then it is required that ~';;i= o~, ~ - -

2)

pj < 0, then it is required that o;~_~ = %, jE{2 .... M } ;

3)

Pi < 0, then it is required that c0'~=% i6{1 . . . . . .

1, M -

1:

VI--1}.

Theorem 3 is a development o f the corresponding theorems concerning /~, v-cuts which were proved in [2], [3], [5] for the case r_ = 0. The proof o f this theorem is carried out analogously. Remark 1. Theorem 3 allows a stepwise algorithm for determining the exact solution g2~ to be constructed in such a way that on each step the vector $20 is determined either entirely (in the case when i - 1 or (and) coo is fixed if the conditions 2) or conditions 1) are fulfilled), or only one o f its components coo

868

(and) 3), respectively, are satisfied. In case 2) a /a-cut of the time resource D-I, t-M] into two resources _ ~_~l and [~o/_~, it1, 0 7~1 is performed, and a problem analogous to the problem (1)-(6) of optimal time-resource sharing but having lower dimensionality is solved for each resource. Similarly, in case 3) a v-cut is performed. The indicated decomposition in cases 2) and 3) is terminated when M = 1, and the problem degenerates into a trivial problem. Under these conditions the solution T o is found exactly and during a finite number of steps that does not exceed the dimensionality M of the original problem. Remark 2. The program of the algorithm for g, v-cuts in the case r_ /> 0 calculates the optimal timeresource distribution for monitoring problems on the BESM-3M digital computer for M = 10 in ~< 1 sec, occupies 117 (10) commands, and may be used for 2 ~< M ~< 290. LITERATURE CITED 1. B. V. Gnedenko and I. N. Kovalenko, Introduction to Queueing Theory [in Russian], Izd. Nauka, Moscow (1966). 2. V. F. Bilyuba, N. M. Belosudtsev, Yu. I. Neimark, V. P. Saverev and M. A. Shelkovnikov, "On a certain optimal servicing algorithm," in: Problems of Accuracy and Efficiency of Computing Algorithms [in Russian], Vol. 4, Izd. Instituta Kibernetiki AN Ukrainsk. SSR, Kiev (1969). 3. V. F. Bilyuba, "On optimal servicing of a flow of objects," in: Methods for Controlling Large Systems [in Russian], Vol. 2, SEI, Irkutsk (1970). 4. N. M. Belosudtsev, V. F. Bilyuba and Yu. I. Neimark, "Efficiency of a certain algorithm for stepwise planning of servicing in the presence of time-local information on the incoming flow," Izv. Akad. Nauk SSSR, Tekhnicheskaya Kibernetika, No. 2 (1972). 5. V. F. Bilyuba and V. P. Savel'ev, "Investigation of optimal time-resource sharing in a certain problem of servicing with priorities," Izv. Vyssh. Uchebn. Zaved., Radiofiz., No. 7 (1972). 6. V. I. Kukekov and A. A. Pervozvanskii, "Optimal servicing of a flow of objects in the presence of a bounded zone of action", Izv. Akad. Nauk SSSR, Tekhnicheskaya Kibernetika, No. 5 (1968). 7. N. O. Vil'chevskii and V. G. Kukekov, "Optimal distribution of the time for servicing a flow of objects," in: Production Control [in Russian], Nauka, Moscow (1972). 8. V. F. Burdyuk and V. V. Shkurba, "Scheduling theory. Problems and methods of solution. Part I," Kibernetika, No. 1 (1971). 9. V. V. Shkurba, T. P. Podchasova, A. N. Pshichuk and L. P. Tur, "Problems in calendar planning and methods of solving them," [in Russian], Izd. Naukova Dumka, Kiev (1966). 10. V. S. Tanaev, "On a certain class of scheduling theory problems," in: Production Control [in Russian], Izd. Nauka, Moscow (1967).

869