=Paper=
{{Paper
|id=Vol-1623/papersc5
|storemode=property
|title=Scheduling of Two Parallel Machines with Linear Decreasing Time Slot Costs to Minimize Total Weighted Completion Time
|pdfUrl=https://ceur-ws.org/Vol-1623/papersc5.pdf
|volume=Vol-1623
|authors=Alexander Kononov,Irina Lushchakova
|dblpUrl=https://dblp.org/rec/conf/door/KononovL16
}}
==Scheduling of Two Parallel Machines with Linear Decreasing Time Slot Costs to Minimize Total Weighted Completion Time==
https://ceur-ws.org/Vol-1623/papersc5.pdf
Scheduling of Two Parallel Machines with Linear
Decreasing Time Slot Costs to Minimize Total
Weighted Completion Time ⋆
Alexander Kononov1,2 and Irina Lushchakova3,4
1
Sobolev Institute of Mathematics,
4, Akad. Koptyug avenue, 630090, Novosibirsk, Russia.
2
Novosibirsk State University, 2, Pirogova str., 630090, Novosibirsk, Russia
3
Belarusian State University of Informatics and Radioelectronics, Belarus.
4
UIIP NAS of Belarus, Belarus.
alvenko@math.nsc.ru,
IrinaLushchakova@yandex.ru
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 decreas-
ing 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
There are two parallel machines and a set N = {1, 2, ..., n} of jobs that should be
processed on these machines. An integer processing time pi > 0 and a weight wi > 0
are given for each job i ∈ N . It is assumed that every job is processed on at most one
machine at a time, and each machine processes no more than one job at a time. In a
schedule s, job i starts at time ri (s) and completes at time Ci (s) = ri (s) + pi , being
processed on a machine ∑ without interruption. We shall consider the total weighted
n
completion time F1 (s) = i=1 wi Ci which is one of the traditional scheduling criteria.
Suppose that the planning horizon consists ∑of K time slots with unit length. Assume
n
that pi ≤ K for each job i ∈ N and P = i=1 pi ≤ 2K. We shall call the interval
(k − 1; k] by the kth slot, k = 1, 2, ..., K. Denote πkL the cost of using the kth time
slot by machine L, 1 ≤ L ≤ 2. Let NL (s) be a set of jobs assigned to machine L in a
schedule s. For job i ∈ NL (s) denote π̄rLi (s),Ci (s) its total time slot cost in a schedule s,
i.e. π̄rLi (s),Ci (s) = π̄rLi (s),ri (s)+pi = πrLi (s)+1 + πrLi (s)+2 + ... + πrLi (s)+pi , where ri (s) is the
starting time of processing job i in this schedule. Then the total ∑2 time ∑slot cost for a given
planning horizon and a schedule s is the function F2 (s) = L=1 i∈NL (s) π̄rLi (s),Ci (s) .
⋆
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
Linear Decreasing Time Slot Costs 345
A schedule s is determined by assigning for each job i ∈ 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 find a schedule s∗ minimizing the function
∑
n ∑
2 ∑
F1 (s) + F2 (s) = wi Ci + π̄rLi (s),Ci (s) .
i=1 L=1 i∈NL (s)
∑ L
We denote this problem by P 2|slotcost| (wi C∑ i + π̄ri ,Ci ). In [1] the analogous
problem for single machine is denoted by 1|slotcost| (wi Ci + π̄ri ,Ci ).
Proposition 1 ([1]). If the sequence∑ {πk } of time slot costs, k = 1, 2, ..., K, is non-
decreasing,
∑ the problem 1|slotcost| (wi Ci + π̄ri ,Ci ) reduces to the classical problem
1|| wi Ci .
∑
The same conclusion can be done for the problem P 2|slotcost| (wi Ci + π̄rLi ,Ci ).
Theorem ∑ 1. [2] If the sequence {πk }, k = 1, 2, ..., K, is non-increasing, the problem
1|slotcost| (wi Ci + π̄ri ,Ci ) is NP-hard in the strong sense.
∑
Consider the case of the problem 1|slotcost| (wi Ci + π̄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 {πk }, k = ∑ 1, 2, ..., K, is linear decreasing, then in a
optimal schedule for the problem 1|slotcost| (wi Ci + π̄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 1|slotcost| (wi Ci + π̄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 {πk1 } and {πk2 }: πk1 −πk+1 1
= ε1 and πk2 −πk+12
= ε2 for k = 1, 2, ..., K −1,
where 0 ≤ ε1 ≤ ε2 .
Divide the set N of jobs into three subsets: J1 = {i : wi /pi > ε2 }, J2 = {i : wi /pi <
ε1 }, J∑
3 = {i : ε1 ≤ wi /pi ≤ ε2 }. For a nonempty set Jj , 1 ≤ j ≤ 3, we set nj = |Jj |,
Pj = i∈Jj pi ; otherwise let nj = 0, Pj = 0.
Let us order and renumber the jobs in such way that we have:
w w wi
J1 = {i1 , i2 , ..., in1 } and pii1 ≥ pii2 ≥ ... ≥ pi n1 > ε2 ;
1 2 n1
346 A. Kononov, I. Lushchakova
w w wk
J2 = {k1 , k2 , ..., kn2 } and pkk1 ≤ pkk2 ≤ ... ≤ pk n2 < ε1 ;
1 2 n2
w w wl
J3 = {l1 , l2 , ..., ln3 } and ε2 ≥ pll1 ≥ pll2 ≥ ... ≥ pl n3 ≥ ε1 .
1 2 n3
For the problem under consideration we present an algorithm DP-LinDec-2 (Dy-
namical 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 .
(1) (1)
Let J1 ̸= ∅. Denote p̄m = pi1 + pi2 + ... + pim for m = 1, 2, ..., n1 ; P1 = p̄n1 .
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 ≤ min{P1 , K}. Then machine 2 should complete the
(1)
processing at time (p̄m − 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) = min{f1 (x − pim , m − 1) + wim x + π̄x−p 1
im ,x
,
(1)
f1 (x, m − 1) + wim (p̄m − x) + π̄ 2(1) (1) }.
p̄m−1 −x,p̄m −x
The boundary conditions are:
(1) (1)
f1 (x, m) = +∞ for x < 0, or x > min{K, p̄m }, or p̄m − x > K.
The initial conditions are
2
f1 (x, 1) = wi1 pi1 + π̄0,p i1
, if x = 0,
1
wi1 pi1 + π̄0,pi1 , if x = pi1 , +∞ otherwise.
For each x = 0, 1, ..., min{P1 , K} 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(n1 P1 ).
At Stage 2, algorithm DP-LinDec-2 schedules jobs from the set J2 .
(2) (2)
Let J2 ̸= ∅. Denote p̄m = pk1 + pk2 + ... + pkm for m = 1, 2, ..., n2 ; P2 = p̄n2 .
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
(2)
of these jobs at time 2K − y − p̄m . 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) = min{f2 (y + pkm , m − 1) + wkm (y + pkm ) + π̄y,y+p
2
km
,
(2)
f2 (y, m − 1) + wkm (2K − y − p̄m−1 ) + π̄ 1 (2) (2) }.
2K−y−p̄m ,2K−y−p̄m−1
The boundary conditions are:
(2) (2)
f2 (y, m) = +∞ for y > K, or y < max{0, K − p̄m }, or 2K − y − p̄m < 0.
The initial conditions are
2
f2 (y, 1) = wk1 K + π̄K−p k ,K
, if y = K − pk1 ,
1
1
wk1 K + π̄K−p k1 ,K
, if y = K, +∞, otherwise.
For each y = K, K − 1, ..., max{0, K − P2 } 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
Linear Decreasing Time Slot Costs 347
corresponding schedule σ ′′ (K) is a dummy one. The time complexity of Stage 2 is
O(n2 P2 ).
Stage 3 of algorithm DP-LinDec-2 is realized for all values of the variables x and
y, 0 ≤ x ≤ min{P1 , K}, max{0, K − P2 } ≤ y ≤ K.
Let us consider the particular values of x and y from the above ranges. At first 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.
(3) (3)
Let J3 ̸= ∅. Denote p̄m = pl1 + pl2 + ... + plm for m = 1, 2, ..., n3 ; P3 = p̄n3 .
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 first part of the set J3 at time z. Then machine 2 should
(3)
complete the processing of the remaining jobs of the set J3 at time u + p̄m − (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) = min{f3 (x, y, z − plm , u, m − 1) + wlm z + π̄z−p
1
lm ,z
,
(3)
f3 (x, y, z, u, m − 1) + wlm (u + p̄m − (z − x))) + π̄ 2 (3) (3) }.
u+p̄m−1 −(z−x),u+p̄m −(z−x)
The boundary conditions are:
(3)
f3 (x, y, z, u, m) = +∞ for z < x, or z > min{2K − y − P2 , x + p̄m },
(3)
or u + p̄m − (z − x) > y.
The initial conditions are:
2
f3 (x, y, z, u, 1) = wl1 (u + pl1 ) + π̄u,u+p l
, if z = x and u + pl1 ≤ y,
1
1
wl1 (x + pl1 ) + π̄x,x+p l1
, if z = x + pl1 ≤ 2K − y − P2 ,
+∞, 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 ≤ min{x + P3 , 2K − y − P2 }, max{y −
P3 , P1 − x} ≤ 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 finishing Stage 3 the algorithm
finds an optimal schedule. The time complexity of Stage 3 is O(n3 P1 P2 P32 ).
The whole time complexity of algorithm DP-LinDec-2 is O(n1 P1 +n2 P2 +n3 P1 P2 P32 ).
It should be mentioned that at all stages of algorithm the space complexity is O(nK).
348 A. Kononov, I. Lushchakova
2 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 al-
gorithm DP-LinDec-2 becomes polynomial algorithm with the complexity O(n21 +
n22 + n1 n2 n33 ). However, we can suggest the modification of our approach to reduce the
complexity to O(n1 n2 n3 ). Let us consider an algorithm DP-LinDec-2-UT(Dynamical
Programming- Linear Decreasing time slot costs - 2 machines-Unit Times)which con-
sists of four stages.
Let L1 , L2 be the numbers of machines, L1 ∈ {1, 2}, 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 non-
increasing order of their weights. Hence, we have the following dynamic programming
recursion: ∑n 1
L2
g1 (0, L1 ) = π̄0,n + j=1 jwij ,
1
∑n1
g1 (x, L1 ) = g1 (x − 1, L1 ) + π̄x−1,x
L1
− π̄nL12−x,n1 −(x−1) − j=2x wij ,
where x = 1, 2, ..., [ 2 ] and L1 ∈ {1, 2}.
n1
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: ∑n2
L2
g2 (0, L1 ) = π̄K−n 2 ,K
+ j=1 (K − n2 + j)wkj ,
g2 (y, L1 ) = g2 (y − 1, L1 ) + π̄K−y,K−y+1
L1
− π̄K−(n
L2
2 −y+1),K−(n2 −y)
+
∑n2 −2y+1
j=1 wkj , where y = 1, 2, ..., [ 2 ] and L1 ∈ {1, 2}.
n2
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
∑n 3 recursion:
2
g3 (0, x, y) = π̄K−y−n 3 ,K−y
+ j=1 (K − y − n3 + j)wlj ,
g3 (z, x, y) = g3 (z − 1, x, y) + π̄x+z−1,x+z
1
− π̄K−y−(n
2
3 −(z−1)),K−y−(n3 −z)
+
Linear Decreasing Time Slot Costs 349
(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(n1 n2 n3 ).
At Stage 4, algorithm DP-LinDec-2-UT finds an optimal schedule. The total
cost of an optimal schedule corresponds to the value G = min{G1 , G2 , G3 }, where
G1 = min{g1 (x, 1) + g2 (y, 1) + g3 (0, x, y)|x = 0, 1, ..., [ n21 ]; y = 0, 1, ..., [ n22 ]; n1 − x ≤
K − (n2 − y + n3 )};
G2 = min{g1 (x, 2) + g2 (y, 2) + g3 (n3 , n1 − x, y)|x = 0, 1, ..., [ n21 ]; y = 0, 1, ..., [ n22 ];
n1 − x + n3 ≤ K − (n2 − y)};
G3 = min{g1 (x, 2)+g2 (y, 1)+g3 (z, n1 −x, n2 −y)|x = 0, 1, ..., [ n21 ]; y = 0, 1, ..., [ n22 ]; z =
1, 2..., n3 − 1, n1 − x + z ≤ K − y; x ≤ K − (n2 − y) − (n3 − z)}.
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(n1 n2 n3 ).
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.