Scheduling of Two Parallel Machines with Linear Decreasing Time Slot Costs to Minimize Total Weighted Completion Time ⋆

Abstract

We consider a scheduling problem with two parallel machines to minimize the sum of total weighted completion time and total machine time slot cost. In this paper we focus on the case of the constant or linear decreasing sequences of time slot costs. We suggest an exact pseudopolynomial DP algorithm for the case of arbitrary integer processing times of jobs. If all jobs have unit processing times, we modify our approach to obtain a polynomial algorithm.

-

Introduction ⋆ partially supported by the Project BRFFR 15 CO-043 Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org

A schedule s is determined by assigning for each job i 2 N its start moment ri(s)

and machine L on which it will be processed. Notice that in a schedule s there may be some machine idle times between jobs.

The objective is to nd a schedule s minimizing the function

F1(s) + F2(s) = n 2 ∑ wiCi + ∑ i=1 L=1 i2NL(s) ∑

L ri(s);Ci(s):

We denote this problem by P 2jslotcostj ∑(wiCi + rLi;Ci ). In [1] the analogous problem for single machine is denoted by 1jslotcostj ∑(wiCi + ri;Ci ).

Proposition 1 ([ 1 ]). If the sequence f kg of time slot costs, k = 1; 2; :::; K, is nondecreasing, the problem 1jslotcostj ∑(wiCi + ri;Ci ) reduces to the classical problem 1jj ∑wiCi.

The same conclusion can be done for the problem P 2jslotcostj ∑(wiCi +

L ri;Ci ).

Theorem 1. [ 2 ] If the sequence f kg, k = 1; 2; :::; K, is non-increasing, the problem 1jslotcostj ∑(wiCi + ri;Ci ) is NP-hard in the strong sense.

Consider the case of the problem 1jslotcostj ∑(wiCi + ri;Ci ) where the time slot

cost decreases as a linear function of the time index k, i.e. k k+1 = ", " > 0, for k = 1; 2; :::; K 1.

Lemma 1. [ 2 ] If the sequence f kg, k = 1; 2; :::; K, is linear decreasing, then in a optimal schedule for the problem 1jslotcostj ∑(wiCi + ri;Ci ) the jobs are scheduled in the order wp11 wp22 ::: wpnn .

Lemma 2. [ 2 ] For a job i, if wpii > ", then it is optimal to process this job as early as possible. If wpii < ", then it is optimal to process job i as late as possible. If wpii = ", then the job has the same cost no matter when it is processed.

Based on the above lemmas, an O(nlogn) algorithm is suggested in [2] for the

problem 1jslotcostj ∑(wiCi + ri;Ci ) with linear decreasing time slot cost sequence. 1

Algorithm DP-LinDec-2 for the case of arbitrary processing times

Suppose that two parallel machines have either constant or linear decreasing time slot

cost sequences f k1g and f k2g: k1 k1+1 = "1 and k2 k2+1 = "2 for k = 1; 2; :::; K 1, where 0 "1 "2.

Divide the set N of jobs into three subsets: J1 = fi : wi=pi > "2g, J2 = fi : wi=pi < "1g, J3 = fi : "1 wi=pi "2g. For a nonempty set Jj , 1 j 3, we set nj = jJj j, Pj = ∑i2Jj pi; otherwise let nj = 0, Pj = 0.

Let us order and renumber the jobs in such way that we have:

J1 = fi1; i2; :::; in1 g and wpii11 wpii22 ::: wpiinn11 > "2; J2 = fk1; k2; :::; kn2 g and wpkk11 wpkk22 ::: wpkknn22 < "1; J3 = fl1; l2; :::; ln3 g and "2 wpll11 wpll22 ::: wpllnn33 "1.

For the problem under consideration we present an algorithm DP-LinDec-2 (Dynamical Programming- Linear Decreasing time slot costs - 2 machines) which proceeds in three stages.

At Stage 1, algorithm DP-LinDec-2 schedules jobs from the set J1:

Let J1 ̸= ∅. Denote p(m1) = pi1 + pi2 + ::: + pim for m = 1; 2; :::; n1; P1 = p(n11).

Consider a subproblem with jobs i1; i2; :::; im. Suppose that machines start at time 0.

Let f1(x; m) be the minimal value of the objective function when machine 1 completes the processing at time x, 0 x minfP1; Kg. Then machine 2 should complete the processing at time (p(m1) x). Due to the WSPT property, job im is the last job either on machine 1 or on machine 2. Hence, we have the following dynamic programming recursion: f1(x; m) = minff1(x pim ; m 1) + wim x + f1(x; m 1) + wim (p(m1) 1 x pim ;x; x) + p2(m1) 1 x;p(m1) xg:

The boundary conditions are:

f1(x; m) = +1 for x < 0, or x > minfK; p(m1)g, or p(m1) x > K.

The initial conditions are

f1(x; 1) = wi1 pi1 + 02;pi1 ; if x = 0,

wi1 pi1 + 01;pi1 , if x = pi1 , +1 otherwise.

For each x = 0; 1; :::; minfP1; Kg we keep the value f1(x; n1) and its corresponding schedule ′(x). If J1 = ∅, we set x = 0, f1(0; 0) = 0. In this case the corresponding schedule ′(0) is a dummy one. The time complexity of Stage 1 is O(n1P1).

At Stage 2, algorithm DP-LinDec-2 schedules jobs from the set J2:

Let J2 ̸= ∅. Denote p(m2) = pk1 + pk2 + ::: + pkm for m = 1; 2; :::; n2; P2 = p(n22):

Consider a subproblem with jobs k1; k2; :::; km from the set J2. Let f2(y; m) be the

minimal value of the objective function when machine 2 starts the processing of some of these jobs at time y. Then machine 1 starts the processing of the remaining part of these jobs at time 2K y p(m2). Both machines complete the processing at time K. Actually, from the symmetry between the set J1 and the set J2 we can use the similar dynamic programming approach in the opposite direction. Formally, we have the following dynamic programming recursion: f2(y; m) = minff2(y + pkm ; m 1) + wkm (y + pkm ) + 2 y;y+pkm ; p(m2) 1) + 21K y p(m2);2K y p(m2) 1 g: f2(y; m 1) + wkm (2K y

The boundary conditions are:

f2(y; m) = +1 for y > K, or y < maxf0; K p(m2)g, or 2K y p(m2) < 0.

The initial conditions are

f2(y; 1) = wk1 K + K2 pk1 ;K ; if y = K pk1 ,

wk1 K + K1 pk1 ;K , if y = K; +1, otherwise.

For each y = K; K 1; :::; maxf0; K P2g we keep the value f2(y; n2) and its corresponding schedule ′′(y). If J2 = ∅, we set y = K, f2(K; 0) = 0. In this case the corresponding schedule ′′(K) is a dummy one. The time complexity of Stage 2 is O(n2P2).

Stage 3 of algorithm DP-LinDec-2 is realized for all values of the variables x and

y, 0 x minfP1; Kg, maxf0; K P2g y K.

Let us consider the particular values of x and y from the above ranges. At rst the algorithm checks, if there exists a feasible schedule (x; y) such that in this schedule jobs from the sets J1 and J2 are processed in the same time intervals and on the same machines as in the schedules ′(x) and ′′(y). A schedule (x; y) is feasible if each machine processes no more than one job at any time slot. To make sure that a feasible schedule exists, it is sufficient to verify that the inequality P1 y x 2K y P2 holds. If a schedule (x; y) is feasible, the algorithm inserts the jobs from the set J3 into it.

Let J3 ̸= ∅. Denote p(m3) = pl1 + pl2 + ::: + plm for m = 1; 2; :::; n3; P3 = p(n33):

Consider a subproblem with jobs l1; l2; :::; lm from the set J3. We know that ma

chine 1 starts the processing of some of these jobs at time x and completes at time z, while machine 2 starts the processing of the remaining part of these jobs at time u. Let f3(x; y; z; u; m) be the minimal value of the objective function when machine 1 completes the processing of the rst part of the set J3 at time z. Then machine 2 should complete the processing of the remaining jobs of the set J3 at time u + p(m3) (z x). Due to the WSPT property, job lm is the last job from the set J3 either on machine 1 or on machine 2. Hence, we have the following dynamic programming recursion: f3(x; y; z; u; m) = minff3(x; y; z plm ; u; m 1) + wlm z + z1 plm ;z; f3(x; y; z; u; m 1) + wlm (u + p(m3) (z x))) + u2+p(m3) 1 (z x);u+p(m3) (z x)g:

The boundary conditions are:

f3(x; y; z; u; m) = +1 for z < x, or z > minf2K y

P2; x + p(m3)g, or u + p(m3) (z x) > y.

The initial conditions are: f3(x; y; z; u; 1) = wl1 (u + pl1 ) + wl1 (x + pl1 ) + 2 u;u+pl1 , if z = x and u + pl1 x1;x+pl1 , if z = x + pl1 2K y, y

P2, +1, otherwise.

Thus, for any feasible schedule (x; y) algorithm DP-LinDec-2 constructs a fam

ily of feasible schedules ~(x; y; z; u), x z minfx + P3; 2K y P2g, maxfy

P3; P1 xg u y. Each schedule ~(x; y; z; u) has the value f3(x; y; z; u; n3) of the

objective function. If J3 = ∅ we set z = x, u = y, f3(x; y; x; y; 0) = 0. In this case the corresponding schedule ~(x; y; x; y) coincides with the schedule (x; y).

At each step of Stage 3 we keep only the current schedule with the minimal value

of the function f1(x; n1) + f2(y; n2) + f3(x; y; z; u; n3) that is found over all values of the variables x; y; z; u enumerated till the moment. After nishing Stage 3 the algorithm nds an optimal schedule. The time complexity of Stage 3 is O(n3P1P2P32).

The whole time complexity of algorithm DP-LinDec-2 is O(n1P1+n2P2+n3P1P2P32).

It should be mentioned that at all stages of algorithm the space complexity is O(nK).

Algorithm DP-LinDec-2-UT for the case of unit processing times

Consider the particular case of the problem under consideration when all jobs have

unit processing times, i.e. all pi = 1. Since in this case Pj = nj, 1 j 3, the algorithm DP-LinDec-2 becomes polynomial algorithm with the complexity O(n21 + n22 + n1n2n33). However, we can suggest the modi cation of our approach to reduce the complexity to O(n1n2n3). Let us consider an algorithm DP-LinDec-2-UT(Dynamical

Programming- Linear Decreasing time slot costs - 2 machines-Unit Times)which consists of four stages.

Let L1; L2 be the numbers of machines, L1 2 f1; 2g, L2 = 3 L1.

At Stage 1, algorithm DP-LinDec2-UT calculates the contribution of jobs from the set J1 into the optimal value of the objective function. Let J1 ̸= ∅. Suppose that machines start at time 0. Let g1(x; L1) be the minimal contribution of jobs from the set J1 when machine L1 completes the processing at time x. Then machine L2 should complete the processing at time (n1 x). Jobs will be scheduled on machines in the nonincreasing order of their weights. Hence, we have the following dynamic programming recursion: g1(0; L1) = 0L;2n1 + ∑jn=11 jwij ; g1(x; L1) = g1(x 1; L1) + xL1 1;x nL12 x;n1 (x 1) ∑jn=12x wij ; where x = 1; 2; :::; [ n1 ] and L1 2 f1; 2g:

2

We keep all values g1(x; 1), g1(x; 2), where x = 0; 1; :::; [ n21 ]. If J1 = ∅, we set x = 0, g1(0; 1) = 0, g1(0; 2) = 0. The time complexity of Stage 1 is O(n1).

At Stage 2, algorithm DP-LinDec2-UT calculates the contribution of jobs from

the set J2 into the optimal value of the objective function. Let J2 ̸= ∅ and g2(y; L1) be the be the minimal contribution of jobs from the set J2 when machine L1 starts the processing at time K y. Then machine L2 should start the processing at time

K (n2 y). Both machines complete the processing at time K. We have the following

dynamic programming recursion: g2(0; L1) = KL2 n2;K + ∑jn=21(K n2 + j)wkj ; g2(y; L1) = g2(y 1; L1) + KL1 y;K y+1 KL2 (n2 y+1);K (n2 y)+ ∑jn=21 2y+1 wkj ; where y = 1; 2; :::; [ n2 ] and L1 2 f1; 2g:

2

We keep all values g2(y; 1), g2(y; 2), y = 0; 1; :::; [ n22 ]. If J2 = ∅, we set y = 0, g2(0; 1) = 0, g2(0; 2) = 0. The time complexity of Stage 2 is O(n2).

At Stage 3, algorithm DP-LinDec-2-UT calculates the contribution of jobs from

the set J3 into the optimal value of the objective function under the condition that jobs from the sets J1 and J2 have been already assigned to machines.

Let J3 ̸= ∅ and g3(z; x; y) be the minimal contribution of jobs from the set J3 when machine 1 starts the processing of some of these jobs at time x and completes their processing at time x + z, while machine 2 starts the processing of the remaining part of these jobs at time K y (n3 z) and completes their processing at time K y.

We have the following dynamic programming recursion:

g3(0; x; y) = K2 y n3;K y + ∑jn=31(K y n3 + j)wlj ; g3(z; x; y) = g3(z 1; x; y) + x1+z 1;x+z K2 y (n3 (z 1));K y (n3 z)+ (x + z)wlz (K y (n3 z))wlz ; where x = 0; 1; 2; :::; [ n21 ], y = 0; 1; 2; :::; [ n22 ], z = 1; 2; :::; n3.

We keep all values g3(z; x; y), x = 0; 1; :::; [ n21 ], y = 0; 1; :::; [ n22 ], z = 0; 1; :::; n3. If J3 = ∅, we set z = 0, g3(0; x; y) = 0 for x = 0; 1; :::; [ n21 ], y = 0; 1; :::; [ n22 ]. The time complexity of Stage 3 is O(n1n2n3).

At Stage 4, algorithm DP-LinDec-2-UT nds an optimal schedule. The total

cost of an optimal schedule corresponds to the value G = minfG1; G2; G3g, where

G1 = minfg1(x; 1) + g2(y; 1) + g3(0; x; y)jx = 0; 1; :::; [ n21 ]; y = 0; 1; :::; [ n22 ]; n1 x K (n2 y + n3)g;

G2 = minfg1(x; 2) + g2(y; 2) + g3(n3; n1 x; y)jx = 0; 1; :::; [ n21 ]; y = 0; 1; :::; [ n22 ]; n1 x + n3 K (n2 y)g;

G3 = minfg1(x; 2)+g2(y; 1)+g3(z; n1 x; n2 y)jx = 0; 1; :::; [ n21 ]; y = 0; 1; :::; [ n22 ]; z = 1; 2:::; n3 1; n1 x + z K y; x K (n2 y) (n3 z)g.

If G = G1 then on machine 1 we reserve x slots starting from the time moment 0 and y slots starting from the moment K y, while on machine 2 we reserve n1 x slots starting from the time moment 0 and n2 y + n3 slots starting from the moment K (n2 y) n3.

If G = G2 then on machine 2 we reserve x slots starting from the time moment 0 and y slots starting from the moment K y, while on machine 1 we reserve n1 x + n3 slots starting from the time moment 0 and n2 y slots starting from the moment K n2 + y.

If G = G3 then on machine 1 we reserve n1 x + z slots starting from the time moment 0 and y slots starting from the moment K y, while on machine 2 we reserve x slots starting from the time moment 0 and n2 y + n3 z slots starting from the moment K n2 + y n3 + z.

In the reserved slots we assign jobs of the sets J1, J3 and J2 in nonincreasing order of their weights. The time complexity of algorithm DP-LinDec-2-UT is O(n1n2n3). If for each job i we have pi = 1 and wi = 1, then all jobs are contained only in one of the sets J1, J2, or J3. In this case the complexity of the algorithm will be O(n).

References

1. Wan G. , Qi X. : Scheduling with Variable Time Slot Costs . Naval Research Logistics. ( 2010 ) V. 57, N 2. P. 159 - 171 .

2. Zhao Y. , Qi X. , Li M.: On scheduling with non-increasing time slot cost to minimize total weighted completion time . Journal of Scheduling. -DOI 10.1007/s10951-015-0462-9.