# Parallel-Machine Scheduling Problems with Past-Sequence-Dependent Delivery Times and Aging Maintenance

Authors: Wei-min Ma; Li Sun; Xue-qin Zeng; Lei Ning
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We consider parallel-machine scheduling problems with past-sequence-dependent (psd) delivery times and aging maintenance. The delivery time is proportional to the waiting time in the system. Each machine has an aging maintenance activity. We develop polynomial algorithms to three versions of the problem to minimize the total absolute deviation of job completion times, the total load, and the total completion time.


---

## Body

## 1. Introduction

A common assumption in classical scheduling theory is that the machines are available at all times. However, there are many situations where machines need to be maintained and become unavailable during certain periods. Cheng et al. [1] study single-machine scheduling with deteriorating job processing times. Lee and Leon [2] investigated single machine scheduling with a rate-modifying activity. Kubzin and Strusevich [3] presented a setting where the maintenance activity was deteriorating; that is, delaying the maintenance activity increased the time required to perform it. Lee and Lin [4] considered single machine scheduling with maintenance and repair rate-modifying activity. Lee and Chen [5] discussed parallel-machine scheduling where each machine must be maintained once during the planning horizon. Cheng et al. [1, 6] considered the unrelated parallel-machine scheduling with aging maintenance activities. Cheng et al. [7] studied a single machine problem of common due-window assignment and scheduling of aging jobs and a maintenance activity simultaneously.Browne and Yechiali [8] claimed that the time and effort required to put out a fire increase if there was a delay in the start of the fire-fighting effort. Scheduling in this setting is known as scheduling with aging jobs, which was first independently introduced by J. N. D. Gupta and S. K. Gupta [9] and Browne and Yechiali [8]. Since then, models of scheduling with deteriorating or aging jobs have been extensively studied from a variety of perspectives. More recent papers which have considered deterioration include Zhao and Tang [10], Cheng et al. [1], Wang et al. [11], Lai and Lee [12], Cheng et al. [13], Huang and Wang [14], Yin et al. [15], Lee et al. [16], Zhao and Tang [17], Wang and Liu [18], Zhao and Tang [19], Wu and Lee [20], Wang [21], Miao et al. [22], Wu and Lee [23], Yin et al. [24], Oron [25], Sicilia et al. [26], Wang et al. [27], Yin et al. [28], J.-B. Wang and J.-J. Wang [29], Xu et al. [30], Yin et al. [31], Bai et al. [32], and Ji et al. [33].In modern industrial production, the manufacturing environment has an increasing influence on the processing times of jobs. A growing evidence displays that waiting time or manufacturing environment may have a disadvantageous effect on the total processing time of a job before delivery to the customer. For example, an electronic component may be exposed to certain electromagnetic or radioactive fields while waiting in the machines preprocessing area and regulatory authorities require the component to be treated for an amount of time proportional to the jobs’ exposure time to these fields. This treatment can be performed after the component has been processed by the machine but before it is delivered to the customer so it can be delivered with a guarantee. Such an extra time for eliminating adverse effects between the main processing and the delivery of a job is viewed as a past-sequence-dependent (psd) delivery time [34]. As usual, we suppose the treatment of the adverse effect for a job does not occupy any machine and has no relation to the schedule of the jobs main processing. In addition, we also assume that the psd delivery time of a job is proportional to the job’s waiting time.Koulamas and Kyparisis [34] assumed that the psd delivery time of a job is proportional to the job’s waiting time, that is, the start time of processing. They proved some problems could be polynomially solvable. Liu et al. [35] studied the problem of single-machine scheduling with past-sequence-dependent delivery times, which was introduced in Koulamas and Kyparisis [34]. Liu [36] considered identical parallel-machine scheduling problem with past-sequence-dependent delivery times and learning effect. Shen and Wu [37] introduced the single machine past-sequence-dependent delivery times scheduling with general learning effects. Yin et al. [22] studied a single machine batch scheduling with an unavailability interval. Yin et al. [38] introduced a single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration.To the best of our knowledge, the aging maintenance scheduling problems with psd delivery time have not been investigated. In this paper, we introduce parallelmachines scheduling model with aging maintenance and psd delivery time. We will present that these scheduling problems are polynomially solvable. The remaining part of this paper is organized as follows. In Section2, a precise formulation of the problem is given. We consider problems of minimizing the total absolute deviation of job completion times, the total load on all machines, and the total completion time in Section 3. The last section contains some conclusions of our model.


## 2. Problem Formulation

There aren independent and nonpreemptive jobs simultaneously available for processing and m identical parallel machines. Each machine can handle one job at a time and preemption is not allowed. If m≥n, the problem is trivial. Therefore, we assume that m<n throughout the paper.Letaij(pij) be the normal (actual) processing time of job Jij; let ai[k](pi[k]) be the normal (actual) processing time of the job Ji[k] if it is scheduled in the kth position on machine Mi in a sequence. Due to the effects of aging, maintenance may be performed on the machine to improve its production efficiency. We suppose that at most one maintenance operation is allowed on one machine throughout the scheduling horizon. However, the starting time of the maintenance operation in the sequence is not known in advance. It can be scheduled immediately after completing the processing of any job. We further assume the following: (1) after maintenance, the machine will revert to its initial condition and the aging effects will start anew and (2) the machine maintenance duration is a linear function of its starting time and is represented by f(t)=μ+σt, where μ>0 is the basic maintenance time, σ>0 is a maintenance factor, and t is the starting time of the maintenance operation.Suppose the position of maintenance operation iski on machine Mi. Hence, the machine maintenance duration is f(t)=μ+σt=μ+σ(∑l=1kipi[l]). As in Liu et al. [39], we consider that the actual processing time of job Ji[j] which is scheduled on machine Mi in position j  (j=1,2,…,ni) is given by(1)
p
i
[
j
]
=
a
i
[
j
]
+
b
t
=
a
i
[
j
]
+
b
∑
l
=
1
j
-
1
‍
p
i
[
l
]
,
i
f
j
≤
k
i
,
a
i
[
j
]
+
b
t
=
a
i
[
j
]
+
b
∑
l
=
k
i
j
-
1
‍
p
i
[
l
]
,
i
f
j
>
k
i
.As in Koulamas and Kyparisis [34], the processing of job Ji[r] must be followed by the psd delivery time qi[r], which can be computed as(2)qi[1]=0,qi[r]=γWi[r]=γ∑l=1r-1‍pi[l],r=2,3,…,ni.γ
≥
0 is a normalizing constant and Wi[r] denotes the waiting time of job Ji[r]. In addition, it is supposed that the postprocessing operation of any job Ji[l] modeled by its delivery time qi[l] is performed off-line; consequently, it is not affected by the availability of the machine and it can commence immediately upon completion of the main operation resulting in(3)Ci[j]=Wi[j]+pi[j]+qi[j]=(1+γ)∑l=1j-1‍pil+pijifj≤ki,Ci[j]=(1+γ)μ+(1+σ)∑l=1ki‍pi[l]mmmmmm+∑l=ki+1j-1‍pil+pijifj>ki,where Ci[j] denotes the completion time of job Ji[j].For convenience, we denote thepsd delivery times given in (2) by qpsd. Let TADCi denote the total absolute deviation of jobs’ completion times on machine Mi; that is, ∑TADCi‍=∑l=1ni‍∑k=lni‍|Ci[l]-Ci[k]|. Let Li indicate the load of machine Mi; that is, Li=max{Ci[r]}, r=1,2,…,ni. We, respectively, consider the minimization of the following objective functions: the sum of the total absolute deviation of jobs’ completion times on each machine ∑i=1m‍TADCi, the total loads on all machines ∑i=1m‍Li, and the total completion time ∑i=1m‍∑j=1ni‍Cij. Using the three-field notation introduced by Graham et al. for scheduling problems, we denote our problems as(4)Pmqpsd,pij=aij+bt,maf,f∈∑‍∑‍Cij,∑‍Li,∑‍TADCi.Before presenting the main results, we first present several Lemmas and some notations that will be used in the proofs in sequel. If the number of jobsni and the position of the job preceding the maintenance operation ki on machine Mi are known in advance, the actual processing times and the completion times of jobs on machine Mi are as follows:(5)pi[1]=ai[1]Ci[1]=pi[1]=ai[1]pi[2]=ai[2]+bpi[1]=ai[2]+bai[1]Ci[2]=ai[2]+1+γ+bai[1]⋮pi[ki]=ai[ki]+bai[ki-1]+b1+bai[ki-2]+⋯+b1+bki-2ai[1]Ci[ki]=ai[ki]+1+γ+bai[ki-1]+⋯+1+γ+b1+bki-2ai[1]ft=μ+σpi1+pi2+⋯+piki=μ+σ∑j=1ki‍1+bki-jai[j]pi[ki+1]=ai[ki+1]Ci[ki+1]=1+γμ+1+γ1+σ∑j=1ki‍1+bki-jai[j]+ai[ki+1]⋮pi[ni]=ai[ni]+bai[ni-1]+⋯+b1+bni-ki-2ai[ki+1]Ci[ni]=1+γμ+1+γ1+σ∑j=1ki‍1+bki-jai[j]+∑j=ki+1ni-1‍1+γ+b1+bni-j-1aij+aini.LetP(n,m,k)=(n1,n2,…,nm;k1,k2,…,km) denote the allocation vector. We derive a lemma to bound P(n,m,k).Lemma 1.
The number ofP(n,m,k) vector is bounded from above by (n+1)2m-1/m!.Proof.
For machineM1, n1 is chosen from {0,1,…,n} and there are n+1 options for n1. When n1 is determined, k1 has at most n+1 options. After n1 is determined, n2 is chosen from {0,1,…,n-n1}⊆{0,1,…,n} at most n+1 times. Subsequently, k2 has at most n+1 options, too. For machines M3,…,Mm-1, we similarly select n3,…,nm-1 and k3,…,km-1. Note that, for the last machine Mm, nm is determined after choosing n1,…,nm-1, because ∑i=1mni=n, and km has at most n+1 options. Considering that m machines are identical, there are (n+1)2m-1/m! possibilities for P(n,m,k) vector. This completes the proof.Lemma 2 (see [40]).
Let there be two sequences of numbersxi and yi. The sum ∑i‍xiyi of products of the corresponding elements is the least (largest) if the sequences are monotonic in the opposite (same) sense.


## 3. Parallel-Machine Scheduling Problems

### 3.1. The Total Completion Time

In this section, we consider the problem of minimizing the total completion time; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑∑Cij. For machine Mi, from the above analyse, we derive the total completion time on this machine:(6)∑j=1ni‍Cij=(ni-ki)(1+γ)μ+∑j=1ki1+1+γ+b1+bki-j-1b+ni-ki1+γ1+σ1+bki-j1+bki-j-1baij+∑j=ki+1ni‍1+1+γ+b1+bni-j-1baij.Therefore, the total completion time is (7)
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
C
i
j
=
∑
i
=
1
m
‍
n
i
-
k
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
k
i
‍
1
+
1
+
γ
+
b
1
+
b
k
i
-
j
-
1
b
+
n
i
-
k
i
1
+
γ
1
+
σ
1
+
b
k
i
-
j
1
+
b
k
i
-
j
-
1
b
a
i
j
+
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
1
+
1
+
γ
+
b
1
+
b
n
i
-
j
-
1
b
a
i
j
=
∑
i
=
1
m
‍
n
i
-
k
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
w
i
j
a
i
[
j
]
,where(8)wij=1+1+γ+b1+bki-j-1b+ni-ki1+γ×1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,1+1+γ+b1+bni-j-1b,i=1,2,…,m,j=ki+1,ki+2,…,ni.Whenni and ki are given, ∑i=1m‍(ni-ki)(1+γ)μ is a constant. And ∑i=1m∑j=1niwijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Therefore, on machine Mi, if the number ni of jobs and the maintenance position ki are known, by Lemma 2, all jobs are sorted in nondecreasing order of their normal processing times first. Then the largest job is assigned to the position with the smallest value of wij, the second largest job to the position with the second smallest value of wij, and so on. The time complexity of sorting algorithm on machine Mi is O(nilogni). Together with Lemma 1, we derive the following theorem.Theorem 3.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑∑Cij can be solved in O(n2m-1nlogn) time.


### 3.2. The Sum of Load on All Machines

In this section, we investigate the problem of minimizing the sum of load on all machines; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑Li. For machine Mi, from the above analysis, we calculate the sum of load on this machine:(9)Li=1+γμ+1+γ1+σ∑j=1ki‍1+bki-jai[j]+∑j=ki+1ni-1‍1+γ+b1+bni-j-1aij+aini.Hence, the sum of load on all machines is(10)∑i=1m‍Li=m1+γμ+∑i=1m‍∑j=1ki‍1+γ1+σ1+bki-jai[j]+∑i=1m‍∑j=ki+1ni-1‍1+γ+b1+bni-j-1ai[j]+∑i=1m‍aini=m1+γμ+∑i=1m‍∑j=1ni‍wijai[j],where(11)wij=1+γ1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,1+γ+b1+bni-j-1,i=1,2,…,m,j=ki+1,ki+2,…,ni-1,1,i=1,2,…,m,j=ni.Sincem(1+γ)μ is a constant, if ni and ki are given, ∑i=1m‍∑j=1ni‍wijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Similar to the above analysis, on machine Mi, the time complexity of sorting algorithm is O(nilogni). Together with Lemma 1, we conclude the following theorem.Theorem 4.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑Li can be solved in O(n2m-1nlogn) time.


### 3.3. The Sum of TADC on All Machines

In this section, we present the problem of minimizing the sum of TADC on all machines; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑TADCi. For machine Mi, from the above analysis, we express the sum of TADC on this machine:(12)
T
A
D
C
i
=
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
j
=
1
k
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
k
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
+
∑
h
=
k
i
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
×
1
+
σ
1
+
b
k
i
-
j
∑
h
=
k
i
+
1
n
i
‍
a
i
[
j
]
+
∑
j
=
k
i
+
1
n
i
-
1
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
∑
h
=
j
+
1
n
i
‍
a
i
[
j
]
+
n
i
-
1
a
i
[
n
i
]
.Thus, the sum of TADC on all machines is(13)
∑
i
=
1
m
‍
T
A
D
C
i
=
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
k
i
‍
∑
h
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
k
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
1
+
b
h
-
j
-
1
+
∑
h
=
k
i
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
1
+
σ
×
1
+
b
k
i
-
j
∑
h
=
k
i
+
1
n
i
‍
a
i
j
+
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
-
1
‍
∑
h
=
j
+
1
n
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
∑
h
=
j
+
1
n
i
‍
a
i
[
j
]
+
∑
i
=
1
m
‍
n
i
-
1
a
i
[
n
i
]
=
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
w
i
j
a
i
[
j
]
,where(14)wij=2j-1-ni+∑h=j+1ki‍2h-1-ni1+γ+b1+bh-j-1+∑h=ki+1ni‍2h-1-ni1+γ1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,2j-1-ni+∑h=j+1ni‍2h-1-ni1+γ+b1+bh-j-1,i=1,2,…,m,j=ki+1,ki+2,…,ni-1,ni-1,i=1,2,…,m,j=ni.Since∑i=1m‍∑j=ki+1ni(2j-1-ni)(1+γ)μ is a constant, when ni and ki are given, ∑i=1m‍∑j=1niwijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Similar to the above analysis, the time complexity of scheduling algorithm on machine Mi is O(nilogni). Together with Lemma 1, we obtain the following theorem.Theorem 5.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑TADCi can be solved in O(n2m-1nlogn) time.


## 3.1. The Total Completion Time

In this section, we consider the problem of minimizing the total completion time; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑∑Cij. For machine Mi, from the above analyse, we derive the total completion time on this machine:(6)∑j=1ni‍Cij=(ni-ki)(1+γ)μ+∑j=1ki1+1+γ+b1+bki-j-1b+ni-ki1+γ1+σ1+bki-j1+bki-j-1baij+∑j=ki+1ni‍1+1+γ+b1+bni-j-1baij.Therefore, the total completion time is (7)
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
C
i
j
=
∑
i
=
1
m
‍
n
i
-
k
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
k
i
‍
1
+
1
+
γ
+
b
1
+
b
k
i
-
j
-
1
b
+
n
i
-
k
i
1
+
γ
1
+
σ
1
+
b
k
i
-
j
1
+
b
k
i
-
j
-
1
b
a
i
j
+
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
1
+
1
+
γ
+
b
1
+
b
n
i
-
j
-
1
b
a
i
j
=
∑
i
=
1
m
‍
n
i
-
k
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
w
i
j
a
i
[
j
]
,where(8)wij=1+1+γ+b1+bki-j-1b+ni-ki1+γ×1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,1+1+γ+b1+bni-j-1b,i=1,2,…,m,j=ki+1,ki+2,…,ni.Whenni and ki are given, ∑i=1m‍(ni-ki)(1+γ)μ is a constant. And ∑i=1m∑j=1niwijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Therefore, on machine Mi, if the number ni of jobs and the maintenance position ki are known, by Lemma 2, all jobs are sorted in nondecreasing order of their normal processing times first. Then the largest job is assigned to the position with the smallest value of wij, the second largest job to the position with the second smallest value of wij, and so on. The time complexity of sorting algorithm on machine Mi is O(nilogni). Together with Lemma 1, we derive the following theorem.Theorem 3.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑∑Cij can be solved in O(n2m-1nlogn) time.


## 3.2. The Sum of Load on All Machines

In this section, we investigate the problem of minimizing the sum of load on all machines; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑Li. For machine Mi, from the above analysis, we calculate the sum of load on this machine:(9)Li=1+γμ+1+γ1+σ∑j=1ki‍1+bki-jai[j]+∑j=ki+1ni-1‍1+γ+b1+bni-j-1aij+aini.Hence, the sum of load on all machines is(10)∑i=1m‍Li=m1+γμ+∑i=1m‍∑j=1ki‍1+γ1+σ1+bki-jai[j]+∑i=1m‍∑j=ki+1ni-1‍1+γ+b1+bni-j-1ai[j]+∑i=1m‍aini=m1+γμ+∑i=1m‍∑j=1ni‍wijai[j],where(11)wij=1+γ1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,1+γ+b1+bni-j-1,i=1,2,…,m,j=ki+1,ki+2,…,ni-1,1,i=1,2,…,m,j=ni.Sincem(1+γ)μ is a constant, if ni and ki are given, ∑i=1m‍∑j=1ni‍wijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Similar to the above analysis, on machine Mi, the time complexity of sorting algorithm is O(nilogni). Together with Lemma 1, we conclude the following theorem.Theorem 4.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑Li can be solved in O(n2m-1nlogn) time.


## 3.3. The Sum of TADC on All Machines

In this section, we present the problem of minimizing the sum of TADC on all machines; that is,Pm|qpsd,pi[j]=ai[j]+bt,ma|∑TADCi. For machine Mi, from the above analysis, we express the sum of TADC on this machine:(12)
T
A
D
C
i
=
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
j
=
1
k
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
k
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
+
∑
h
=
k
i
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
×
1
+
σ
1
+
b
k
i
-
j
∑
h
=
k
i
+
1
n
i
‍
a
i
[
j
]
+
∑
j
=
k
i
+
1
n
i
-
1
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
∑
h
=
j
+
1
n
i
‍
a
i
[
j
]
+
n
i
-
1
a
i
[
n
i
]
.Thus, the sum of TADC on all machines is(13)
∑
i
=
1
m
‍
T
A
D
C
i
=
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
k
i
‍
∑
h
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
k
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
1
+
b
h
-
j
-
1
+
∑
h
=
k
i
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
1
+
σ
×
1
+
b
k
i
-
j
∑
h
=
k
i
+
1
n
i
‍
a
i
j
+
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
-
1
‍
∑
h
=
j
+
1
n
i
‍
2
j
-
1
-
n
i
+
∑
h
=
j
+
1
n
i
‍
2
h
-
1
-
n
i
1
+
γ
+
b
×
1
+
b
h
-
j
-
1
∑
h
=
j
+
1
n
i
‍
a
i
[
j
]
+
∑
i
=
1
m
‍
n
i
-
1
a
i
[
n
i
]
=
∑
i
=
1
m
‍
∑
j
=
k
i
+
1
n
i
‍
2
j
-
1
-
n
i
1
+
γ
μ
+
∑
i
=
1
m
‍
∑
j
=
1
n
i
‍
w
i
j
a
i
[
j
]
,where(14)wij=2j-1-ni+∑h=j+1ki‍2h-1-ni1+γ+b1+bh-j-1+∑h=ki+1ni‍2h-1-ni1+γ1+σ1+bki-j,i=1,2,…,m,j=1,2,…,ki,2j-1-ni+∑h=j+1ni‍2h-1-ni1+γ+b1+bh-j-1,i=1,2,…,m,j=ki+1,ki+2,…,ni-1,ni-1,i=1,2,…,m,j=ni.Since∑i=1m‍∑j=ki+1ni(2j-1-ni)(1+γ)μ is a constant, when ni and ki are given, ∑i=1m‍∑j=1niwijai[j] can be viewed as the scalar product of the wij vector and ai[j] vector. Similar to the above analysis, the time complexity of scheduling algorithm on machine Mi is O(nilogni). Together with Lemma 1, we obtain the following theorem.Theorem 5.
The problemPm|qpsd,pi[j]=ai[j]+bt,ma|∑TADCi can be solved in O(n2m-1nlogn) time.


## 4. Conclusions

In this paper we study parallel-machine scheduling problems with past-sequence-dependent (psd) delivery times and aging maintenance. The delivery time of a job is proportional to its waiting time. Each machine has an aging maintenance activity. Polynomially solvable problems have been explored for parallel-machine scheduling. The research extends the existed models of parallel machine scheduling with delivery times. For future research, it will be worth extending the problem to multiple maintenances or flow-shop environment.



---

*Source: 865978-2015-07-27.xml*