# Uncertain Single-Machine Scheduling with Deterioration and Learning Effect

Authors: Jiayu Shen
Journal: Journal of Mathematics
 (2020)

---

## Abstract

A single-machine scheduling problem with deterioration and learning effect is studied in the present paper. The processing time and due date are considered uncertain variables due to lack of historical data. The aim is to minimize the makespan, total completion time, total weight completion time, and maximum lateness under an uncertain environment. To address the problem in an uncertain environment, the expected value model and pessimistic value model are developed. These models can be converted into equivalent models based on the inverse distribution method. It is proved that the corresponding dispatching rules can solve the problem optimally under different objective criteria. Finally, sensitivity analysis is used to illustrate the effectiveness of these rules.


---

## Body

## 1. Introduction

Single-machine scheduling is the basis of all scheduling problems, and many complex scheduling problems can be simplified into several single-machine problems. In recent years, many literature studies on scheduling are mainly concerned with the single scheduling problem. The traditional scheduling problem usually assumes that the processing time is a constant. This assumption may be impractical in many cases because the processing time may be prolonged or shortened as time passes. Some examples about deterioration or learning effect were mentioned in [1]. Raw material in the queue waiting to be processed deteriorates as time passes, which may lead to a certain loss (job deterioration). On an assembly line, workers become more skilled over time (learning effect). Many scholars had studied the scheduling problem with deterioration and learning effect [2–17].Since environmental impact and resource constraint, emergencies can lead to uncertainty in processing time and due date. Many researchers studied the scheduling problems under stochastic or fuzzy environment. Optimal permutation policies in single-machine stochastic scheduling problems with learning effects were investigated [18]. A sequence-dependent single-machine scheduling problem with different learning effects was considered [19]. The processing times, setup times, and reliabilities/unreliabilities were considered as random variables. Li [20] studied a single-machine scheduling problem with random processing time and job-based learning effect recently. Ahmadizar and Hosseini [21, 22] considered single-machine scheduling problems with a position-based learning effect and fuzzy processing times. Toksari and Arık [23] considered single-machine scheduling problems under position-dependent fuzzy learning effect with fuzzy processing times, and polynomially solvable algorithms for different confidence levels for these problems were proposed.Most people believe that probability distribution is easy to obtain from the historical data, and then, we should use probability theory. However, the distribution function obtained in most practical problems is not close enough to the actual frequency. In this case, we have to invite the domain expert to assess the degree of belief that each event will occur. For example, a worker can only assess the processing time of a job based on his past experience. To address personal belief degrees, uncertainty theory was founded by Liu [24] in 2007 and refined it in 2010 [25]. Uncertainty theory is a branch of axiomatic mathematics. It has been developed in many fields such as uncertain calculus [15, 26–28], uncertain risk analysis [29–31], uncertain differential equation [32–35], and uncertain programming [36–40].This paper studies the impacts of both deterioration and learning effect in a single-machine scheduling problem under an uncertain environment. The processing time and due date are considered uncertain variables. For example, in the rough machining operation process, due to machine failure, operation error, environmental impact, and many other uncertainties, workers usually evaluate the processing time according to their own experience. Much asymmetric information in the production and logistics process of the supply chain may lead to uncertainty and cause delays of the due date. It is more suitable for production practice to assume these parameters to be uncertain variables, which can ensure the feasibility and effectiveness of scheduling. The objective functions are makespan, total completion time, total weight completion time, and maximum lateness, respectively. Under different decision criteria, the expected value model and pessimistic value model are developed. Once uncertain distributions are given, the deterministic equivalence of the models is obtained by the uncertainty theory. To address the models effectively, corresponding dispatching rules are proposed.The rest of the paper is organized as follows. To understand this paper better, basic definitions and results about uncertainty theory are introduced in Section2. In Section 3, the problem under an uncertain environment is described and the mathematical models are constructed. In Section 4, to facilitate computation, the equivalence of the models is investigated and dispatching rules for the optimal solutions are presented. Section 5 gives an example of sensitivity analysis.


## 2. Preliminary

To describe an uncertain variable which refers to human uncertainty, Liu [24] established the uncertainty theory and it has been developed well up to now. Some necessary preliminary concepts about uncertainty theory are given.LetΓ be a nonempty set, ℒ is a σ-algebra over Γ, and each element Λ in ℒ is called an event. A set function M from ℒ to 0,1 is called an uncertain measure if it satisfies normality axiom, duality axiom, subadditivity axiom, and product axiom [24, 41].The uncertain distributionΦ of an uncertain variable ξ is defined by Φx=Mξ≤x for any real number x. The uncertain variables ξ1,ξ2,…,ξm are said to be independence (Liu [41]) if(1)M∩i=1mξi∈Bi=min1≤i≤mMξi∈Bi,for any Borel sets B1,B2,…,Bn of real numbers.Uncertain measure has the following two useful properties: (i) for any eventsΛ1⊂Λ2, we have MΛ1≤MΛ2, and (ii) for any events Λ1 and Λ2, we have(2)MΛ1+MΛ2−1≤MΛ1∩Λ2≤MΛ1∧MΛ2.Definition 1.
(see [24]). Let ξ be an uncertain variable, and α∈0,1. Then(3)ξsupα=suprMξ≥r≥αis called the α-optimistic value to ξ, and(4)ξinfα=infrMξ≤r≥αis called the α-pessimistic value to ξ.Definition 2 (see [24]).
An uncertain distributionΦx is said to be regular if its inverse function Φ−1x exists and is unique for each α∈0,1. Then, the inverse function Φ−1 is called the inverse uncertainty distribution of ξ.Theorem 1 (see [24]).
Assume the constraint functiongx,ξ1,ξ2,…,ξn is strictly increasing with respect to ξ1,ξ2,…,ξk and strictly decreasing with respect to ξk+1,ξk+2,…,ξn. If ξ1,ξ2,…,ξn are independent uncertain variables with uncertainty distributions Φ1,Φ2,…,Φn, respectively, then the chance constraint(5)Mgx,ξ1,ξ2,…,ξn≤0≥α,holds if and only if(6)gx,Φ1−1α,…,Φk−1α,Φk+1−11−α,…,Φn−11−α≤0.Theorem 2 (see [24]).
Letξ be an uncertain variable. Then, the expected value of ξ is defined by(7)Eξ=∫0+∞Mξ≥rdr−∫−∞0Mξ≤rdr,provided that at least one of the two integrals is finite.Ifξ and η are independent uncertain variables, then(8)Eaξ+bη=aEξ+bEηholds for any real numbers a and b.


## 3. Mathematical Models

The definition of the uncertain single-machine scheduling problem with deterioration and learning effect is given as follows.Assume thatn independent and nonpreemptive jobs are processed on a single machine. All jobs are available at time 0. Only one job can be processed at a time. The basic processing time of job i is ξi, the due date of job i is di, and the weight of job i is wi. The deterioration function at is an increasing function a0≥0 and is a differentiable convex function. We consider the similar actual processing time proposed by Lee [42]. The actual processing time of job i is ξiat+βrb, where b≤0 is the learning coefficient and t is the start processing time of job i.The processing time, due date, and learning coefficient are assumed to be uncertain variables. In the real operating environment, the forgotten effect leads to job deterioration due to the frequent rotation of the task. With the increase of time and the accumulation of experience, workers become more skilled in operating the machine. Before constructing the mathematical model of the uncertain single-machine problem, the parameters for models are given as follows (Table1 lists notations for the proposed models):Table 1
List of notations.
Notations
Definitions
i
=
1,2
,
…
,
n
The index of job
r
=
1,2
,
…
,
n
The index of position
ξ
i
Inherent processing time of jobi
d
i
The due date of jobi
w
i
The weight of jobi
a
t
Deterioration function
p
r
The processing time of therth job on the machine
b
Learning coefficient
C
max
The makespan
C
i
The completion time of jobi
C
r
The completion time of therth job on the machine
∑
C
i
The total completion time
∑
w
i
C
i
The total weighted completion time
L
max
The maximum lateness(9)
C
max
=
max
i
=
1,2
,
…
,
n
C
i
,
L
max
=
max
i
=
1,2
,
…
,
n
C
i
−
d
i
.Decision variables:(10)xi,r:1,if jobiis processed at therth position,0,otherwise.The relationship of variables is as follows:(11)pr=∑i=1nxi,r⋅ξiat+βrb,r=1,2,…,n,(12)Cr=Cr−1+pr,r=1,2,…,n;j=1,2,…,m,(13)Ci=∑r=1nxi,r⋅Cr,i=1,2,…,n.Equation (11) define the actual processing time of the rth job on the machine. Clearly, the processing time changes with the position. Equation (12) define the completion time of the rth job on the machine. Equation (13) reveal the relationship between the completion times.When the processing time, due date, and learning coefficient are uncertain variables, how can we obtain an optimal solution in such an uncertain environment? First, we can use the uncertainty expectation to measure the uncertain variables. The expected value is the average of the uncertain variables on the uncertainty measure.The problem is modeled under the expected value criterion:(14)minECmaxminE∑CiminE∑wiCiminELmaxsubject to∑i=1nxi,r=1,r=1,2,…,n∑r=1nxi,r=1,i=1,2,…,nxi,r∈0,1,∀i,r.This model minimizes the expected values of these objective functions subject to some constraints, respectively. Equation (14) ensure that each job can only be assigned to one position on the machine. Equation (14) ensure that each position can only process one job and there is no spare time on the machine. Constraint (14) gives the range of the decision variables.In reality, the decision maker always tries to find the optimal solution within a small deviation. A preset targetf¯ is determined such that there exists a solution x∗ satisfying Mfx≤f¯≥α. For example, let α=0.9, the decision maker should determine a target f¯ and then choose a solution x which satisfies Mfx≤f¯≥0.9. It means that if the decision maker chooses the solution x, the objective function fx will be less than or equal to f¯ at least 90%. A pessimistic value model is conceived:(15)minf¯1minf¯2minf¯3minf¯4subject toMCmax≤f¯1≥α1M∑Ci≤f¯2≥α2M∑wiCi≤f¯3≥α3MLmax≤f¯4≥α4∑i=1nxi,r=1,r=1,2,…,n∑r=1nxi,r=1,i=1,2,…,nxi,r∈0,1.where αi,i=1,2,…,4 are preset confidence levels.This model is to calculate the pessimistic value tofi,i=1,2,…,4. The detailed proof will be obtained in the next section. Constraint (15) ensure that the conditions hold under confidence levels αi,i=1,2,…,4, respectively.


## 4. Equivalence of Uncertain Models

It is noted that the above two models contain many uncertain variables, so it is difficult to solve them directly. In most uncertain programming literature studies, GA and PSO are used to find the approximate optimal solution. Although the effectiveness of these approaches is often illustrated by numerical experiments, the preciseness and generality of these approaches are not satisfactory. The uncertain models can be converted into deterministic forms with the help of uncertainty theory.Theorem 3.
The expected value model can be converted into the following model equivalently:(16)minmaxi=1,2,…,n∑r=1nxi,r∫01ΦCr−1−1γdγ+∑i=1nxi,r∫01Φξi−1γat+βrbdγmin∑i=1n∑r=1nxi,r∫01ΦCr−1−1γdγ+∑i=1nxi,r∫01Φξi−1γat+βrbdγmin∑i=1nwi∑r=1nxi,r∫01ΦCr−1−1γdγ+∑i=1nxi,r∫01Φξi−1γat+βrbdγminmaxi=1,2,…,n∑r=1nxi,r∫01ΦCr−1−1γdγ+∑i=1nxi,r∫01Φξi−1γat+βrbdγ−∫01Φdi−1γdγsubject to∑i=1nxi,r=1,r=1,2,…,n∑r=1nxi,r=1,i=1,2,…,nxi,r∈0,1.where Φf−1 represents the inverse uncertainty distribution of f.Proof.
Since the expectation operator is linear and according to Jensen’s inequality, it yields(17)ECmax≥maxi=1,2,…,nECi=maxi=1,2,…,nE∑r=1nxi,rCr−1+∑i=1nxi,rξiat+βrb=maxi=1,2,…,n∑r=1nxi,rECr−1+∑i=1nxi,rEξiat+βrb=maxi=1,2,…,n∑r=1nxi,r∫01ΦCr−1−1γdγ+∑i=1nxi,r∫01Φξi−1γat+βrbdγ.
Similarly, other objective functions can be obtained.Theorem 4.
The pessimistic value model can be converted into the following model equivalently:(18)minΦCmax−1α1minΦ∑Ci−1α2minΦ∑wiCi−1α3minΦLmax−1α4subject to∑i=1nxi,r=1,r=1,2,…,n∑r=1nxi,r=1,i=1,2,…,nxi,r∈0,1.where αi,i=1,2,…,4 are preset confidence levels and Φf−1 represents the inverse uncertainty distribution of f.Proof.
Letξ1,ξ2,…,ξn be independent uncertain variables with regular uncertainty distributions Φ1,Φ2,…,Φn, respectively. Assume fξ1,ξ2,…,ξn is strictly increasing with respect to ξ1, ξ2, …, ξm and strictly decreasing with respect to ξm+1,ξm+2,…,ξn. Let ξ=fξ1,ξ2,…,ξn, and according to Definition 2, ξ is an uncertain variable with the inverse uncertainty distribution(19)Ψ−1α=fΦ1−1α,…,Φm−1α,Φm+1−11−α,…,Φn−11−α,which yields Mξ≤f¯=Ψf¯.
M
ξ
≤
f
¯
≥
α is equivalent to Ψf¯≥α. Then, it yields(20)Ψf¯≥ΨΨ−1α.
Since the uncertainty distribution is an increasing function, it yields(21)fΦ1−1α,…,Φm−1α,Φm+1−11−α,…,Φn−11−α≤f¯.
M
ξ
≤
f
¯
≥
α is equivalent to(22)fΦ1−1α,…,Φm−1α,Φm+1−11−α,…,Φn−11−α≤f¯,where α is a given confidence level.
According to the above conclusion, we can obtain the equivalent form of the pessimistic value model:(23)minf¯1minf¯2minf¯3minf¯4subject toΦCmax−1α1≤f¯1Φ∑Ci−1α2≤f¯2Φ∑wiCi−1α3≤f¯3ΦLmax−1α4≤f¯4∑i=1nxi,r=1,r=1,2,…,n∑r=1nxi,r=1,i=1,2,…,nxi,r∈0,1.where αi,i=1,2,…,4 are preset confidence levels and Φf−1 represents the inverse uncertainty distribution of f.
According to the definition of optimistic value (Definition1), equation (23) is equivalent to equation (18), thus (23) are equivalent to equation (18), equations (23) are equivalent to equation (18), equations (23) are equivalent to equation (18). Thus, the theorem is proved.Theorem 5.
The optimal schedule of the makespan problem under the uncertain environment is obtained by the shortest processing time (SPT) rule.Proof.
An optimal scheduleπ which consists of two adjacent jobs (Ji precedes Jj) is considered. Assume the start processing time of job Ji is A. Let Ci and Cj represent the completion times of the jobs Ji and Jj, respectively.(1)
Under the expectation value criterionEξi>Eξj:(24)ECiπ=A+EξiaA+βrb,ECjπ=A+EξiaA+βrb+EξjaCiπ+βr+1b.By exchanging the position of two jobs, a scheduleπ′ is obtained:(25)ECjπ′=A+EξjaA+βrb,ECiπ′=A+EξjaA+βrb+EξiaCjπ′+βr+1b.By comparing their sizes and according to Lagrange mean value theorem, it yields(26)ECiπ′−ECjπ=EξjaA+βrb+EξiaCjπ′+βr+1b−EξiaA+βrb−EξjaCiπ+βr+1b=βEξj−EξirEa−r+1b+Eξia′ζ1EξjaA+βrb−Eξja′ζ2ξiaA+βrb,whereA<ζ1<A+EξjaA+βrb and A<ζ2<A+EξiaA+βrb.BecauseEξi>Eξj, rb≥r+1b, and a′ζ1<a′ζ2, it yields ECiπ′<ECjπ. It implies that the expected makespan under π is smaller than that under π′. This result contradicts the optimality of π.(2)
Under the pessimistic value criterionMξi>ξj≥α, rb≥r+1b, and Ma′ζ1<a′ζ2≥α:(27)MCiπ′−Cjπ<0=Mβξj−ξira−r+1a+ξiα′ζ1ξjαA+βra−ξjα′ζ2ξiαA+βra<0.BecauseCiπ′−Cjπ<0⊃ξi>ξj∩ra≥r+1a∩a′ζ1<a′ζ2, and according to the two useful properties of uncertain measure, it yields(28)MCiπ′−Cjπ<0≥Mξi>ξj+Mrb−r+1b+Ma′ζ1<a′ζ2−2≥3α−2.It implies that the pessimistic value of makespan underπ is smaller than that under π′. This result contradicts the optimality of π. Hence, the SPT rule gets the optimal solution. The theorem is proved.Theorem 6.
The optimal schedule of∑Ci problem under the uncertain environment is obtained by the SPT rule.Proof.
Theorem5 implies that the start processing time of jobs after Ji and Jj can be advanced by changing the order. Therefore, the ∑Ci in π′ is less than that in π. This result contradicts the optimality of π. The theorem is proved.Theorem 7.
The optimal schedule of∑wiCi problem under the uncertain environment is obtained by the WSPT rule.Proof.
An optimal scheduleπ which consists of two adjacent jobs (Ji precedes Jj) is considered, and the jobs are not arranged according to the WSPT rule. Hence, we have ξi/wi>ξj/wj.(1)
Under the expectation value criterion:(29)ECiπ=A+EξiaA+βrb,ECjπ=A+βEξirb+EξiaA+EξjaCiπ+βEξjr+1b.By exchanging the position of two jobs, a scheduleπ′ is obtained:(30)ECjπ′=A+EξjaA+βrb,ECiπ′=A+βEξjrb+EξjaA+EξiaCjπ′+βEξir+1b.Similar to Theorem5, it yields(31)∑wiECiπ′−∑wjECjπ=βEξj−Eξirb−r+1bwi+wj+wiEξj−wjEξiaA+βr+1b+wiEξia′ζ1EξjaA+βrb−wjEξja′ζ2EξiaA+βrb.BecauseEξi>Eξj, rb≥r+1b, wj>wi, Eξi/wi>Eξj/wj, and a′ζ1<a′ζ2, it yields ∑wiECiπ′<∑wjECjπ. It implies that the expected weighted sum under π′ is smaller than that under π. This result contradicts the optimality of π.(2)
Under the pessimistic value criterionMξi>ξj≥α, wi<wj, Mra≥r+1a≥α, and Ma′ζ1<a′ζ2≥α.Becauseξi>ξj∩wi<wj⊂ξi/wi>ξj/wj, it yields Mξi/wi>ξj/wj≥α:(32)M∑wiCiπ′−∑wjCjπ<0=Mβξj−ξirb−r+1bwi+wj+wiξj−wjξiaA+βr+1b+wiξia′ζ1ξjaA+βrb−wjξja′ζ2ξiaA+βrb<0.Because(33)∑wiCiπ′−∑wjCjπ<0⊃ξi>ξj∩rb≥r+1b∩ξi/wi>ξj/wj∩a′ζ1<a′ζ2,then according to the two useful properties of uncertain measure, it yields(34)MCiπ′−Cjπ<0≥Mξi>ξj+Mrb≥r+1b+Mξi/wi>ξj/wj+Ma′ζ1<a′ζ2−3≥4α−3.It implies that the pessimistic value of∑wiCi under π′ is smaller than that under π. This result contradicts the optimality of π. Hence, the SPT rule gets the optimal solution. The theorem is proved.Theorem 8.
The optimal schedule ofLmax problem under uncertain environment is obtained by the EDD rule.Proof.
An optimal scheduleπ which consists of two adjacent jobs (Ji precedes Jj) is considered, and the jobs are not arranged according to the EDD rule.(1)
Under the expectation value criterion, we haveEdi>Edj. It implies that Eξi>Eξj:(35)ELiπ=A+EξiaA−Edi,ELjπ=A+βEξirb+EξiaA+EξjaA+ξiaA+βrb+βEξjr+1b−Edj.By exchanging the position of two jobs, a scheduleπ′ is obtained:(36)ELjπ′=A+EξjaA−Edj,ELiπ′=A+βEξjrb+EξjaA+EξiaA+ξjaA+βrb+βEξir+1b−Edi.BecauseEdi>Edj and Eξi>Eξj, it yields(37)maxELiπ′,ELjπ′≤maxELiπ,ELjπ.It implies that EDD is optimal.(2)
Under the pessimistic value criterionMdi>dj≥α.Becausedi>dj⊂ξi>ξj, it yields Mξi>ξj≥α.And because(38)maxLiπ′,Ljπ′−maxLiπ,Ljπ<0⊃di>dj∩ξi>ξj,it yields(39)MmaxLiπ′,Ljπ′−maxLiπ,Ljπ<0≥Mξi>ξj+Mdi>dj−1≥2α−1.It implies that the optimal solution can be obtained by the EDD rule. The theorem is proved.
Note that these theorems have a higher dependence on the confidence level in the case of pessimistic value. For instance, the condition that the confidence levelα is greater than 0.75 is sufficient for the result of Theorem 7. If the confidence level α is less than 0.75, the required result may not be deduced based on the current method in the proof of Theorem 7. Also the confidence level α greater than 0.75 shows that the conclusion holds at a high confidence level. It is reasonable since we generally do not consider the situation that a result holds at a lower confidence level in reality. The pessimistic value case also shows that the decision maker is more inclined to believe that the rule can effectively obtain the optimal solution when faced with making decisions.


## 5. Sensitivity Analysis

Numerical examples are conducted to investigate the sensitivity of these confidence levels. Assume that there are 30 jobs;β=2; processing time of job i is generated from uncertain normal distribution: N15,10 for i=1,2,…,50; due date of job i is generated from uncertain normal distribution: N60,30 for i=1,2,…,50; wi=1.5; a obeys normal distribution N−0.2,0.1;and deterioration function αt=t/2. To examine the sensitivity of confidence levels αi, i=1,2,…,4, Figures 1–4 indicate that the objective values are nondecreasing with respect to these confidence levels. It can be seen that these confidence levels must be greater than 0.6. Since the confidence level is too low, there is no guarantee that the conclusion of the theorem will be established in the case of pessimistic value.Figure 1
The sensitivity of solution for makespan problem.Figure 2
The sensitivity of solution for total completion time problem.Figure 3
The sensitivity of solution for total weight completion time problem.Figure 4
The sensitivity of solution for maximum lateness problem.


## 6. Conclusions

An uncertain single-machine scheduling problem with deterioration and learning effect was studied in this paper. The processing time, due date, and learning coefficient were considered uncertain variables. Two different criteria (expected value and pessimistic value) multiobjective programming models were proposed. The equivalence of the two models was proved based on the uncertainty inverse distribution method. Due to the complexity of the problem, different dispatching rules was used to solve the problem. It was proved that the SPT rule can solve the makespan and total completion time problems under different uncertain criteria optimally, and the total weight completion time and maximum lateness can be solved by WSPT and EDD rules optimally, respectively. The results also suggested that the decision maker will choose the scheme with relatively high confidence level. At the last, the sensitivity analysis revealed that the objective function values are nondecreasing with respect to the confidence levels. For future work, it is an interesting research to investigate the influence of these uncertain variables on other workshop environment (e.g., parallel machine, flow shop, and job shop).



---

*Source: 7176548-2020-05-07.xml*