# Flowshop Scheduling Problems with a Position-Dependent Exponential Learning Effect

Authors: Mingbao Cheng
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We consider a permutation flowshop scheduling problem with a position-dependent exponential learning effect. The objective is to minimize the performance criteria of makespan and the total flow time. For the two-machine flow shop scheduling case, we show that Johnson’s rule is not an optimal algorithm for minimizing the makespan given the exponential learning effect. Furthermore, by using the shortest total processing times first (STPT) rule, we construct the worst-case performance ratios for both criteria. Finally, a polynomial-time algorithm is proposed for special cases of the studied problem.


---

## Body

## 1. Introduction

Many researchers have studied flowshop scheduling problems under various assumptions and with different objective functions. Minimizing the makespan of the classical flowshop is known to be an NP-hard problem except for Johnson’s [1] two-machine case. Dannenbring [2], Gonzalez and Sahni [3], Smutnicki [4], and Cepek et al. [5] have developed approximation algorithms for some special cases of m-machine flowshop problems.In traditional machine scheduling theory, the processing time of a job is independent of its processed position. However, due to workers’ learning ability, working attitude, and their continuously improved skills with the passage of time, the processing time of a job is shorter if it is scheduled later in the production sequence. This phenomenon is known as a learning effect, which has been employed in management science since its discovery by Wright [6]. Although the learning theory was first applied to industry more than 70 years ago, it remains an interesting important topic in scheduling research. Biskup [7] and Cheng and Wang [8] investigated the effect of learning in the framework of scheduling. Since then, scheduling with learning effect has received growing attention. Mosheiov [9] investigated Biskup’s learning effect model in various scheduling problems and through several examples showed that the optimal schedule is very different from that of the classical versions. Mosheiov and Sidney [10] considered a single-machine scheduling problem with job-dependent learning effects with objectives such as makespan and total flow time, which are proved to be polynomial-time solvable. Bachman and Janiak [11, 12] investigated several single machine scheduling problems with position-dependent processing time.Many researchers have extended several kinds of learning effect model in machine scheduling problems. Wang [13] studied flowshop scheduling problems with job processing times dependent on their positions and suggested Johnson’s rule as a heuristic algorithm to analyze the worst-case ratio of the makespan and special cases of m-machine flowshop. Wang and Xia [14] and Xu et al. [15] extended Biskup’s learning effect to minimize makespan and the total completion time in a flowshop setting. Biskup [16] provided an extensive review of scheduling with learning effects. Janiak and Rudek [17] considered a learning effect model in which the learning curve is S-shaped and provided NP-hard proofs for two cases of the problem to minimize the makespan. S.-J. Yang and D.-L. Yang [18] investigated a single-machine scheduling with a position-dependent aging effect described by a power function and variable maintenance duration. Li and Hsu [19] considered the case of two agents competing for a common single machine with learning effect. Lee et al. [20] studied a uniform parallel machine problem to jointly find an optimal assignment of operators to machines and an optimal schedule to minimize the makespan. Jiang et al. [21] introduced an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. Wu et al. [22] proposed two truncated learning models in single-machine scheduling problems. The related literature also includes Koulamas and Kyparisis [23], Mosheiov [24], Janiak et al. [25], Lee and Wu [26], Huang et al. [27], Zhang and Yan [28], Koulamas [29], J.-B. Wang and J.-J. Wang [30], and Kuo [31] and further references.We know that the modelpjr=pjrα is proposed by Biskup [16], the effect for the given job processed in different positions is not stable; that is, if job Jj is processed at rth and (r+1)th position, respectively, then pjr+k/pjr=((r+1)/r)α, and the processing time decreases quickly if α<0 and far from zero. However, in many realistic settings, the learning process of workers should be stable, which is of utmost importance to guarantee the quality of the product. Therefore, we propose a position-dependent exponential learning effect model pjr=pjαr-1, where α∈(0,1] is a learning index. In such model, the processed position effect for a given job in some schedule is a constant because of pjr+k/pjr=α, and the processing time decreases slowly if α is near 1, and the proposed learning effect model can reflect reasonably the stability of the manufacturing process.In this paper, we study permutation flowshop scheduling problems with a position-dependent exponential learning effect to minimize one of the following two regular performance criteria: makespan and the total flow time. An example is constructed to show that the classical Johnson rule is not optimal for the two-machine case with minimizing makespan under such a position-dependent exponential learning effect. We use the shortest total processing time first (STPT) rule (Dannenbring [2]) to solve our problem and obtain the same worst-case performance ratio for both criteria and prove this performance ratio to be tight. Furthermore, a polynomial-time algorithm is proposed for two special cases: identical processing times on all the machines for any given jobs and the flowshop scheduling problem with dominant machines.The rest of the paper is organized as follows. In Section2, we formalize the problem. We develop the worst-case performance ratios of the STPT algorithm and use it to solve our problem in Section 3. In Section 4, we analyze several special cases and prove that all the problems are solvable in polynomial time. Finally, concluding remarks are given in Section 5.


## 2. Formulation of the Problem

N
(
J
1
,
J
2
,
…
,
J
n
) jobs are to be processed on an m-machine flowshop. We assume that the normal processing time of job Ji on machine Mj is denoted as pi,j and the actual processing time of job Ji on machine Mj at the rth position is denoted as pi,j,r. Namely, the actual processing time of a job is characterized by a position-dependent exponential function: pi,j,r=pi,jαr-1, i=1,2,…,m; r,j=1,2,…,n, where α∈(0,1] denotes the common learning index for all jobs. The aim in this paper is to find a schedule so that n jobs should be processed on the m machines to minimize a given objective function.For a given scheduleσ, Ci(σ) represents the completion time of job Ji, Cmax(σ)=max{Ci(σ)∣i=1,2,…,n} denotes the makespan, and σ=([1],[2],…,[n]) denotes a schedule, where [r] denotes a job that occupies the rth position in σ. In the remaining part of this paper, all problems considered are denoted by the three-field notation scheme α|β|γ introduced by Graham et al. [32]; that is, Fm∣pi,j,r=pi,jαr-1∣f(σ), where f(σ)∈{Cmax,∑‍Ci}.


## 3. Worst-Case Ratio for the General Case

It is well known that problemsFm∣pi,j,r=pi,jαr-1∣Cmax(m≥3) and Fm∣pi,j,r=pi,jαr-1∣∑‍Cj(m≥2) are all strong NP-hard (Garey and Johnson [33]) even for α=1. Johnson [1] proved that F2∥Cmax can be optimally solved by Johnson’s rule. However, in the following example, we show that this policy is not optimal for problem F2∣pi,j,r=pi,jαr-1∣Cmax, where 0<α≤1 is a constant learning index.Example 1.
Letn=3, m=2, p1,1=2, p1,2=3, p2,1=1, p2,2=20, p3,1=7, p3,2=5, and learning index α=0.85. The schedule given by Johnson’s rule is (J2,J1,J3) with the value Cmax=27.16. However, the optimal permutation schedule is (J1,J2,J3), and the optimal value Cmax*=25.61.Before analyzing the worst-case ratio of the problems, we provide two lemmas. By simple interchange technique, the following results can be easily obtained.Lemma 2.
For problem1∣pi,r=piαr-1∣Cmax, an optimal schedule can be obtained by shortest processing time first (SPT) rule.Lemma 3.
For problem1∣pi,r=piαr-1∣∑‍Cj, an optimal schedule can be obtained by SPT rule.In the following, we turn our attention to obtain quasi-optimal schedule. For theFm∥∑‍Cj problem, Dannenbring [2] gave the approximation algorithm shortest total processing time first (STPT) (a nondecreasing order of {Lj}(Lj=∑i=1m‍pi,j)) and showed that it has worst-case performance ratio m.Similarly, we use the STPT rule to construct an approximate algorithm for problemFm∣pi,j,r=pi,jαr-1∣Cmax.Theorem 4.
Ifσ* is an optimal schedule and σ is an STPT schedule for Fm∣pi,j,r=pi,jαr-1∣Cmax, then Cmax(σ)/Cmax(σ*)≤m, and the bound is tight.Proof.
Without loss of generality, we assume thatL1≤L2≤⋯≤Ln. Let Ci(σ) be the completion time of job Ji in schedule σ; then we have Ci(σ)≤∑j=1i‍Ljαj-1 and subsequently Cmax(σ)≤∑j=1n‍Ljαj-1. Let σ*=(J[1],J[2],…,J[n]) be the optimal schedule. We will have Cmax(σ*)≥(∑j=1n‍L[j]αj-1)/m; hence, Cmax(σ*)≥(∑j=1n‍L[j]αj-1)/m≥(∑j=1n‍Ljαj-1)/m, and the term (∑j=1n‍L[j]αj-1)/m is minimized by the nondecreasing order of Lj (Lemma 2 corresponding to the last machine). Therefore, we have Cmax(σ)/Cmax(σ*)≤m.
We show that the bound is tight for the following example. Assume that there arem jobs J1,J2,…,Jm with normal processing times pi,i=t,pi,j=ε(ε≪t),(i≠j=1,2,…,m), and the learning index 0<α≤1. Since Lj=∑i=1m‍pi,j=t+(m-1)ε for all jobs, the proposed heuristic may schedule the jobs in any order. Suppose that we process the jobs in the order of (J1,J2,…,Jm) on all machines. The makespan of σ is Cmax(σ)=t((1-αm)/(1-α))+ε((1-αm-1)/(1-α)). The optimal schedule is σ*=(Jm,Jm-1,…,J1), and the makespan of σ* is Cmax(σ*)=t+(m-2)ε+ε((1-αm-1)/(1-α)). Hence, Cmax(σ)/Cmax(σ*)→m(α→1), and this bound is tight.Similarly, we can use the STPT rule to put together an approximation algorithm for problemFm∣pi,j,r=pi,jαr-1∣∑‍Ci.Theorem 5.
Letσ* be an optimal schedule, and let σ be the STPT schedule for Fm∣pi,j,r=pi,jαr-1∣∑‍Ci; then ∑‍Ci(σ)/∑‍Ci(σ*)≤m, and the bound is tight.Proof.
Without loss of generality, we assume thatL1≤L2≤⋯≤Ln. Let Ci(σ) be the completion time of job Ji in the STPT schedule σ; then Ci(σ)≤∑j=1i‍Ljαj-1 and ∑‍Ci(σ)≤∑i=1n‍∑j=1i‍Ljαj-1. Let σ*=(J[1],J[2],…,J[n]) be the optimal schedule. For σ*, we have C[i](σ*)≥(∑j=1i‍L[j]αj-1)/m; hence
(1)∑‍Ci(σ*)≥∑i=1n‍∑j=1i‍L[j]αj-1m≥∑i=1n‍∑j=1i‍Ljαj-1m,
while the term (∑i=1n‍∑j=1i‍Ljαj-1)/m is minimized by the nondecreasing order of {Lj} (Lemma 3 corresponding to the last machine). Consequently, we have that ∑‍Ci(σ)/∑‍Ci(σ*)≤m.
We now show that the bound is tight. Assume that there arem machines and mn jobs J1,J2,…,Jmn with processing times p1,j=1, pi,j=ε, ε≪1, i=2,…,m, j=1,2,…,n; p1,j=pi,j=ε, p2,j=1, i=3,…,m, j=n+1,n+2,…,2n; pi,j=ε, pi,j=1, i=1,…,m-1, j=(m-1)n+1,(m-1)n+2,…,mn, and the learning index 0<α≤1. Since Lj=∑i=1m‍pi,j=1+(m-1)ε for all jobs, our heuristic may schedule the jobs in any order. Suppose that we arrange the jobs in the order of σ=(J1,J2,…,Jmn) on m machines. The cost of the schedule is ∑‍Ci(σ)=mn/(1-α)-α(1-αmn)/(1-α)2+o(ε). However, the optimal schedule σ* is such a one in which the jobs are executed in the order of (J(m-1)n+1,J(m-2)n+1,…,Jn+1,J1,J(m-1)n+2,…,Jn+2,J2,…,Jmn,…,Jn), and the cost is Ci(σ*)=mn/(1-α)-mα(1-αn)/(1-α)2+o(ε). Hence, ∑‍Ci(σ)/∑‍Cj(σ*)=(mn/(1-α)-α(1-αmn)/(1-α)2+o(ε))/(mn/(1-α)-mα(1-αn)/(1-α)2+o(ε)). As α approximates 1, we have limα→1(∑‍Ci(σ)/∑‍Ci(σ*))=(mn+1)/(n+1)≈m.


## 4. Special Cases Solvable in Polynomial Time

We now consider the special case where a job has the same processing times on all machines for any given job; that is,pi,j=pi. We know that for the Fm∣pi,j=pi∣Cmax problem, the completion time of J[i] is C[i](σ)=∑k=1i‍p[k]+(m-1)max{p[1],p[2],…,p[i]} (Pinedo [34]), where σ denotes a schedule and [i] denotes the job that occupies the ith position in σ. Hence, for the Fm∣pi,j,r=piαr-1∣Cmax problem, the completion time C[i] of J[i] is
(2)C[i](σ)=∑k=1i‍p[k]αk-1+(m-1)max{p[1]α0,p[1]α1,…,p[i]αi-1}.Theorem 6.
For problemFm∣pi,j,r=piαr-1∣Cmax, an optimal schedule can be obtained by the SPT rule.Proof.
Consider a scheduleσ. Suppose that job J[i] occupy the ith position in σ and that p[i] is defined accordingly. The schedule σ′ is obtained from the schedule σ by swapping jobs J[i] and J[i+1]. Assume that the schedule σ, in which p[i]>p[i+1], is optimal. The difference in makespan for the two schedules is given as follows:
(3)Cmax(σ)-Cmax(σ′)=p[i]αi-1+p[i+1]αi+(m-1)×max{p[1],p[2]α,…,p[i]αi-1,p[i+1]αi,…,p[n]αn-1}-p[i+1]αi-1-p[i]αi-(m-1)×max{p[1],p[2]α,…,p[i+1]αi-1,p[i]αi,…,p[n]αn-1}=(p[i]-p[i+1])(αi-1-αi)+(m-1)×(max{p[1],p[2]α,…,p[i]αi-1,p[i+1]αi,…,p[n]αn-1}-max{p[1],p[2]α,…,p[i+1]αi-1,p[i]αi,…,p[n]αn-1}).
Since
(4)p[i]>p[i+1],0<α≤1,p[i]αi-1>p[i+1]αi-1,p[i]αi-1>p[i]αi,
we have
(5)max{p[1],p[2]α,…,p[i]αi-1,p[i+1]αi,…,p[n]αn-1}-max{p[1],p[2]α,…,p[i+1]αi-1,p[i]αi,…,p[n]αn-1}≥0.
That is, Cmax(σ)>Cmax(σ′), which contradicts our assumption that σ is an optimal schedule. Therefore, the schedule obtained by using the SPT rule is optimal.Theorem 7.
For problemFm∣pi,j,r=pjαr-1∣∑‍Cj, an optimal schedule can be obtained by the SPT rule.Proof.
The proof is similar to that of Theorem6 and is omitted.We now consider another special case. Assume that the flowshop has dominant machines. Following Ho and Gupta [35], machine Mr is dominated by Mk, or Mk dominates Mr iff min{pi,k∣i=1,2,…,n}≥max{pi,r∣i=1,2,…,n} (denoted by Mk>Mr). Refer to van den Nouweland et al. [36] and Cepek et al. [5] for such special cases.For the dominant machine case, we form the machine in an increasing sequence of dominating machines (idm); that is, M1<M2<⋯<Mm. Recall that for the Fm|idm|f(σ) problem with f(σ) measure, the schedule σ=(J[1],J[2],…,J[n]) has the completion time C[i] of job J[i] equal to C[i]=∑j=1m-1‍p[1],j+∑k=1i‍p[k],m (Pinedo [34]). Therefore, for the Fm∣pi,j,r=pi,jαr-1,idm∣f(σ) problem, the completion time C[i] of job J[i] is
(6)C[i]=∑j=1m-1‍p[1],j+∑k=1i‍p[k],mαk-1.
Therefore, an optimal algorithm can be developed as follows.Algorithm  AStep  1. Construct the SPT sequence (J[1],J[2],…,J[n]) of processing time pi,m,i=1,2,…,n, on machine Mm. That is, p[1],m≤p[2],m≤⋯≤p[n],m.Step  2. Let σi=(J[i],J[1],J[2],…,J[i-1],J[i+1],…,J[n]). Compute f(σi).Step  3. Let f(σi*)=min{f(σi)∣i=1,2,…,n}; then an optimal schedule is σi*=(J[i*],J[1],J[2],…,J[i*-1],J[i*+1],…,J[n]).Theorem 8.
For problemFm∣pi,j,r=pi,jαr-1,idm∣Cmax, the schedule generated by Algorithm A is optimal.Proof.
For any feasible solutionσ′=(J[1]′,J[2]′,…,J[i-1]′,J[i]′,J[i+1]′,…,J[n]′), let J[1]′=J[k], where J[k] is the kth element of σ=(J[1],J[2],…,J[i-1],J[i],J[i+1],…,J[n]) obtained by Step  1 of Algorithm A. We have
(7)Cmax(σ′)=∑i=1m-1‍p[1]′,i+∑i=1n‍p[i]′,mαi-1=∑i=1m-1‍p[k],i+∑i=1n‍p[i]′,mαi-1≥∑i=1m-1‍p[k],i+∑i=1k-1‍p[i],mαi+∑i=k+1n‍p[i],mαi-1=Cmax(σk)≥Cmax(σj*).
This completes the proof.Algorithm A requiresO(mn), and the computation of an SPT schedule needs O(nlogn), so the computation of f(σj*) needs O(mn).From (6), we have ∑i=1nC[i]=∑i=1n∑k=1m-1p[1],k+∑i=1n∑k=1ip[k],mαk-1, where the first term is only dependent on job J[1], while the second term is the total flow-time of all the jobs on machine Mm and is minimized by the SPT rule (Lemma 3). Therefore, an optimal schedule can be constructed for the problem Fm∣pi,j,r=pi,jαr-1∣∑‍Cj by Algorithm A.Theorem 9.
For problemFm∣pi,j,r=pi,jαr-1,idm∣∑‍Cj, the schedule generated by Algorithm A is an optimal one.Proof.
The proof is similar to that of Theorem8 and is omitted.


## 5. Conclusion

In order to overcome the lack of stability in Biskups model in a manufacturing setting, we focus on flowshop scheduling problems with position-dependent exponential learning effect to minimize the makespan and the total flow time. For the two-machine case, we show that Johnson’s algorithm does not obtain optimal result. We thus develop the worst-case ratios of the STPT algorithm to minimize the makespan and the total flow time, respectively, and empirically prove that both bounds are tight by several examples. Finally, for special cases, we show that the problems remain polynomially solvable.Notice that the complexity of the studied problem remains unreciprocated and the worst-case ratios we developed heavily depend on the number of machines. The dependency of machine number in the flowshop is a limitation of our algorithm as it may create notable discrepancy between the optimal solution and that derived by our method. Therefore, our future research includes proving the complexity of the flowshop scheduling problem with position-dependent exponential learning effect and developing generalizable and effective algorithms for diverse problems.



---

*Source: 753123-2013-09-10.xml*