# Group Scheduling with Learning Effect and Random Processing Time

Authors: Dingyu Wang; Chunming Ye
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we establish a stochastic grouping scheduling model. In the model, there is no installation time between the jobs in the same group, but each group has an installation time before processing. There are learning effects between groups and within groups, and the completion time of jobs is a random variable. We take the long expected schedule and the expected total completion time as the objective function, and the noninterruptible static priority strategy is obtained. At the same time, heuristic algorithms and examples are given.


---

## Body

## 1. Introduction

Since Biskup [1] researched on a single-machine scheduling which is based on position learning effect, this kind of problem has become a hot research topic, and the research results have been very fruitful. Moshiov [2] studied a single-machine scheduling problem and proved that the SPT ordering rules is the optimal solution to minimize makespan and EDD ordering rules is optimal order to minimize the maximum delay. The authors in [3–5] have also carried out a lot of research studies on this problem. Mosheiov and Sidney [6] proved that model 1pjr=pjraCmax,1pjr=pjra∑Cj, and 1pjr=pjrai,dj=d∑ω1Cj+ω2Tj+ω3d can be transformed into assignment problem, time complexity is On3. Mosheiov and Sidney [7] studied the problem 1pjr=pjrai,dj=d∑Uj. They transformed the problem into a classic assignment problem, and the time complexity of the problem is On3logn. Lin [8] proved the problem to minimize the tardy jobs when learning rates of the jobs. Bachman and Janiak [9] discussed the problem in special cases 1pjr=pjra,dj=d∑ωjCj, and 1pjr=pjra∑ωpjCj. The former is based on the nonincreasing order, and the latter, according to the SPT sequence, can get the optimal solution. Zhao et al. [10] gave a solution to question 1pjr=pjra∑ωjCj. When pi≤pj⇒wi≥wj, the WSPT order rule is used. When pi≤pj⇒di≤dj, by using EDD ordering rules for the problem of minimizing the maximum tardiness problem, we can get optimal solutions. Liu and Cao [11] solve a kind of difficult problem with the structure network of N prism. Cheng et al. [12] found that there is no gap between the jobs in the process of the jobs, that is to say, the jobs are continuous processing. In [13–15], the authors continue to study this kind of problem and get many results.As people pay attention to the processing time, time of arrival, and uncertainty of machine breakdown, the problem of stochastic scheduling has been paid more and more attention. Pinedo and Hadavi [16], Pinedo and Rammouz [17], Frenk [18], and Liu et al. [19] have carried out a lot of pioneering work on stochastic scheduling problems, and their objective function are mostly the normal function. Then, the content of the research is also more and more diversified. In addition, Zhang et al. [20] continued to study this question. Li [21] considered a stochastic scheduling problem. However, in real life, the machining time is affected by many factors, the randomness of the universal existence. The learning effect of the machine has not changed. The authors in [22–28] continued to study this kind of problem and obtained good results in many aspects.In the classical scheduling problems, most of the research studies on the problem that the installation time is needed to replace the jobs are assumed to be independent of the scheduling of machines and jobs, so the installation time is usually incorporated into the processing time of the jobs. Ham et al. [29] first proposed the “group technology,” but found that the production of products according to a certain same attribute or grouping can greatly improve the production efficiency, thus breaking through the classical assumption of sorting and scheduling. In group technology, the workpiece is divided into several groups according to the similar production technology. The workpiece in the group is processed continuously, and there is no installation time or cost between the parts in the group. Lee and Wu [30] proposed a model: 1pijr,k=pijraika2,G,sir=sira1Cmax and 1pijr,k=pijraika2,G,sir=sira1∑Cj, where pijr,k represents the processing time of Jij in group Gi and r and k represent the position of groups and jobs, respectively, and a1<0 and a2<0 represent the learning factor. Yang and Chand [31] constructed three basic models: there is no forgetting, partial forgetting, and total forgetting in job processing, and the processing time of jobs is related to the location. The authors in [32–35] continue to study this problem and obtain many important results.In this paper, we establish a stochastic grouping scheduling model, and we take the long expected schedule and the expected total completion time as the objective function.


## 2. Two Stochastic Grouping Scheduling Problems with Uniform Processing Time and Learning Effect

For the group scheduling and scheduling problem of this model, we assume that all jobs can be processed at zero; the processing time of jobs is a random variable, which obeys uniform distribution and has location-based learning effect; there is no installation time between jobs in the same group, but each group has an installation time before processing; the group installation time obeys the classical learning effect hypothesis.The assumptions and symbols of the model are as follows:m: the number of groups in the sequence, m≥2Gi: group i, i=1,2,…,mni: number of jobs in group Gin: number of total jobs n1+n2+⋯+ni=nJij: the jth job in group Gi, i=1,2,…,m;j=1,2,…,nia: learning rate for group installation, a<0si: normal installation time of group Gi, i=1,2,…,msir: actual installation time of group Gi in number r, sir=siraai: learning rates of jobs in group Gi, ai<0pij: the random processing time of the job Jij, which obeys the uniform distribution in the interval 0,λijpijk: random processing time of job Jij in position k of group Gi, pijk=pijkaiECij: expected completion time of job JijfCj: function of processing time of job Jj, such as Cmax, ∑CjNow, we consider the stochastic problem of group scheduling, discuss the optimal group sequence and job sequence under the noninterruptible static priority strategy, and give their algorithms. This problem can be expressed by three parameters:(1)1pijk=pijkai,pij∼U0,λij,G,sir=siraEfCj.Theorem 1.
For problem1pijk=pijkai,pij∼U0,λij,G,sir=siraECmax, if the groups are arranged according to the nondecreasing order of the basic installation time sii=1,2,…,m and the jobs in each group are arranged in the nondecreasing order of parameter λij (i,j are natural numbers, and i∈1,m,j∈1,ni), the optimal algorithm under the noninterruptible static priority strategy can be obtained.Proof.
Firstly, we prove that the optimal algorithm of noninterruptible static priority strategy by the nonsubtraction order of parametersλij, that is, the ESPT order, can be obtained. Considering a group, this problem can be attributed to(2)1pijk=pijkai,pij∼U0,λijECmax.
SupposeS and S′ are two sequences and Jis and Jits<t are two jobs; denote S=π1,Jis,Jit,π2 and S′=π1,Jit,Jis,π2. π1andπ2 are job sequences except job Jis and Jit. Jis and Jit are processing in S at rth and r+1th positions, respectively, but in S′, the case is reverse. Et0 is the expected completion time in addition to the jobs Jis and Jit in the sequence. Here, we only need to compare ECitS and ECisS′.
By assuming conditions, we obtain(3)ECitS=Et0+EpiskS+Epitk+1S=Et0+λiska2+λitk+1a2,ECisS′=Et0+EpitkS′+Episk+1S′=Et0+λitka2+λisk+1a2.
So,(4)ECitS−ECisS′=12λis−λit⋅ka−k+1a<0.
Secondly, we prove the group sequence rule. Letsi<sj, Q=σ1,Gi,Gj,σ2 and Q′=σ1,Gj,Gi,σ2. Let the expected completion time of the last job of group Gj in sequence Q be ECjnjQ and the group Gi in sequence Q′ be ECiniQ′. If ECjnjQ≤ECiniQ′ is satisfied, it can be proved that sequence Q is superior to sequence Q′.
According to the hypothesis, we can obtain(5)ECjnjQ=ECiniQ+sjr+1a+E∑k=1njpjkkaj,(6)ECinjQ′=ECjnjQ′+sir+1a+E∑k=1nipikkai,where(7)ECiniQ=Et0+sira+E∑k=1nipikkai,ECjnjQ′=Et0+sjra+E∑k=1njpjkkaj,where Et0 is the expected completion time of the last job of group Gi and Gj. It is noted that si<sj and a<0, by the difference between (1) and (2), we can obtain(8)ECjnjQ−ECinjQ′=si−sj⋅ra−r+1a<0.
So, sequenceQ is superior to sequence Q′. Therefore, by repeating such a swap operation, all groups can be arranged in nonsubtractive order of group installation time. Theorem 1 is proved.
By proving Theorem1, we can design a simple algorithm for problem(9)1pijk=pijkai,pij∼U0,λij,G,sir=siraECmax.
The time complexity of Algorithm1 is Onlogn.
Next, we give an example of Theorem1.Algorithm 1: Heuristic algorithm.
Step 1: according to the nondecreasing order of parameterλij, we arrange the processing of the job in the groupStep 2: arrange the groups according to the nondecreasing order of the basic installation timesi of the groupsExample 1.
m=2, G1=J11,J12, G2=J21,J22,J23, s1=3, s2=4, a1=−0.5, a2=−0.4, a=−0.3, λ11=2, λ12=1, λ21=2, λ22=4, and λ23=3.
Solution. The solution of Example1 is as follows:Step 1: in groupG1, the optimal order of jobs is J12⟶J11; in group G2, the optimal order of jobs is J21⟶J23⟶J22Step 2: because ofs1=3<s2=4, the groups are sorted as G1⟶G2
Therefore, the expected minimum maximum completion time of this example isECmax=11.1086.
Next, we consider another stochastic problem of group scheduling. We have the following conclusion.Theorem 2.
For the problem1pijk=pijkai,pij∼U0,λijE∑Cj, if the group installation time and the number of jobs in the group satisfy the consistent relationship si/ni≤sj/nj, i∈1,m,j∈1,m, then the jobs in the group are arranged according to the nondecreasing order of the parameters λij, and the groups are in the nondecreasing order of ∑l,k=1niλilkai/ni. We can get the optimal algorithm under the noninterruptible static priority policy.Proof.
First of all, we prove that the optimal algorithm under the noninterruptible static priority strategy can be obtained by arranging the jobs in the group according to the nondecreasing order of the parametersλij. When only one group Gi is considered, the problem can be transformed into(10)1pijk=pijkai,pij∼U0,λijE∑j=1njCij.
SupposeS and S′ are two sequences and Jis and Jits<t are two jobs; denote S=π1,Jis,Jit,π2 and S′=π1,Jit,Jis,π2. π1andπ2 are job sequences, except job Jis and Jit. The meaning of Jis,Jit,andEt0 are the same in Theorem 1. In order to prove that sequence S is superior to sequence S′, we just need proof ECisS+ECitS≤ECisS′+ECitS′.
According to the definition, we can obtain(11)ECisS=Et0′+Episkai=Et0′+12λiskai,ECitS=Et0′+Episkai+Epitk+1ai=Et0′+12λiskai+12λitk+1ai,ECitS′=Et0′+Epitkai=Et0′+12λitkai,ECisS′=Et0′+Epitkai+Episk+1ai=Et0′+12λitkai+12λisk+1ai.
By hypothesisai<0 and when s<t, there is λis<λit; therefore,(12)ECisS+ECitS−ECitS′−ECisS′=λis−λit⋅kai−12k+1ai=λis−λit⋅12kai−k+1ai+12k+1ai≤0.
That is,ECisS+ECitS≤ECisS′+ECitS′. In the same way, the jobs in the group are arranged according to the nondecreasing order of parameter λij through the operation of pairwise exchange, and the optimal algorithm under the noninterruptible static priority strategy can be obtained.
Secondly, we prove the group sequence rule. Supposesi<sj, Q=σ1,Gi,Gj,σ2, and Q′=σ1,Gj,Gi,σ2. Let the expected total completion times of jobs in group Gi and Gj of sequence Q be E∑l=1niCilQ and E∑l=1njCjlQ and the expected total completion times of jobs in group Gi and Gj of sequence Q′ be E∑l=1niCilQ′ and E∑l=1njCjlQ′. Then, if the relation E∑l=1niCilQ+E∑l=1njCjlQ≤E∑l=1niCilQ′+E∑l=1njCjlQ′ is satisfied, it can be proved that sequence Q is superior to sequence Q′.
According to the same assumption in the definition and Theorem1, we can obtain(13)E∑l=1niCilQ=niEt0+nisira+E∑k=1,l=1nini−l+1pilkai,(14)E∑l=1njCjlQ=njECiniQ+njsjr+1a+E∑k=1,l=1njnj−l+1pjlkaj.
And, we can also obtain(15)E∑l=1njCjlQ′=njEt0+njsjra+E∑k=1,l=1njnj−l+1pjlkaj,(16)E∑l=1niCilQ′=niECjnjQ′+nisir+1a+E∑k=1,l=1nini−l+1pilkai.
Noticesi/ni≤sj/nj and ∑l,k=1niλilkai/ni≤∑l,k=1njλjlkaj/nj; from (5)–(16), we can obtain(17)E∑l=1niCilQ+E∑l=1njCjlQ−E∑l=1niCilQ′+E∑l=1njCjlQ′=ni+nj⋅si−sj⋅ra−r+1a+njsi−nisj⋅r+1a+12nj∑l,k=1niλilkai−ni∑l,k=1njλjlkai≤0.
By repeating the similar exchange procedure, we can make the group satisfy the nondecreasing order of∑l,k=1niλilkai/ni, thus completing the proof of group sequence rule.
Therefore, we have completed the proof of Theorem2.
We can design an algorithm for problem:(18)1pijk=pijkai,pij∼U0,λijE∑Cj.
The intragroupGi time complexity in step 1 is Onilogni and the total time complexity is ∑i=1mOnilogni; the optimal order time complexity of step 2 is Omlogm. The time complexity of Algorithm 2 is Onlogn.
Next, we give an example of Theorem2.Algorithm 2: Heuristic algorithm.
Step 1: in the group, if the parameterλij of the job is large, it should be arranged firstStep 2: when the group installation time and the number of jobs in the group meet the consistent relationshipsi/ni≤sj/nj, the group processing is arranged according to the nondecreasing order of ∑l,k=1niλilkai/niExample 2.
m=2, G1=J11,J12, G2=J21,J22,J23, s1=3, s2=6, a1=−0.5, a2=−0.4, a=−0.3, λ11=2, λ12=1, λ21=2, λ22=4, and λ23=3.
Solution. The solution of Example2 is as follows:Step 1: in groupG1, the optimal order of jobs is J12⟶J11; in group G2, the optimal order of jobs is J21⟶J23⟶J22Step 2: because ofs1/n1=3/2<s2/n2=6/3 and ∑l,k=1n1λ1lka1/n1=1.3536<∑l,k=1n2λ2lka2/n2=2.3215, the groups are sorted as G1⟶G2
Therefore, the expected minimum total completion time of this example isE∑Cj=39.5113.


## 3. Conclusions

For the expected total completion time problem, the optimal solution can be obtained in polynomial time when there is a consistent relationship between the number of jobs in the group and the sum of the expected processing times of the jobs in the group. When the consistency relation is not satisfied, if the number of groups is small and the number of jobs in the group is small, the optimal algorithm can be found by comparison enumeration; however, when the number of groups is large, the polynomial time algorithm cannot be given, and the complexity of the algorithm is unknown.Considering the randomness of machine learning effect and the randomness of job processing time, we can further discuss the possibility that machine processing time obeys different types of random functions and machine has the random learning index.



---

*Source: 6685149-2021-07-12.xml*