# Group Scheduling with General Autonomous and Induced Learning Effect

Authors: Jia-zhen Huo; Lei Ning; Li Sun
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

In recent research, induced learning requires management involvement. The initial investment can be interpreted as induced learning via an investment in the creation of technological knowledge or knowledge transfer. Induced learning has received attention in productivity improvement. In this paper, we consider scheduling problems with autonomous and induced learning under group technology. The jobs’ processing times decrease according to a learning rate which conversely increases the investment cost. The objectives of the scheduling problems are to minimize a linear combination of the makespan and the investment cost and a linear combination of the total completion time and the investment cost. We present polynomial algorithms to determine the optimal job sequence, group sequence, and the percentage reduction of the standard learning rate.


---

## Body

## 1. Introduction

Jobs’ actual processing times usually decrease as a result of workers’ improved skill due to repetitive performance of similar jobs. This process is known as the learning effect in the literature. Biskup [1], Wright [2], and Cheng and Wang [3] are among the pioneers that brought the topic of learning into the field of scheduling. Recent studies that consider scheduling with the learning effect include Qian and Steiner [4], Wang and Wang [5], Rudek [6], Liu [7], Shen and Wu [8], Wu et al. [9], Li et al. [10], and Rudek [11]. In the recent literature, a quality improvement of labour due to repetition is the factor in productivity increasing, which is called autonomous learning or learning by doing. As opposed to autonomous learning, which is a by-product of repeating activities, induced learning requires management involvement. The initial investment can be interpreted as induced learning via an investment in the creation of technological knowledge or knowledge transfer. Induced learning has received attention in productivity manufacturing. Nevertheless, it is hardly considered in scheduling. Most existing scheduling models with the learning effect concentrate on autonomous learning, i.e., learning by doing. Zhang et al. [12] considered scheduling problems with autonomous and induced learning. Biskup and Simons [13] investigated scheduling problems with autonomous and induced learning. In addition to these two papers, there is no research, which considers scheduling problems with autonomous and induced learning simultaneously.In many manufacturing processes, production efficiency can be raised by grouping various parts and products with similar designs or requiring similar production processes. This practice is known as group technology in the literature. Many advantages of applying group technology in manufacturing have been observed. Research considering group technology includes Wei and Wang [14], Yang [15], Lee and Wu [16], Bai et al. [17], and Lee and Lu [18].To the best of our knowledge, scheduling with autonomous and induced learning under group technology has not been studied in the literature. The topic pertains to the scope of mathematical problems in engineering. Therefore, we think this paper will arouse reader’s interest. In this paper, we introduce group scheduling problems with autonomous and induced learning. We present that the problems to minimize the weighted sum of the makespan and the investment cost and the weighted sum of the total completion time and the investment cost are polynomially solvable. The remaining part of this paper is organized as follows. In Section2, we formulate the problem and introduce the notation and some lemmas. We then study the problem to minimize the weighted sum of the makespan and the investment cost. In Section 3, we consider the problem to minimize the weighted sum of the total completion time and the investment cost. In the last section, we conclude the paper.


## 2. Problem Formulation

There aren jobs to be classified into m groups, where the number of jobs within each group is ni, i=1,2,…,m. That is to say, a job belonging to a group is decided in advance. All the jobs are ready to be processed on a single machine and are nonpreemptive. Jobs in the same group are processed consecutively and need no setup time. A group setup time is required if the machine switches processing jobs from one group to another. We first define the notation which are used throughout this paper and formulate the problems under study.G[i]: group scheduled in the ith position in a sequence, i=1,2,…,m.ni: the number of jobs in group Gi, i=1,2,…,m.n: the total number of jobs, i.e., n1+n2+n3+⋯+nm=n.si: the normal setup time of group Gi, i=1,2,…,m.si[r]A: the actual setup time of group Gi occupying the rth group position in the sequence, i=1,2,…,m.s[i]A: the actual setup time of group G[i] occupying the ith group position in the sequence, i=1,2,…,m.Ji[j]: the job scheduled in the jth position in group Gi.pij: the basic (normal) processing time of job Jij, i=1,2,…,m, j=1,2,3,…,ni.pi[j]: the basic (normal) processing time of job Ji[j] scheduled in the jth position of group Gi, i=1,2,…,m, j=1,2,3,…,ni.pij[r,k]A: the actual processing time of job Jij scheduled in the rth position of group position and the kth job-position in group Gi, i=1,2,…,m, j=1,2,3,…,ni.In this paper, we study the group scheduling problems under autonomous and induced learning. Following Biskup and Simins (2004), we assume that the actual setup time of groupGi is scheduled in the rth position as follows:(1)sirA=siralog2⁡1-xs,i=1,2,…,m.S is a learning rate; its value needs to be smaller than or equal to one as Biskup and Simins (2004). We consider job processing time model concerning autonomous and induced learning. Following the model in Lee and Wu [19], the actual processing time of job Jij when scheduled in the rth group and in the kth position is(2)pijr,kA=pijralog2⁡1-xskblog2⁡1-xs,i=1,2,…,m,j=1,2,3,…,ni,where x, 0≤x≤xmax<1, is the percentage reduction of the standard learning rate s and 0<s≤1. There is an additional cost k(x) incurred by the effort to achieve x, i.e., the investment cost. So the problem is to make a tradeoff between the original objective function and the investment cost through a proper choice of x. a>0,b>0 are the learning coefficient, which are related to jobs repetition and groups repetition. When a=b=1, it is the model studied in Biskup and Simous (2004). The objectives are to find the optimal job sequence in each group, the optimal group sequence, and the optimal investment cost such that the weighted sum of the makespan and the investment cost is minimized. Let AILE denote the jobs’ autonomous and induced learning. Using the three-field notation for scheduling problems, we denote our problems as (3)1GT,sirA=siralog2⁡1-xs,AILEβ1Cmax+β2kx.We also investigate the problem to minimize the weighted sum of the total completion time and the investment cost under the condition that all the groups have the same number of jobs, i.e., (4)1GT,sirA=siralog2⁡1-xs,AILE,ni=n¯β1∑Cij+β2kx.where β1 and β2 are positive parameters decided by the decision-maker reflecting the relative weights of the two cost components. Before presenting the main results, we first present several lemmas that will be used in the proofs in the sequel.Lemma 1.
IfG(r)=δ(r)rmlog2⁡(1-x)s, m≥1, 0≤x≤xmax<1, r≥1, δ(r)≥1, and δ(r) is a nonincreasing function, then G(r) is nonincreasing function in r.Lemma 2.
Ifh(x)=δ(r)rmlog2⁡(1-x)s, m≥1, r≥1, 0≤x≤xmax<1, δ(r)≥1, and δ(r) is a nonincreasing function, then h(x) is a convex function over the interval [0,xmax].Lemma 3.
Ifρ(x)=δ1(i,j)ialog2⁡(1-x)s+δ2(i,j)ialog2⁡(1-x)sjblog2⁡(1-x)s, a≥1, b≥1, 0≤x≤xmax<1, i≥1, j≥1, δ1(i,j)≥1, δ2(i,j)≥1, and δ1(i,j) and δ2(i,j) are nonincreasing functions with respect to i and j, then ρ(x) is a convex function over the interval [0,xmax].Lemma 4 (Hardy et al. [20]).
Let there be two sequences of numbersxi and yi. The sum ∑ixiyi of products of the corresponding elements is the least (largest) if the sequences are monotonic in the opposite (same) sense.


## 3. The Makespan with the Investment Cost Minimization Problem

In this section we consider the problem1|GT,sirA=siralog2⁡1-xs,AILE|β1Cmax+β2k(x). Our objective is to find the optimal group sequence, the job sequence, and the percentage reduction of the standard learning rate x.For the problem1|GT,sirA=siralog2⁡1-xs,AILE|β1Cmax+β2k(x), by calculation, we obtain the following expression: (5)β1Cmax+β2kx=∑i=1mβ1siialog2⁡1-xs+∑i=1m∑j=1niβ1pijialog2⁡1-xsjblog2⁡1-xs+β2kx.Let f1(x)=∑i=1mβ1s[i]ialog2⁡(1-x)s+∑i=1m∑j=1niβ1pijialog2⁡(1-x)sjblog2⁡(1-x)s and F1(x)=f1(x)+β2k(x). From Lemma 3, we obtain that f1(x) is a convex function over the interval [0,xmax]. Since k(x) is a convex function, F1(x) is also a convex function over the interval [0,xmax]. Hence, for a certain x∈[0,xmax], the optimal sequence does not change (see Biskup and Simons [13]). Based on the above expression, for a certain x∈[0,xmax], the groups sequence does not affect the jobs sequence in each group.LetG1(j)=β1jblog2⁡(1-x)s. From Lemma 1, we see that G1(j) is a nonincreasing function about j. From Lemma 4, for a given group sequence, the optimal internal job sequence can be obtained by assigning pi[j] to the corresponding G1(j) following a well-known result on two vectors given by Hardy et al. [20]. Since G1(j) is a nonincreasing function about j, pi[j] should be a nondecreasing sequence. Therefore, the optimal schedule is obtained by sequencing the jobs in each group in nondecreasing order of pi[j], i.e., pi[1]≤pi[2]≤,…,≤pi[ni],i=1,2,3,…,m (the shortest processing time SPT rule). For a certain x∈[0,xmax], if the internal job sequence in each group is determined, the total cost depends on the group sequence. Consequently, we show that the group sequence is determined by the following assignment problem:AP1MinimizeZ=∑i=1m∑r=1mwirxirs.t.∑i=1mxir=1r=1,2,…,m,∑r=1mxir=1i=1,2,…,m,xir=0or1i=1,2,…,m,r=1,2,…,m.where wir=β1siralog2⁡(1-x)s+∑j=1niβ1pi[j]ralog2⁡(1-x)sjblog2⁡(1-x)s.From the above formulation, the optimalx depends on the sign of the first derivative of F1(x), i.e., F1′(x). If F1′(x) is positive, we should allocate the minimal value to x, i.e., x=0. If F1′(x) is negative, we should allocate the maximal value to x, i.e., x=xmax. If F1′(x) is equal to 0, any value between 0 and xmax will not affect the total cost.Based on the above analysis, we present the following algorithm to solve this problem.Algorithm 5.
Step 1. Arrange the jobs in each group in the SPT order, i.e., (6)pi1≤pi2≤,…,≤pini,i=1,2,…,m.Step 2. Give a value to x, which x∈[0,xmax], schedule the groups by AP1.
Step 3. Take the first derivative of F1(x)
Set(7)x∗=0,ifF1′x>0,xmax,ifF1′x<0,x∈0,xmax,ifF1′x=0.Step 4. Output the optimal job sequence, optimal group sequence, and optimal percentage reduction of the standard learning rate x∗.Step 1 requiresO(∑i=1mnilog⁡ni)=O(nlog⁡n) time. Step 2 is executed in O(m3). Therefore, the complexity of Algorithm 5 is at most O(n3). Thus, we have obtained the following result.Theorem 6.
The1|GT,sirA=siralog2⁡1-xs,AILE|β1Cmax+β2k(x) problem is solvable in O(n3) time.


## 4. The Sum of Completion Times with the Investment Cost Minimization Problem

In this section we study the problem1|GT,si[r]A=siralog2⁡(1-x)s,AILE,ni=n¯|β1∑Cij+β2k(x). We assume that each group has the same number of jobs. Our objective is to find the optimal group sequence, the job sequence, and the percentage reduction of the standard learning rate x.For the problem1|GT,si[r]A=siralog2⁡(1-x)s,AILE,ni=n¯|β1∑Cij+β2k(x), by calculation, we present the following expression: (8)β1∑Cij+β2kx=∑i=1mβ1n-i-1n¯siialog2⁡1-xs+∑i=1m∑j=1n¯β1n-i-1n¯-j+1pijialog2⁡1-xsjblog2⁡1-xs+β2kx.Let f2(x)=∑i=1mβ1(n-(i-1)n¯)s[i]ialog2⁡(1-x)s+∑i=1m∑j=1n¯β1(n-(i-1)n¯-j+1)pijialog2⁡(1-x)sjblog2⁡(1-x)s and F2(x)=f2(x)+β2k(x).From Lemma3, we see that f2(x) is a convex function over the interval [0,xmax]. Since k(x) is a convex function, F2(x) is also a convex function over the interval [0,xmax]. Hence, for a certain x∈[0,xmax], the optimal sequence does not change. From the above expression, the group sequence does not affect the job sequence in each group.LetG2(j)=β1(n-(i-1)n¯-j+1)jblog2⁡(1-x)s. From Lemma 1, we see that G2(j) is a nonincreasing function about j. From Lemma 4, for a given group sequence, the optimal internal job sequence can be obtained by assigning pi[j] to the corresponding G2(j) following a well-known result on two vectors given by Hardy et al. [20]. Since G2(j) is a nonincreasing function about j, pi[j] should be a nondecreasing sequence. Therefore, the optimal schedule is obtained by sequencing the jobs in each group in nondecreasing order of pi[j], i.e., pi[1]≤pi[2]≤,…,≤pi[ni],i=1,2,3,…,m (the SPT rule). For a certain x∈[0,xmax], if the internal job sequence in each group is determined, the total cost depends on the group sequence. Therefore, we can determine the group sequence by solving the following assignment problem:AP2MinimizeZ=∑i=1m∑r=1mφiryirs.t.∑i=1myir=1r=1,2,…,m,∑r=1myir=1i=1,2,…,m,yir=0or1i=1,2,…,m,r=1,2,…,m.where φir=β1(n-(r-1)n¯)siralog2⁡(1-x)s+∑j=1n¯β1(n-(r-1)n¯-j+1)pi[j]ralog2⁡(1-x)sjblog2⁡(1-x)s.From the above expression, the optimalx depends on the sign of the first derivative of F2(x), i.e., F2′(x). If F2′(x) is positive, we should allocate the minimal value to x, i.e., x=0. If F2′(x) is negative, we should allocate the maximal value to x, i.e., x=xmax. If F2′(x) is equal to 0, any value between 0 and xmax will not affect the total cost.Based on the above analysis, we propose the following algorithm to solve this problem.Algorithm 7.
Step  1. Arrange the jobs in each group in the SPT order, i.e., (9)pi1≤pi2≤,…,≤pini,i=1,2,…,m.Step2. Give a value to x, which x∈[0,xmax], schedule the groups by AP2.
Step  3. Take the first derivative of F2(x)
Set(10)x∗=0,ifF2′x>0,xmax,ifF2′x<0,x∈0,xmax,ifF2′x=0.Step4. Output the optimal job sequence, optimal group sequence, and optimal percentage reduction of the standard learning rate x∗. Similar to the above analysis, the complexity of Algorithm 7 is at most O(n3). Thus, we obtain the following result.Theorem 8.
The1|GT,si[r]A=siralog2⁡(1-x)s,AILE,ni=n¯|β1∑Cij+β2k(x) problem is solvable in O(n3) time.


## 5. Conclusions

In this paper we consider single-machine group scheduling with autonomous and induced learning. The objectives are to minimize a linear combination the makespan and the investment cost and a linear combination the total completion time and the investment cost. We first derive that the problems to minimize the weighted sum of the makespan and the investment cost are polynomially solvable. Then we prove that the problems to minimize the weighted sum of the total completion time and the investment cost are polynomially solvable under certain condition. In future research it is worth considering more general learning models in other machine environments or extend our model with other objective functions.



---

*Source: 2172378-2018-08-05.xml*