# Single-Machine Scheduling with Learning Effects and Maintenance: A Methodological Note on Some Polynomial-Time Solvable Cases

Authors: Kuo-Ching Ying; Chung-Cheng Lu; Shih-Wei Lin; Jie-Ning Chen
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This work addresses four single-machine scheduling problems (SMSPs) with learning effects and variable maintenance activity. The processing times of the jobs are simultaneously determined by a decreasing function of their corresponding scheduled positions and the sum of the processing times of the already processed jobs. Maintenance activity must start before a deadline and its duration increases with the starting time of the maintenance activity. This work proposes a polynomial-time algorithm for optimally solving two SMSPs to minimize the total completion time and the total tardiness with a common due date.


---

## Body

## 1. Introduction

The single-machine scheduling problem (SMSP) is one of the most extensively studied classical scheduling problems owing to its wide range of applications in many realistic systems [1]. The excellent surveys of Abdul-Razaq et al. [2], Yen and Wan [3], Pinedo [4], and Adamu and Adewumi [5] have detailed the literature on the theory and applications of various SMSPs in the past several decades. Most SMSPs assume that job processing times are fixed and known throughout the process, and SMSPs with learning effects constitute a relatively new subfield in the area of scheduling.Wright [6] scientifically examined the processing time of a single unit continuously decreasing with the processing of additional units in the aircraft industry; in the literature, this effect is known as the learning effect. Gawiejnowicz [7] was probably the first researcher who applied the learning effect to scheduling problems. Since learning effects are common in both manufacturing and service sectors, many studies have been devoted to investigating it following the pioneering work of Gawiejnowicz [7]. Depending on the production environment, learning effects can be classified into two categories [8]:position-basedlearning effects and thesum-of-processing-times-based learning effects. The former depend only on the number of jobs being processed; the latter depend on the sum of the normal processing times of the already processed jobs.With respect to position-based learning effects, Biskup [9] modified the original power formula, pj,k=p[1]ka, to formulate the basic position-based learning model, pj,k=pjka, where pj,k is the actual processing time of job j if it is scheduled in position k  (k=2,…,n); p[1] denotes the processing time of the first unit; pj represents the normal processing time of job j, and a=log2LR≤0 is the learning index, which depends on the learning rate (LR). Biskup demonstrated that the SMSP with basic position-based learning and the goal of minimizing total completion times can be optimally solved in polynomial time by using the shortest processing time (SPT) rule. Since then, many studies of SMSPs with various performance measures have been performed using the basic position-based learning model of Biskup [9]. The most well-known ones include those of Mosheiov [10, 11], Lee et al. [12], Bachman and Janiak [13], Zhao et al. [14], Kuo and Yang [15], and Wu et al. [16]. Some extensions of the basic position-based learning model have been presented, including the consideration of job-dependent position-based learning effects [17–19], autonomous position-based and induced learning effects [20], position-based learning and deteriorating effects [21, 22], and position-based linear learning effects [13, 23, 24]. In all of the aforementioned position-based learning models, the actual processing time of a job decreases as its scheduled position k increases.With respect to sum-of-processing-time-based learning effects, Kuo and Yang [25, 26] were among the pioneers that considered the processing times of jobs that had already been preprocessed and proposed two learning models, pj,k=pj(1+∑i=1k-1p[i])a and pj,k=pj(∑i=1k-1p[i])a, for SMSPs with time-dependent learning. Yang and Kuo [27] later developed another model, pj,k=pj(1+∑i=1k-1p[i]A)a, that is based on the sum of actual processing times, p[i]A. Koulamas and Kyparisis [28] also proposed a sum-of-processing-time-based learning model for SMSPs: pj,k=pj(1-∑i=1k-1p[i]/∑i=1np[i])b=pj(∑i=knp[i]/∑i=1np[i])b, where b≥1 is the learning index. Based on this model, Biskup [8] indicated that the gains from learning are extremely high and suggested that b≥0 would be more appropriate. Wang [29] considered an SMSP with the learning model that was developed by Koulamas and Kyparisis and proved that an optimal schedule that minimizes the sum of the square completion times can be obtained using the SPT rule. All of the aforementioned sum-of-processing-time-based learning models have in common the fact that the actual processing time of a job cannot be calculated without data on the normal or actual processing times of its preceding jobs, so the analysis is more difficult than that based on position-based learning models. An excellent survey by Biskup presents more detailed discussions regarding SMSPs with learning effects [8].Both position-based learning and sum-of-processing-times-based learning approaches are valid and numerous practical examples of each have been presented. Biskup [8] indicated that position-based learning usually involves operations that are independent of processing time, such as the setting up of machines, while sum-of-processing-times-based learning generally involves the experience that is gained by workers who are involved in the jobs. However, in some situations, position-based learning and sum-of-processing-times-based learning exist simultaneously, such as those that involve a robot with a neural network system, as is used in many assembly lines and has been discussed by Lee and Wu [30]. This fact has motivated recent studies [30–35] that consider both learning effects at once. SMSPs with position-based learning and/or the sum-of-processing-times-based learning have also been studied from different perspectives to develop models that are as realistic as possible [36–40].Since the 1990s, the scheduling of jobs with fixed maintenance [41] or variable maintenance [42] in a manufacturing system has attracted much attention. For scheduling with fixed maintenance, the starting time and the maintenance duration are fixed and given in advance. In scheduling with variable maintenance, the starting time is set by the scheduler, and the maintenance duration is a nondecreasing function of the starting time [43]. For a comprehensive survey, refer to Ma et al. [43]. SMSPs with learning and maintenance commonly arise in realistic manufacturing systems. If learning and maintenance simultaneously occur in an SMSP, then they will critically and enormously influence scheduling. However, learning effects and maintenance activity have seldom been simultaneously studied in relation to SMSPs.To incorporate more practically important factors into scheduling, this work proposes a polynomial-time algorithm for solving two SMSPs, which takes into account both learning effects and variable maintenance activity. The objectives are to minimize the total completion time and the total tardiness with a common due date. The remainder of this paper is organized as follows. Section2 defines the four SMSPs that are considered herein. Section 3 elucidates in detail the proposed polynomial-time algorithm. Finally, Section 4 concludes by offering recommendations for future studies.


## 2. Problem Definition

The SMSPs of interest are characterized by a set,J={J1,J2,…,Jn}, of n independent jobs that are nonpreemptively processed on a single machine. All jobs are available for processing at the beginning of the planning horizon, which is time zero. Each job Jj  (j=1,2,…,n) has a normal processing time (without any learning effects), pj, if the job is sequenced first in a schedule. The following learning model, proposed by Low and Lin [36], applies generally to practical SMSPs.(1)pj,k=pj1-∑i=1k-1pi∑i=1npiabk-1=pj∑i=knpi∑i=1npiabk-1,j,k=1,2,…,n,where pj,k is the actual processing time of job Jj if it is sequenced in position k in a schedule; a≥1 and 0<b<1 are the learning indices, and p[k] is the normal processing time of the job in position k. In (1), the actual processing time of a job is simultaneously influenced by the traditional sum-of-processing-time-based learning effect, pj(1-∑i=1k-1p[i]/∑i=1np[i])b, and the general position-based learning effect, bk-1. Equation (1) clearly reveals that position-based learning and sum-of-processing-times-based learning are special cases with b=1 and a=1, respectively.The machine can handle only one job at a time and is continuously available during the planning horizon, except for the mandatory variable maintenance(VM) activity, which is performed at the beginning of the planning horizon or between two consecutive processed jobs; in that case, the starting time of the maintenance activity,s, must precede a specified deadline, sd (i.e., s≤sd). Notably, the maintenance activity cannot be performed after the completion time of the final job (i.e., sd≤∑k=1n-1pj,k), because if it were so, the variable maintenance activity would effectively be neglected. The duration of maintenance for a given schedule π, tVMπ, is a positive and nondecreasing function of its starting time s: tVMπ=f(s) and f(sb)≥f(sa) for all sb>sa.For a given schedule, letCj be the completion time of job Jj,  j=1,2,…,n. The tardiness of job Jj  (j=1,2,…,n) is Tj=max⁡{0,Cj-dj}, where dj is the due date of job Jj. The objective is to determine the starting time of the maintenance activity and the sequence of all jobs that optimize the total completion time (∑Cj) and the total tardiness (∑Tj) with a common due date, respectively. According to the three-field classification scheme of Graham et al. [44], the two SMSPs of interest are represented as 1,VMLE∑Cj and 1,VMLE,dj=d∑Tj, respectively, where 1 denotes the SMSP; VM stands for the variable maintenance, and LE stands for learning effects.It is important to note that the SMSP with the total flow time,∑Fj, and identical release dates, rj=r, is equivalent to the SMSP with the total completion time, ∑Cj; that is, ∑Fj=∑(Cj-r)=∑Cj-nr, so the 1,VM|LE,rj=r|∑Fj problem is equivalent to the 1,VM|LE|∑Cj problem. Besides, the SMSP with the mean lateness, 1/n∑Lj, is also equivalent to the SMSP with the total completion time, ∑Cj; that is, 1/n∑Lj=1/n∑Cj-1/nD (where D=∑dj). Therefore, the 1,VM|LE|L¯ problem as well as the 1,VM|LE|∑Lj problem is equivalent to the 1,VM|LE|∑Cj problem. Hence, the proposed polynomial-time algorithm can also be used for optimally solving these equivalent SMSPs.


## 3. Polynomial-Time Algorithm

The following three theorems provide obvious properties for sequencing an optimal schedule in the two SMSPs under study.Theorem 1.
In the1,VM|LE|∑Cj problem, there exists an optimal schedule that is obtained by sequencing jobs in the SPT order.Theorem 2.
In the1,VM|LE,dj=d|∑Tj problem, there exists an optimal schedule that is obtained by sequencing jobs in the SPT order.Proof.
The maintenance activity is carried out among a pair of consecutive jobs. The job interchange method can easily be used to reveal that the optimal schedules in the1,VM|LE|∑Cj and 1,VM|LE,dj=d|∑Tj problems are those consistent with the SPT order. Here, only two jobs, j′ and j, which are scheduled before and after the maintenance activity, are considered. Their schedule is denoted as π=(…,j′,VM,j,…). The positions of jobs j′ and j can be swapped, keeping the other jobs in the same positions, to generate a new schedule, π′=(…,j,VM,j′,…). If pj′>pj, then the duration of the maintenance activity is lower in π′, tVMπ′<tVMπ, because the maintenance activity in π′ will start before that in π. Therefore, the completion time of job j′ in π′ will be less than the completion time of job j in π, so Cj′π′<Cjπ. Based on these results, the proofs of Theorems 1 and 2 are as follows.Proof of Theorem1.
LetTCj&j′π and TCj&j′π′ denote the sums of the completion times of jobs j and j′ in π and π′, respectively. Now,(2)TCj&j′π-TCj&j′π′=Cj′π+Cjπ-Cjπ′+Cj′π′=pj′∑i=knpi∑i=1npiabk-1+tVMπ+pj∑i=knpi-pj′∑i=1npiabk-pj∑i=knpi∑i=1npiabk-1+tVMπ′+pj′∑i=knpi-pj∑i=1npiabk=pj′-pj∑i=knpi∑i=1npiabk-1+tVMπ-tVMπ′+pj∑i=knpi-pj′∑i=1npiabk-pj′∑i=knpi-pj∑i=1npiabk.
Substitutingx=pj/∑i=1npi,  y=∑i=knpi/∑i=1npi, and λ=pj′/pj into (2) yields (3)TCj&j′π-TCj&j′π′=pjyabk-11-λxab-λ1-xab+λ-1+tVMπ-tVMπ′.
Letf(λ)=(1-λx)ab-λ(1-x)ab+λ-1; then, (4)f′λ=-ax1-λxa-1b-1-xab+1,f′′λ=aa-1x21-λxa-2b.
Sinceλ≥1,  a≥1,  0<x≤1, and 0<b<1,  f′′(λ)≥0. Thus, f′(λ) is an increasing function.
Letg(x)=-ax(1-x)a-1b-(1-x)ab+1; now, g′(x)=a(a-1)x(1-x)a-2b+a(1-x)a-1b≥0, for a≥1,  0<x≤1, and 0<b<1.
Sinceg(x)≥g(0)=1-b>0, for 0<b<1,  g(x) is increasing for a≥1, 0<x≤1, and 0<b<1. Therefore, g(x)=-ax(1-x)a-1b-(1-x)ab+1>0, and f′(1)=-ax1-xa-1b-1-xab+1≥0.
Therefore,f′(λ)≥f′(1)≥0 for λ≥1,  a≥1,  0<x≤1, and 0<b<1. Hence, f(λ) is an increasing function for λ≥1,  a≥1,  0<x≤1, and 0<b<1. Since f(λ)≥f(1)=0,  (1-λx)ab-λ(1-x)ab+λ-1>0 for λ≥1,  a≥1,  0<x≤1, and 0<b<1, so the first term in (3) is nonnegative. Also, the second term in (3) (tVMπ-tVMπ′)>0 if pj′>pj. Clearly, TCj&j′π-TCj&j′π′>0 if pj′>pj, implying that the total completion time of π is larger than that of π′, completing the proof of Theorem 1.Proof of Theorem2.
Let∑Tj&j′π and ∑Tj&j′π′ denote the average tardiness of jobs j and j′ in π and π′, respectively. Now,(5)∑Tj&j′π-∑Tj&j′π′=max⁡0,Cjπ-d+max⁡0,Cj′π-d-max⁡0,Cjπ′-d+max⁡0,Cj′π′-d.
Obviously,∑Tj&j′π-∑Tj&j′π′>0 because (Cjπ+Cj′π)>(Cjπ′+Cj′π′) if pj′>pj, implying that the total tardiness of π is larger than that of π′, completing the proof of Theorem 2.Based on Theorems1 and 2, the following simple algorithm (named YLLC algorithm) is proposed to determine the optimal starting time of the variable maintenance activity and the sequences of all jobs in the two SMSPs of interest.Algorithm YLLCStep 1.
Sort all jobs in the SPT order based on normal processing times to generate a sequenceπ=(J[1],J[2],…,J[n]) with p[1]≤p2≤⋯≤p[n], where p[k]  (k=1,2,…,n) is the normal processing time of the job with thekth processing priority.Step 2.
Use (1) to calculate the actual processing time, p[k]A (k=1,2,…,n), of each job with thekth processing priority in π.Step 3.
For a given deadlinesd for the start of the maintenance activity, compute k- that satisfies ∑k=1k-p[k]A≤sd<∑k=1k-+1p[k]A.Step 4.
Construct the candidate schedulesπk=(J[0],…,J[k-1],VM,J[k],…,J[n]), k=1,2,…,k-+1, where J[0] is a dummy job. Select the optimal schedule among the candidate schedules, which has the lowest objective function value.Notably, proof of Theorem1 also reveals the existence of an optimal schedule to the 1,VM|LE|Cmax problem, which is obtained by sequencing jobs in the SPT order. Hence, the optimal solution to the 1,VM|LE|Cmax problem can also be obtained by using the proposed YLLC algorithm. However, the criteria of maximum lateness and the makespan with release dates are not considered in this study because the SMSP with anyone of these criteria are strongly NP-hard even with simple linear position learning models (without maintenance) [45].Theorem 3.
Algorithm YLLC solves the1,VM|LE|∑Cj and 1,VM|LE,dj=d|∑Tj problems in O(n2) time.Proof.
Sort the jobs using the SPT rule, requiringO(nlog⁡n) time. Given the SPT order and a starting time of the maintenance activity, the objective function value of a candidate schedules can be computed in O(n) time. The maximum number of possible starting times for maintenance is n, so the objective function value is computed not more than n times. Hence, algorithm YLLC solves each of the four SMSPs in O(n2) time.


## 4. Conclusions and Recommendations for Future Studies

Learning effects and maintenance activity are critical factors in many scheduling environments but have seldom been studied in relation to SMSPs. In an attempt to address real-world situations, this work considered two SMSPs with learning effects and variable maintenance activity. The objectives were to minimize the total completion time and the total tardiness. An algorithm for solving the two SMSPs was developed, and the SMSPs were thus proved to be solvable in polynomial time with the explicit consideration of learning and the variable maintenance. According to the results, the developed algorithm is useful to practitioners in guiding them to solve the relevant SMSPs.The SMSP with learning effects and variable maintenance is not purely hypothetical but arises in real scheduling decisions. It will continue to attract the attention of researchers and practitioners. This study suggests various potential directions for further research. First, the proposed algorithm could be extended to solve SMSPs with more general functions of learning effects as well as with the aging/deteriorating effect. Second, different objective functions for the SMSP with learning effects and maintenance considerations should be considered in the light of the results herein. Third, an SMSP with learning effects and maintenance in which a biobjective function value is minimized would be an interesting topic of research. Fourth, an SMSP with learning effects and multiple variable maintenance activities during the planning horizon would also be an interesting topic of research. Finally, extending the problems to the jobs with different release dates or due dates would be complex but warrants further works.



---

*Source: 7532174-2017-08-08.xml*