# Scheduling Jobs with Variable Job Processing Times on Unrelated Parallel Machines

Authors: Guang-Qian Zhang; Jian-Jun Wang; Ya-Jing Liu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

m unrelated parallel machines scheduling problems with variable job processing times are considered, where the processing time of a job is a function of its position in a sequence, its starting time, and its resource allocation. The objective is to determine the optimal resource allocation and the optimal schedule to minimize a total cost function that dependents on the total completion (waiting) time, the total machine load, the total absolute differences in completion (waiting) times on all machines, and total resource cost. If the number of machines is a given constant number, we propose a polynomial time algorithm to solve the problem.


---

## Body

## 1. Introduction

In classical scheduling theory, it is assumed that the job processing times are fixed and constant values. In practice, however, we often encounter settings in which job processing times may be subject to change due to the deterioration effects and/or learning effects and/or controllable processing times. Extensive surveys of different scheduling models and problems involving deteriorating jobs can be found in Alidaee and Womer [1], Cheng et al. [2], and Gawiejnowicz [3]. A recent survey of the scheduling problems with learning effects could be found in Biskup [4]. A recent survey of the scheduling problems with controllable processing times was given by Shabtay and Steiner [5]. More recent papers that have considered scheduling problems with deterioration effects and/or learning effects and/or controllable processing times include Bai et al. [6, 7], Cheng et al. [8], Gorczyca and Janiak [9], Hsu and Yang [10], Huang and Wang [11], Lee et al. [12], Leyvand et al. [13], Nian and Mao [14], Shabtay and Steiner [15], Wang et al. [16], J. B. Wang and M. Z. Wang [17], J. B. Wang and J. J. Wang [18], Wang et al. [19–21], Wei et al. [22], Wu and Lee [23], Wu and Liu [24], Yang and Kuo [25], S. J. Yang and D. L. Yang [26], Yang et al. [27], Yin et al. [28–31], and Zhao and Tang [32]. Mosheiov and Sidney [33] considered the single machine model:
(1)pj=ajrbj,
where aj is the original (normal) processing time of job Jj, pj is the actual processing time of job Jj, r is the position of job Jj when scheduled on the machine, and bj≤0 is the job-dependent learning index of job Jj. Yang and Kuo [25] considered single machine scheduling with the deterioration and learning effect in which the job processing times are
(2)pj=ajrb+αt,
where t is the starting time of job Jj, b≤0 is a learning index, and α≥0 is a common deterioration rate for all the jobs. Shabtay and Steiner [15] considered single machine scheduling with the resource allocation model in which the job processing times are
(3)pj=aj-βjuj,
where uj is the amount of a nonrenewable resource allocated to job Jj, with 0≤uj≤u-j<aj/βj, where u-j denote the maximum amount of resource allocated to job Jj and βj is the positive compression rate of job Jj.Wang et al. [19] considered single machine scheduling problem where the job processing time is a function of position in a sequence, starting time, and resource allocation to this job on a single machine; that is, the model
(4)pj=ajrb+αt-βjuj,
where 0≤uj≤u-j<ajnb/βj. For minimizing a cost function containing makespan, total completion (waiting) time, total absolute differences in completion (waiting) times, and total resource cost, they proved that the problem can be solved in polynomial time.Wang et al. [19] considered single machine scheduling problem with effect of deterioration, learning, and resource allocation simultaneously. The example of the phenomena of deterioration, learning effect, and resource allocation occurring simultaneously can be found in Wang et al. [19]. However, the parallel machine scheduling is interesting and closer to real problems in practice (Cheng et al. [8], Hsu and Yang [10], Huang and Wang [11], Yang et al. [27], and Yin et al. [30]). This paper extends the single machine scheduling results of Wang et al. [19], by considering unrelated parallel machine scheduling problems that include the one given in Wang et al. [19] as a special case. The remainder of this paper is organized as follows. In Section 2 we formulate the model. In Sections 3 and 4, we show that the problem can be solved in polynomial time for two different cost functions. The last section contains some conclusions.


## 2. Problem Formulation

The model is described as follows. There aren independent jobs {J1,J2,…,Jn} to be processed on m unrelated parallel machines {M1,M2,…,Mm}. Each of them is available at time 0. The machine can handle one job at a time, and preemption is not allowed. Let ni denote the number of jobs assigned to Mi(i=1,2,…,m) and P(n,m)=(n1,n2,…,nm) denote a job-allocation vector, where (n1+n2+⋯nm=n). We assume, as in most practical situations, that m<n and m are a given constant. Each job can be processed on any one of the m unrelated parallel machines. Associated with each job Jj(j=1,2,…,n) on machine Mi, there is a normal processing time aij. Let pij denote the actual processing time for job Jj on machine Mi. In this paper, we consider a general unrelated parallel machines model stemming from Yang and Kuo [25], Shabtay and Steiner [15], and Wang et al. [19]; that is,
(5)pij=aijrbij+αt-θijuij,
where r is the position of job Jj when scheduled on machine Mi, t is the starting time of job Jj on machine Mi, bij≤0 is a job-dependent learning index, α≥0 is a common deterioration rate for all the jobs, θij≥0 is the positive compression rate of job Jj on machine Mi, and uij is the amount of resource that can be allocated to job Jj on machine Mi, with 0≤uij≤u-ij<aijnbij/θij, where u-ij is the upper bound on the amount of resource that can be allocated to job Jj on machine Mi.LetJi[j] denote the jth job on machine Mi and Ci[j](Wi[j]) denote the completion (waiting) time of job Ji[j]; pi[j], ai[j], bi[j], θi[j], ui[j], and u-i[j] are defined similarly, where Wi[j]=Ci[j]-pi[j]. Let Li=max⁡{Cij∣j=1,2,…,ni}, TCi=∑j=1ni‍Cij (TWi=∑j=1ni‍Wij), and TADCi=∑j=1ni‍∑l=jni‍|Cij-Cil| (TADWi=∑j=1ni‍∑l=jni‍|Wij-Wil|) be the load, the total completion (waiting) times, and the total absolute differences in completion (waiting) times of machine Mi. Then, the total machine load, the total completion (waiting) time, and the total absolute deviation of job completion (waiting) time on all machines are ∑i=1m‍Li, ∑i=1m‍TCi (∑i=1m‍TWi), and ∑i=1m‍TADCi (∑i=1m‍TADWi), respectively. The objective is to determine the optimal resource allocations and the optimal schedule on the machines so that the corresponding value of the following cost functions is optimal:
(6)Z1(π,u)=α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m∑j=1ni‍Gijuij,(7)Z2(π,u)=α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m∑j=1ni‍Gijuij,
where weights α1≥0, α2≥0, α3≥0, and α4≥0 are given constants and Gij is the per time unit cost associated with the resource allocation. Using the three-field notation introduced by Graham et al. [34], the corresponding scheduling problem is denoted by Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij and Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij.


## 3. ProblemRm|pij = aijrbij + αt − θijuij|α1∑i=1m‍Li + α2∑i=1m‍TCi + α3∑i=1m‍TADCi + α4∑i=1m‍∑j=1ni‍Gijuij

If the number of jobs on machineMi is known in advance, from Wang et al. [19], we have
(8)Ci[j]=∑l=1j(1+α)j-l(ai[l]lbi[l]-βi[l]ui[l]),pi[j]=ai[j]jbi[j]-βi[j]ui[j]+α∑l=1j-1(1+α)j-1-l(ai[l]lbi[l]-βi[l]ui[l]).From Kanet [35], we have TADCi=∑j=1ni‍(j-1)(ni-j+1)pi[j]; in addition, Ci[j]=∑l=1j‍pi[l], Li=∑j=1ni‍pi[j], and TCi=∑j=1ni‍Ci[j]=∑j=1ni‍(ni-j+1)pi[j]; hence, we have
(9)Z1(π,u)=α1∑i=1m‍∑j=1ni‍pi[j]+α2∑i=1m‍∑j=1ni‍(ni-j+1)pi[j]+α3∑i=1m‍∑j=1ni‍(j-1)(ni-j+1)pi[j]+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍∑j=1ni‍[α1+α2(ni+1-j)+α3(j-1)(ni-j+1)]pi[j]+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍∑j=1ni‍ωijpi[j]+α4∑i=1m∑j=1ni‍Gi[j]ui[j]=∑i=1m‍∑j=1ni‍ωij(∑l=1j-1‍ai[j]jbi[j]-βi[j]ui[j]0000000000000+α∑l=1j-1‍(1+α)j-1-l(ai[l]lbi[l]-βi[l]ui[l]))+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍[(ai[ni-2](ni-2)bi[ni-2])))ωi1(ai[1]1bi[1]-βi[1]ui[1])000000+ωi2(ai[2]2bi[2]-βi[2]ui[2]0000000000000+α(ai[1]1bi[1]-βi[1]ui[1]))000000+ωi3(ai[3]3bi[3]-βi[3]ui[3]0000000000000+α(ai[2]2bi[2]-βi[2]ui[2]+(1+α)000000000000000000×(ai[1]1bi[1]-βi[1]ui[1])))000000+ωi4(ai[4]4bi[4]-βi[4]ui[4]000000000000+α(ai[3]3bi[3]-βi[3]ui[3]+(1+α)0000000000000000×(ai[2]2bi[2]-βi[2]ui[2])0000000000000000+(1+α)2(ai[1]1bi[1]-βi[1]ui[1])))+⋯000000+ωi,ni-1(ai[ni-1](ni-1)bi[ni-1]-βi[ni-1]ui[ni-1]00000000000000+α(ai[ni-2](ni-2)bi[ni-2]000000000000000000-βi[ni-2]ui[ni-2]+(1+α)000000000000000000×(ai[ni-3](ni-3)bi[ni-3]0000000000000000000000-βi[ni-3]ui[ni-3](ni-3)bi[ni-3])+⋯000000000000000000+(1+α)ni-4(ai[2]2bi[2]-βi[2]ui[2])000000000000000000+(1+α)ni-3(ai[1]1bi[1]-βi[1]ui[1])ai[ni-3](ni-3)bi[ni-3]))000000+ωini(ai[ni]nibi[ni]-βi[ni]ui[ni]0000000000000+α(ai[ni-1](ni-1)bi[ni-1]-βi[ni-1]ui[ni-1]00000000000000000+(1+α)(ai[ni-2](ni-2)bi[ni-2]00000000000000000000000000-βi[ni-2]ui[ni-2]ai[ni-2](ni-2)bi[ni-2])+⋯00000000000000000+(1+α)ni-3(ai[2]2bi[2]-βi[2]ui[2])00000000000000000+(1+α)ni-2(ai[1]1bi[1]-βi[1]ui[1])ai[ni-2](ni-2)bi[ni-2]))]+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍[(ai[ni]nibi[ni]-βi[ni]ui[ni])(ωi1+αωi2+α(1+α)ωi3+⋯+α(1+α)n-2ωini)000000×(ai[1]1bi[1]-βi[1]ui[1])000000+((1+α)ni-3ωiniωi2+αωi3+α(1+α)ωi4+⋯000000000+α(1+α)ni-3ωini)(ai[2]2bi[2]-βi[2]ui[2])000000+((1+α)ni-3ωiniωi3+αωi4+α(1+α)ωi5+⋯000000000+α(1+α)ni-4ωini)(ai[3]3bi[3]-βi[3]ui[3])000000+⋯+(ωi,ni-1+αωini)(ai[ni-1]-βi[ni-1]ui[ni-1])000000+ωini(ai[ni]nibi[ni]-βi[ni]ui[ni])]+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍∑j=1ni‍Ωijai[j]jbi[j]+∑i=1m‍∑j=1ni‍(α4Gi[j]-βi[j]Ωij)ui[j],
where ωij=α1+α2(ni+1-j)+α3(j-1)(ni-j+1) and
(10)Ωi1=ωi1+αωi2+α(1+α)ωi3+⋯+α(1+α)ni-2ωini,Ωi2=ωi2+αωi3+α(1+α)ωi4+⋯+α(1+α)ni-3ωini,Ωi3=ωi3+αωi4+α(1+α)ωi5+⋯+α(1+α)ni-4ωini,⋮Ωi,ni-1=ωi,ni-1+αωini,Ωini=ωini.From (9), for any given sequence on all machines, the optimal resource allocation on all machines can be obtained by the following.Lemma 1.
For a given sequence, the optimal resource allocation of the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij can be determined by
(11)ui[j]*={u-i[j],ifα4Gi[j]-βi[j]Ωij<0,ui[j]∈[0,u-i[j]],ifα4Gi[j]-βi[j]Ωij=0,0,ifα4Gi[j]-βi[j]Ωij>0,
where ui[j]*,i=1,2,…,m;j=1,2,…,ni, represents the optimal resource allocation of the job in position j on machine Mi.Proof.
For the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij, taking the derivative by ui[j] to (9), we have df(π,u)/ui[j]=α4Gi[j]-βi[j]Ωij for i=1,2,…,m;j=1,2,…,ni. Hence, if α4Gi[j]-βi[j]Ωij>0, we should not allocate any resource to job Ji[j]; if α4Gi[j]-βi[j]Ωij<0, we will allocate the maximal feasible amount of resource to job Ji[j]; and if α4Gi[j]-βi[j]Ωij=0, any feasible resource allocation can be optimal.We definexijr=1 if job Jj is scheduled in position r on machine Mi, and xijr=0 otherwise. If the number of jobs on machine Mi is known in advance, then we formulate the Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij problem as the following assignment problem:
(12)Min⁡Z=∑i=1m‍∑r=1ni‍∑j=1n‍λijrxijr
subject to
(13)∑i=1m‍∑r=1ni‍xijr=1,j=1,2,…,n,(14)∑j=1n‍xijr=1,i=1,2,…,m;r=1,2,…,ni,(15)xijr=0or1,i=1,2,…,m;r=1,2,…,ni;j=1,2,…,n,
where
(16)λijr={Ωiraijrbij,ifα4Gij-βijΩir≥0,Ωiraijrbij+(α4Gij-βijΩir)u-ij,ifα4Gij-βijΩir<0.
Constraint (13) makes sure that each job is scheduled exactly once. Constraint (14) makes sure that each position on each machine is taken by one job.Next, the question is how manyP(n,m)=(n1,n2,…,nm) vectors exist. Note that ni may be 0,1,2,…,n for i=1,2,…,m. So, if we get the numbers of jobs on the first m-1 machines, the number of jobs processed on the last machine is then determined uniquely due to n1+n2+⋯+nm=n. Therefore, the upper bound of the number of P(n,m) vectors is (n+1)m-1. Based on the above analysis, we have the following result.Theorem 2.
The problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij can be solved in O(nm+2) time; that is, the problem is polynomially solvable because m is a constant.Base on the above analysis, we can determine the optimal solution for the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij via the following algorithm.Algorithm 3.
Consider the following.
Step  1. For all the possible vectors (n1,n2,…,nm), solve the assignment problems ((12)–(16)). Then, obtain the optimal schedule and the corresponding total cost α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij for each possible vector (n1,n2,…,nm).
Step  2. The optimal solution for the problem is the one with the minimum value of the total cost α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij.
Step  3. Calculate the optimal resources allocation by using (11).The following example illustrates the working of Algorithm3 for the problem Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij.Example 4.
Data.
n
=
4, m=2, α=0.05, and α1=α2=α3=α4=1, and the other corresponding parameters are shown in Table 1.Table 1
The date of Example4.
J
j
J
1
J
2
J
3
J
4
a
1
j
16
20
18
14
a
2
j
17
19
20
12
b
1
j
−0.35
−0.21
−0.25
−0.31
b
2
j
−0.23
−0.31
−0.27
−0.25
θ
1
j
2
3
4
5
θ
2
j
4
5
2
3
u
-
1
j
3
4
3
1
u
-
2
j
3
2
5
2
G
1
j
6
4
2
3
G
2
j
3
7
5
4Solution. When n1=0,n2=4, Ω21=5.9931,Ω22=7.6125,Ω23=7.2500,Ω24=5, then the optimal schedule on machine M2 is [J4,J1,J2,J3] and Z1=155.2178.Whenn1=1,n2=3, Ω11=2,Ω21=4.4600,Ω22=5.2000,Ω23=4, the optimal schedule on machine M1 is [J3] and on machine M2 is [J4,J1,J2], and Z1=102.7967.Whenn1=2,n2=2,Ω11=3.1500,Ω12=3,Ω21=3.1500,Ω22=3, the optimal schedule on machine M1 is [J2,J3] and on machine M2 is [J4,J1], and Z1=99.9928.Whenn1=3,n2=1, Ω11=4.4600,Ω12=5.2000,Ω13=4,Ω21=2, the optimal schedule on machine M1 is [J2,J3,J4] and on machine M2 is [J1], and Z1=115.8243.Whenn1=4,n2=0, Ω11=5.9931,Ω12=7.6125,Ω13=7.2500,Ω14=5, the optimal schedule on machine M1 is [J4,J3,J2,J1], and Z1=168.1833.Hence, the optimal schedule on machineM1 is [J2,J3] and on machine M2 is [J4,J1], u1[1]*=4,u1[2]*=3,u2[1]*=2,u2[2]*=3 and optimal cost is Z1=99.9928.


## 4. ProblemRm|pij = aijrbij + αt − θijuij|α1∑i=1m‍Li + α2∑i=1m‍TWi + α3∑i=1m‍TADWi + α4∑i=1m‍∑j=1ni‍Gijuij

Similar to the analysis of the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij presented in the previous section, if we substitute Wi[j]=∑l=1j-1‍pi[l], TWi=∑j=1ni‍Wi[j], and TADWi = ∑j=1ni‍j(ni-j)pi[j] (Bagchi [36]) into (7), we have
(17)Z2(π,u)=α1∑i=1m‍∑j=1ni‍pi[j]+α2∑i=1m‍∑j=1ni‍(ni-j)pi[j]+α3∑i=1m‍∑j=1ni‍j(ni-j)pi[j]+α4∑i=1m‍∑j=1ni‍Gi[j]ui[j]=∑i=1m‍∑j=1ni‍Ψijai[j]jbi[j]+∑i=1m‍∑j=1ni‍(α4Gi[j]-βi[j]Ψij)ui[j],
where νij=α1+α2(ni-j)+α3j(ni-j),
(18)Ψi1=νi1+ανi2+α(1+α)νi3+⋯+α(1+α)ni-2νini,Ψi2=νi2+ανi3+α(1+α)νi4+⋯+α(1+α)ni-3νini,Ψi3=νi3+ανi4+α(1+α)νi5+⋯+α(1+α)ni-4νini,⋮Ψi,ni-1=νi,ni-1+ανini,Ψini=νini.Applying a similar analysis in the previous section, we have the following results.Lemma 5.
For a given sequence, the optimal resource allocation of the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij can be determined by
(19)ui[j]*={u-i[j],ifα4Gi[j]-βi[j]Ψij<0,ui[j]∈[0,u-i[j]],ifα4Gi[j]-βi[j]Ψij=0,0,ifα4Gi[j]-βi[j]Ψij>0,
where ui[j]*,i=1,2,…,m;j=1,2,…,ni represents the optimal resource allocation of the job in position j on machine Mi.Lemma 6.
For the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1mLi‍+α2TWi+α3TADWi+α4∑i=1m‍∑j=1ni‍Gijuij, if the vector P(n,m)=(n1,n2,…,nm) is given, the optimal sequence can be determined by solving the following assignment problem:
(20)MinZ=∑i=1m‍∑r=1ni‍∑j=1n‍θijrxijrsubjectto(13),(14)and(15),
where
(21)θijr={Ψiraijrbij,ifδ4Gij-βijΨir≥0,Ωiraijrbij+(α4Gij-βijΨir)mij,ifα4Gij-βijΨir<0.Theorem 7.
The problemRm|pij=aijrbij+αt-θijuij|α1∑i=1mLi‍+α2TWi+α3TADWi+α4∑i=1m‍∑j=1ni‍Gijuij can be solved in O(nm+2) time; that is, the problem is polynomially solvable because m is a constant.The optimal solution for the problemRm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2TWi+α3TADWi+α4∑i=1m‍∑j=1ni‍Gijuij can be obtained by the following algorithm.Algorithm 8.
Consider the following.
Step  1. For all the possible vectors (n1,n2,…,nm), solve the assignment problems ((20), (13)–(15), (21)). Then, obtain the optimal schedule and the corresponding total cost α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij for each possible vector (n1,n2,…,nm).
Step  2. The optimal solution for the problem is the one with the minimum value of the total cost α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij.
Step  3. Calculate the optimal resources allocation by using (19).The following example illustrates the working of Algorithm8 for the problem Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij.Example 9.
The same date in Example4 is used.Solution. When n1=0,n2=4, Ψ21=7.6676,Ψ22=7.3025,Ψ23=5.0500,Ψ24=1, then the optimal schedule on machine M2 is [J4,J1,J2,J3] and Z2=126.7347.Whenn1=1,n2=3, Ψ11=1,Ψ21=5.2525,Ψ22=4.0500,Ψ23=1, the optimal schedule on machine M1 is [J3] and on machine M2 is [J4,J1,J2], and Z2=84.13484.Whenn1=2,n2=2, Ψ11=3.0500,Ψ12=1,Ψ21=3.0500,Ψ22=1, the optimal schedule on machine M1 is [J3,J4] and on machine M2 is [J1,J2], and Z2=73.1692.Whenn1=3,n2=1, Ψ11=5.2525,Ψ12=4.0500,Ψ13=1,Ψ21=1, the optimal schedule on machine M1 is [J3,J4,J2] and on machine M2 is [J1], and Z2=95.8810.Whenn1=4,n2=0, Ψ11=7.6676,Ψ12=7.3025,Ψ13=5.0500,Ψ14=1, the optimal schedule on machine M1 is [J4,J3,J2,J1], and Z2=144.1351.Hence, the optimal schedule on machineM1 is [J3,J4] and on machine M2 is [J1,J2], u1[1]*=3,u1[2]*=1,u2[1]*=3,u2[2]*=0 and optimal cost is Z2=73.1692.


## 5. Conclusions

In this paper, we have studied the problem of schedulingn jobs on m unrelated parallel machines with simultaneous consideration of learning effect, deteriorating jobs, and controllable processing times. We provide an O(nm+2) time algorithm for the problems Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TCi+α3∑i=1m‍TADCi+α4∑i=1m‍∑j=1ni‍Gijuij and Rm|pij=aijrbij+αt-θijuij|α1∑i=1m‍Li+α2∑i=1m‍TWi+α3∑i=1m‍TADWi+α4∑i=1m‍∑j=1ni‍Gijuij, respectively. The algorithms can also be easily applied to the cases bij>0 (aging effect) and α<0. Future research may focus on similar problems with more general processing time model and extend the problems to flow shop machine settings.



---

*Source: 242107-2014-05-26.xml*