# Multitasking Scheduling Problems with Deterioration Effect

Authors: Zhanguo Zhu; Jinlin Li; Chengbin Chu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Multitasking scheduling problems with a deterioration effect incurred by coexisting behavioral phenomena in human-related scheduling systems including deteriorating task processing times and deteriorating rate-modifying activity (DRMA) of human operators are addressed. Under the assumption of this problem, the processing of a selected task suffers from the joint effect of available but unfinished waiting tasks, the position-dependent deterioration of task processing time, and the DRMA of human operators. Traditionally, these issues have been considered separately; herein, we address their integration. We propose optimal algorithms to solve the problems to minimize makespan and the total absolute differences in completion time, respectively. Based on the analysis, some special cases and extensions are also discussed.


---

## Body

## 1. Introduction

During the past decade, multitasking, as a natural response to a growing number of competing activities in the workplace, has become a symbol for productivity and has attracted growing interest in the fields of behavioral psychology, cognitive engineering, and operations management [1, 2]. Under multitasking, human operators frequently perform multiple tasks by switching from one task to another, which demand their time and attention in the workplace. For example, in health care, 21% of hospital employees’ working time is spent on more than one activity [3] while, in information consulting, information workers usually engage in about 12 working spheres per day and the continuous engagement with each working sphere before switching lasts only 10.5 minutes on average [4]. As pointed out by Rosen [5], multitasking might have significant effects on the economy: it is estimated that extreme multitasking information overload costs the US economy $650 billion per year owing to the loss of productivity. Although many multitaskers state that multitasking has made them more productive [6–8], many studies have indicated that multitasking may lower productivity [9, 10]. Thus, in recent multitasking-related literature, investigation has been made about the effects of multitasking on the productivity from different perspectives [2, 11–13]. Yet, considering multitasking in scheduling systems remains relatively unexplored except for the works of Hall et al. [14], Sum et al. [15], Sum et al. [16], and Zhu et al. [17]. Hall et al. [14] initiated scheduling problems with multitasking by proposing scheduling models in an administration scheduling system. Then, Sum et al. [15], Sum et al. [16], and Zhu et al. [17] extended their work based on the basic setting of a multitasking scheduling model, where the processing of a selected task suffers from interruption by other tasks that are available but unfinished.There are also two other important human behaviors that affect productivity in a human-based scheduling system: the fatigue effect (aging effect) of human operators and rate-modifying activity. The fatigue effect here means that productivity deteriorates over time because of the tiredness of human operators and incurs the duration of task processing which becomes longer than expected. Thus, the task processing time is described as a nondecreasing function dependent on the fatigue of human operators. The function form is similar to the aging effect in the literature. They are both certain types of deterioration. For convenience in introducing the problem, we use the term deterioration effect to denote both of them hereafter. For details on such deteriorations, the readers can refer to Gawiejnowicz [18], Mosheiov [19], Zhao and Tang [20], Janiak and Rudek [21], S.-J. Yang and D.-L. Yang [22], Rudek [23], Yang et al. [24], A. Rudek and R. Rudek [25], Rudek [26], and Ji et al. [27]. A rate-modifying activity (RMA) refers to human operators regularly engaging in rest breaks during work shifts to recover some of the negative effects of fatigue [28]. Lee and Leon [29] first investigated scheduling with RMA by modeling it as a special type of classical machine maintenance activity during which no tasks are processed [30]. The work then was extended in two aspects. Most focused on the machine perspective (e.g., [31–36]). However, some work focused on the human behavior perspective (e.g., [17, 37, 38]). However, both sets of work utilize the same assumption that the duration of the RMA is fixed. In fact, the later an RMA starts, the longer the duration of the RMA usually becomes [22, 39, 40]. For example, the later a human operator has a break, the longer the time he or she takes for recovering to sustain an acceptable production rate. Here, we call this a deteriorating rate-modifying activity (DRMA).As common behavioral phenomena, multitasking, the deterioration effect, and DRMA play concurrently important roles in realistic human-based scheduling systems by affecting the productivity; however, most prior research has concentrated on them separately. Although Hall et al. [14] provided a practical administrative planning scenario illustrating scheduling with multitasking, the deterioration effect and DRMA of human operators were not considered. When human operators are multitasking, the deterioration effect and DRMA change the processing times remarkably, which may incur different scheduling results. Lodree Jr. and Geiger [37] discussed human-like characteristics of fatigue (deterioration effect) and recovery (RMA) in human task sequencing, but not in a multitasking environment. Zhu et al. [17] investigated the multitasking scheduling problem with RMA, yet they ignored the job deterioration effect and the variability (deterioration) of RMA from human fatigue. Extending the work of Hall et al. [14], Lodree Jr. and Geiger [37], and Zhu et al. [17], we jointly consider the above issues in human-based scheduling systems to pursue more practical results. We refer to the proposed problem as multitasking scheduling problems with deterioration effect.The rest of the paper is organized as follows. After presenting the problem formulation and notation in Section2, we provide the results for the considered problem in Section 3. Then, we discuss some extensions in Section 4. The paper is concluded in Section 5.


## 2. Problem Formulation and Notation

In this section, we formulate multitasking scheduling problems with DRMA and a deterioration effect based on the multitasking setting in Hall et al. [14] and the RMA and fatigue effect in Lodree Jr. and Geiger [37] and S.-J. Yang and D.-L. Yang [22]. The scheduling environment can be presented as follows: suppose that a set of tasks needs to be processed by a human operator. While the human operator is processing a selected task, other available but unfinished tasks unavoidably interrupt the operator. Moreover, the productivity of the human operator deteriorates over time due to the fatigue effect, which increases the actual task processing times. The human operator may regularly take rest breaks (DRMA) to recover to a certain level of productivity, yet the duration of the RMA is not fixed and it also deteriorates over time, which means that the later the DRMA is performed the longer its duration is. For convenience in describing the scheduling model, jobs and machines are used to denote tasks and human operators, respectively.Consider a setJ={J1,J2,…,Jn} of n jobs available at time 0 to be processed on a machine that can process at most one job at a time. Each job has a normal processing time pj. As in Hall et al. [14], while job Jj is being scheduled as a primary job, the available and unfinished jobs are called waiting jobs of primary job Jj, and we use Sj∈N to denote the set of such waiting jobs. Thus, for each primary job Jj, the actual job processing time also consists ofinterruption time incurred by interrupting job Jj from the waiting jobs Jk, k∈Sj, andswitching time for handling the interrupting jobs during which no useful work is performed, in addition to normal processing time. The primary job Jj is nonpreemptive except for the interruptions by the waiting jobs Jk, k∈Sj; that is, a primary job is always completed before another job is scheduled as a primary one. Let pk′ denote the remaining processing time of job Jk when job Jj starts to be scheduled as a primary job. Let vk(l), 0≤l≤n-1, denote the remaining processing time of job Jk after it has interrupted l primary jobs. The multitasking function is defined as f(|Sj|)+∑k∈Sj‍gk(pk′) based on empirical evidence in the operations management literature [41, 42]. Again, like Hall et al. [14], we use f(|Sj|) and ∑k∈Sj‍gk(pk′) to denote, respectively, the switching time dependent only on the number of waiting jobs and the interruption time, which is the sum of the amount of time for all the waiting jobs Jk∈Sj interrupting job Jj. Following their assumption too, in this paper, gk(pk′)=Dpk′ and f(|Sj|)=β|Sj|, where 0<D<1, 0<β. Thus, the multitasking function is β|Sj|+∑k∈Sj‍Dpk′.There are two types of deterioration: the deterioration effect of RMA and the deterioration effect of job processing times. Just like the form of DRMA and the aging effect in S.-J. Yang and D.-L. Yang [22], both deterioration effects are position-dependent, meaning that the actual duration of DRMA and job processing are both affected by their actual scheduled positions. Therefore it is assumed that the duration of DRMA is a function of its actual scheduled position. We denote the position of DRMA as i if it is scheduled immediately after the completion of the primary job J[i], where i=0,…,n-1. The actual duration of DRMA is t=ibt0, where t0 is its normal duration and b>0 is the deterioration index. Thus, by combining this with the deterioration of jobs, the actual processing time of Jj is p[j]A=θjpj′fj(j)+βSj+∑k∈Sjθ[k]Dp[k]′f[k](k), for j=i+1,i+2,…,n, and p[j]A=p[j]′f[j](j)+β|Sj|+∑k∈SjDp[k]′f[k](k), for j=1,2,…,i, where 0<θj≤1 is the job-dependent modifying rate and fj(r) is a general job-dependent deterioration, a nondecreasing function of job Jj dependent on its position r in a sequence (schedule). For example, one special case is fj(r)=raj, where aj>0 is the job-dependent deterioration factor. For a given job sequence and position of DRMA, the actual processing times for jobs J[j],j=1,2,…,n, in multitasking scheduling with a deterioration effect and DRMA can be expressed by induction as(1)pjA=1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk,forj=1,…,i,pjA=θj1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1nθkpkfkk,forj=i+1,…,n.The completion time of each job Jj, C[j], for j=1,2,…,n, is(2)Cj=∑j=1j1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk,j=1,2,…,i,Cj=∑j=1i1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk+ibt0+∑j=i+1jθj1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1nθkpkfkk,j=i+2,…,n,where C0=0.The objective is to find the optimal schedule of jobs and the optimal position of DRMA, which minimizes the following objective functions, respectively: the makespan (Cmax=maxj=1,2,…,n{Cj}) and the total absolute differences in completion time (TADC=∑i=1n‍∑j=in‍|Ci-Cj|). Following the three-field notation of Graham et al. [43], we denote the problems as 1MT,DE,DRMACmax and 1|MT,DE,DRMA|TADC, where MT means “multitasking,” DE means “deterioration effect,” and DRMA means “deteriorating rate-modifying activity.”


## 3. Results

The main problems considered in this section are1|MT,DE,DRMA|Cmax and 1|MT,DE,DRMA|TADC, where jobs are subject to a position-dependent deterioration effect and deteriorating RMA while the human operator is carrying out multitasking. Scheduling models and optimal solutions are proposed to find the optimal job sequence π∗ and position of DRMA i∗ such that the makespan and the total absolute differences in the completion time of the schedule are minimized, respectively. For each problem, we analyze the main problem first and then discuss some important special cases.


### 3.1. Makespan Minimization

We now analyze the1|MT,DE,DRMA|Cmax problem. The objective function can be expressed as(3)Z=Cn=ibt0+∑j=1i1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk+∑j=i+1nθj1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1nθkpkfkk=ibt0+∑j=1ipjfjj+1-1-Di∑j=i+1npjfjj+∑j=i+1n1-Diθjpjfjj+βnn-12=ibt0+∑j=1ipjfjj+∑j=i+1n1-1-Di+1-Diθjpjfjj+βnn-12,for1≤i≤n-1.To solve this problem, we use Ejr to denote the cost incurred by a primary job scheduled in position r and set xjr=1 if job Jj is scheduled as a primary job in position r; otherwise, xjr=0, for j=1,2,…,n and r=1,2,…,n. Thus,(4)xjr=1,if  jobJjis  scheduled  as  a  primary  job  in  positionr,forj=1,2,…,n,r=1,2,…,n,0,otherwise,  forj=1,2,…,n,r=1,2,…,n.(5)Ejr=pjfjr,r=1,…,i,1-1-Di+1-Diθjpjfjr,r=i+1,…,n.Thus, the makespan minimization can be represented as the following linear programming problem:LP1minZ=∑j=1n∑r=1nEjrxjr+ibt0+βnn-12subject  to∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.Note that the above objective function consists of three terms. The last term is constant, and the second one is also fixed for each given position of DRMA i. Two sets of constraints are used to guarantee that each job is scheduled as a primary job exactly once and each position is taken by only one primary job.Therefore, given the position of DRMAi, addressing the above linear programming problem LP1 is equivalent to solving the following classical assignment problem AP1:AP1min∑j=1n∑r=1nEjrxjrsubjectto∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.The way to find the optimal job sequence π∗ and the position of DRMA i∗ to minimize the makespan for problem 1|MT,DE,DRMA|Cmax is formally described as the following optimization algorithm based on Hall et al. [14] and Zhu et al. [17].Theorem 1.
For the1|MT,DE,DRMA|Cmax problem, finding the optimal schedule of jobs and the position of DRMA can be done in O(n4).Proof.
As discussed in Algorithm1, we first preprocess the jobs to obtain the remaining processing times of all jobs after they have interrupted l primary jobs, for l=1,…,n-1, which requires O(n) time. Then, for each given position of DRMA i, the 1|MT,DE,DRMA|Cmax problem is converted to a classical assignment problem that can be solved in O(n3) (see [44]). Thus, the assignment problem is executed n-1 times. Consequently, the time complexity of Algorithm 1 is O(n4).Algorithm 1
Step 1. For k from 1 to n do
Step 1.1. vk0≔pk.
Step 1.2. For l from 1 to n-1 do
vkl≔vk(l-1)-Dvk(l-1).
Step 2. For i from 0 to n-1 do
Step  2.1. Compute every cost coefficient Ejr with Equations. (5) for j,r=1,2,…,n.
Step  2.2. Obtain the local optimal sequence (πi∗) and the corresponding makespan related cost by
solving the assignment problemAP1.
Step 3. The optimal solution is the sequence π∗ and the position of the DRMA i∗ that leads to the lowest
makespan-related cost.
Step 4. Schedule the DRMA in the position of i∗ and the jobs with multitasking as the sequence π∗.Further, we discuss three special cases of the main problem1|MT,DE,DRMA|Cmax: the one without DRMA, denoted as 1|MT,DE|Cmax; the one in which the deterioration effect is job-independent (f(r), a nondecreasing function dependent on position r; e.g., one of its special cases is f(r)=ra, where a>0 is a job-independent deterioration factor) and DRMA is not allowed, denoted as 1|MT,DE-id|Cmax; and the one in which the deterioration of RMA is not allowed, denoted as 1|MT,DE,RMA|Cmax.If the DRMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a deterioration effect to minimize the makespan, the1|MT,DE|Cmax problem, which has the following results.Property 2.
For the1|MT,DE|Cmax problem, finding the optimal schedule of jobs can be done in O(n3).Proof.
The makespan of all jobs in the1|MT,DE|Cmax problem is given by(6)Cmax=∑j=1n1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk=∑j=1npjfjj+βnn-12.It can be minimized in O(n3) time by creating an assignment problem similar to the above main problem.If the DRMA is not allowed and the deterioration effect is job-independent, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect to minimize the makespan, the1|MT,DE-id|Cmax problem, which has the following results.Property 3.
For the1|MT,DE-id|Cmax problem, finding the optimal schedule of jobs can be done in O(nlog⁡n).Proof.
The makespan of all jobs in the1|MT,DE-id|Cmax problem is given by(7)Cmax=∑j=1n1-Dj-1pjfj+βn-j+D1-Dj-1∑k=j+1npkfk=∑j=1npjfj+βnn-12.According to a well-known result on two vectors proposed by Hardy et al. [45], the makespan can be minimized in O(nlog⁡n) time by assigning the job with the largest p[j] to the position with the smallest value of f(j), the job with the second largest p[j] to the position with the second smallest value of f(j), and so on. Thus the optimal job sequence can be found in O(nlog⁡n) time.If the deterioration of RMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the makespan, the1|MT,DE,RMA|Cmax problem, which has the following results.We useZ1, Z2, and Z3 to denote the objective values for the 1|MT,DE,RMA|Cmax problem when the RMA is located preceding, within, and following the job sequence, respectively. These can be expressed by induction as follows:(8)Z1=∑j=1npjfjjθj+βnn-12+t0,fori=0,Z2=t0+∑j=1npjfjj-1-Di∑j=i+1n1-θjpjfjj+βnn-12,for1≤i≤n-1,Z3=∑j=1npjfjj+βnn-12,fori=n.If we let Q=∑j=1n‍(1-θ[j])p[j]f[j](j), then the following lemma holds.Lemma 4.
For the1MT,DE,RMACmax problem, if Q<t0, the optimal job sequence can be obtained only by creating an assignment problem without the RMA. Otherwise, the optimal job sequence can be obtained by scheduling the RMA first and then creating an assignment problem to sequence the jobs.Proof.
We prove the case ofQ<t0; the proof for the case of Q≥t0 is similar.(9)Z3-Z1=∑j=1npjfjj-∑j=1npjfjjθj-t0=Q-t0<0.Z3-Z2=1-Di∑j=i+1n1-θjpjfjj-t0≤1-Di∑j=1n1-θjpjfjj-t0≤∑j=1n1-θjpjfjj-t0=Q-t0<0.Therefore, for the 1|MT,DE-id,RMA|Cmax problem, the situation of i=n (i.e., in which the objective function is Z3) is the optimal situation, which means the optimal job sequence can be obtained by scheduling no RMA. Then the optimal job sequence can be obtained by converting the minimization of Z3 to an assignment problem, which takes O(n3) time.Property 5.
For the1|MT,DE,RMA|Cmax problem, finding the optimal schedule of jobs and the position of RMA can be done in O(n3).Proof.
According to Lemma4, an optimal sequence can be obtained by scheduling the RMA at time zero and then sequencing the jobs by solving an assignment problem after the RMA for the case of Q≥t or sequencing the jobs by solving an assignment problem without the RMA for the case of Q<t. Therefore Lemma 4 indicates that an optimal sequence for problem 1|MT,RMA|Cmax can be obtained in O(n3) time. Property 5 holds.


### 3.2. Total Absolute Differences in Completion Time Minimization

We now analyze the1MT,DE,DRMATADC problem. The objective function is(10)TADC=∑j=1iψjpjfjj+∑j=i+1nρjθj+λpjfjj+∑j=1nn-j+1βn-j+in-iibt0,where(11)ψj=j-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1,ρj=j-1n-j+11-Dj-1+∑k=ij-2D1-Dkn-kk,λ=∑k=1iD1-Dk-1k-1n-k+1.Similarly, the right side of the above equation can be minimized by solving the following linear programming problem:(12)min∑j=1n∑r=1nΩjryjr+∑j=1nn-j+1βn-j+in-iibt0subjectto∑r=1nyjr=1,j=1,2,…,n,∑j=1nyjr=1,r=1,2,…,n,yjr=1or0,j=1,2,…,n,r=1,2,…,n,where(13)Ωjr=ψrpjfjr,r=1,…,i,ρrθj+λpjfjr,r=i+1,…,n.Property 6.
For the1|MT,DE,DRMA|TADC problem, finding the optimal schedule of jobs and the position of DRMA can be done in O(n4).Proof.
The proof is similar to that of Theorem1.Now we discuss three special cases of the main problem1|MT,DE,DRMA|TADC: the one without DRMA, denoted as 1|MT,DE|TADC, the one in which the deterioration effect is job-independent (f(r), a nondecreasing function dependent on position r; e.g., one special case is f(r)=ra, where a>0 is the job-independent deterioration factor) and DRMA is not allowed, denoted as 1|MT,DE-id|TADC, and the one in which the deterioration of RMA is not allowed, denoted as 1|MT,DE,RMA|TADC.If the schedule of DRMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the total absolute differences in completion time, the1|MT,DE|TADC problem, which has the following results.Property 7.
For the1|MT,DE|TADC problem, finding the optimal schedule of jobs can be done in O(n3).Proof.
The objective function of the1|MT,DE|TADC problem is given by(14)TADC=∑j=1nj-1n-j+1pjA=∑j=1nj-1n-j+11-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk=∑j=1nj-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1pjfjj+∑j=1nj-1n-j+1βn-j.It can be minimized in O(n3) time by creating an assignment problem with the coefficient ((j-1)(n-j+1)(1-D)j-1+∑k=1j-1‍(k-1)(n-k+1)D(1-D)k-1)p[j]f[j](j).If the DRMA is not allowed and the deterioration effect is job-independent, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect to minimize the total absolute differences in completion time, the1|MT,DE-id|TADC problem, which has the following results.Property 8.
For the1|MT,DE-id|TADC problem, finding the optimal schedule of jobs can be done in O(nlog⁡n).Proof.
The objective function of the1|MT,DE-id|TADC=∑i=1n‍∑j=in‍|Ci-Cj| problem is given by(15)TADC=∑j=1nj-1n-j+1pjA=∑j=1nj-1n-j+11-Dj-1pjfj+βn-j+D1-Dj-1∑k=j+1npkfk=∑j=1nj-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1pjfj+∑j=1nj-1n-j+1βn-j.We set (16)ϕj=j-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1fj.According to a well-known result on two vectors proposed by Hardy et al. [45], the absolute differences in completion time can be minimized in O(nlog⁡n) time by assigning the job with the largest p[j] to the position with the smallest value of ϕj, the job with the second largest p[j] to the position with the second smallest value of ϕj, and so on. Thus the optimal job sequence can be found in O(nlog⁡n) time.If the deterioration of RMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the total absolute differences in completion time, the1|MT,DE,RMA|TADC problem, which has the following results.Property 9.
For the1|MT,DE,RMA|TADC problem, finding the optimal schedule of jobs and the position of RMA can be done in O(n4).Proof.
This problem can be converted to a linear programming similar to that for the1|MT,DE,DRMA|TADC problem with the difference in the last item of the objective function. In this problem it is i(n-i)ibt0 while it is i(n-i)t0 in that problem.


## 3.1. Makespan Minimization

We now analyze the1|MT,DE,DRMA|Cmax problem. The objective function can be expressed as(3)Z=Cn=ibt0+∑j=1i1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk+∑j=i+1nθj1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1nθkpkfkk=ibt0+∑j=1ipjfjj+1-1-Di∑j=i+1npjfjj+∑j=i+1n1-Diθjpjfjj+βnn-12=ibt0+∑j=1ipjfjj+∑j=i+1n1-1-Di+1-Diθjpjfjj+βnn-12,for1≤i≤n-1.To solve this problem, we use Ejr to denote the cost incurred by a primary job scheduled in position r and set xjr=1 if job Jj is scheduled as a primary job in position r; otherwise, xjr=0, for j=1,2,…,n and r=1,2,…,n. Thus,(4)xjr=1,if  jobJjis  scheduled  as  a  primary  job  in  positionr,forj=1,2,…,n,r=1,2,…,n,0,otherwise,  forj=1,2,…,n,r=1,2,…,n.(5)Ejr=pjfjr,r=1,…,i,1-1-Di+1-Diθjpjfjr,r=i+1,…,n.Thus, the makespan minimization can be represented as the following linear programming problem:LP1minZ=∑j=1n∑r=1nEjrxjr+ibt0+βnn-12subject  to∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.Note that the above objective function consists of three terms. The last term is constant, and the second one is also fixed for each given position of DRMA i. Two sets of constraints are used to guarantee that each job is scheduled as a primary job exactly once and each position is taken by only one primary job.Therefore, given the position of DRMAi, addressing the above linear programming problem LP1 is equivalent to solving the following classical assignment problem AP1:AP1min∑j=1n∑r=1nEjrxjrsubjectto∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.The way to find the optimal job sequence π∗ and the position of DRMA i∗ to minimize the makespan for problem 1|MT,DE,DRMA|Cmax is formally described as the following optimization algorithm based on Hall et al. [14] and Zhu et al. [17].Theorem 1.
For the1|MT,DE,DRMA|Cmax problem, finding the optimal schedule of jobs and the position of DRMA can be done in O(n4).Proof.
As discussed in Algorithm1, we first preprocess the jobs to obtain the remaining processing times of all jobs after they have interrupted l primary jobs, for l=1,…,n-1, which requires O(n) time. Then, for each given position of DRMA i, the 1|MT,DE,DRMA|Cmax problem is converted to a classical assignment problem that can be solved in O(n3) (see [44]). Thus, the assignment problem is executed n-1 times. Consequently, the time complexity of Algorithm 1 is O(n4).Algorithm 1
Step 1. For k from 1 to n do
Step 1.1. vk0≔pk.
Step 1.2. For l from 1 to n-1 do
vkl≔vk(l-1)-Dvk(l-1).
Step 2. For i from 0 to n-1 do
Step  2.1. Compute every cost coefficient Ejr with Equations. (5) for j,r=1,2,…,n.
Step  2.2. Obtain the local optimal sequence (πi∗) and the corresponding makespan related cost by
solving the assignment problemAP1.
Step 3. The optimal solution is the sequence π∗ and the position of the DRMA i∗ that leads to the lowest
makespan-related cost.
Step 4. Schedule the DRMA in the position of i∗ and the jobs with multitasking as the sequence π∗.Further, we discuss three special cases of the main problem1|MT,DE,DRMA|Cmax: the one without DRMA, denoted as 1|MT,DE|Cmax; the one in which the deterioration effect is job-independent (f(r), a nondecreasing function dependent on position r; e.g., one of its special cases is f(r)=ra, where a>0 is a job-independent deterioration factor) and DRMA is not allowed, denoted as 1|MT,DE-id|Cmax; and the one in which the deterioration of RMA is not allowed, denoted as 1|MT,DE,RMA|Cmax.If the DRMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a deterioration effect to minimize the makespan, the1|MT,DE|Cmax problem, which has the following results.Property 2.
For the1|MT,DE|Cmax problem, finding the optimal schedule of jobs can be done in O(n3).Proof.
The makespan of all jobs in the1|MT,DE|Cmax problem is given by(6)Cmax=∑j=1n1-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk=∑j=1npjfjj+βnn-12.It can be minimized in O(n3) time by creating an assignment problem similar to the above main problem.If the DRMA is not allowed and the deterioration effect is job-independent, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect to minimize the makespan, the1|MT,DE-id|Cmax problem, which has the following results.Property 3.
For the1|MT,DE-id|Cmax problem, finding the optimal schedule of jobs can be done in O(nlog⁡n).Proof.
The makespan of all jobs in the1|MT,DE-id|Cmax problem is given by(7)Cmax=∑j=1n1-Dj-1pjfj+βn-j+D1-Dj-1∑k=j+1npkfk=∑j=1npjfj+βnn-12.According to a well-known result on two vectors proposed by Hardy et al. [45], the makespan can be minimized in O(nlog⁡n) time by assigning the job with the largest p[j] to the position with the smallest value of f(j), the job with the second largest p[j] to the position with the second smallest value of f(j), and so on. Thus the optimal job sequence can be found in O(nlog⁡n) time.If the deterioration of RMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the makespan, the1|MT,DE,RMA|Cmax problem, which has the following results.We useZ1, Z2, and Z3 to denote the objective values for the 1|MT,DE,RMA|Cmax problem when the RMA is located preceding, within, and following the job sequence, respectively. These can be expressed by induction as follows:(8)Z1=∑j=1npjfjjθj+βnn-12+t0,fori=0,Z2=t0+∑j=1npjfjj-1-Di∑j=i+1n1-θjpjfjj+βnn-12,for1≤i≤n-1,Z3=∑j=1npjfjj+βnn-12,fori=n.If we let Q=∑j=1n‍(1-θ[j])p[j]f[j](j), then the following lemma holds.Lemma 4.
For the1MT,DE,RMACmax problem, if Q<t0, the optimal job sequence can be obtained only by creating an assignment problem without the RMA. Otherwise, the optimal job sequence can be obtained by scheduling the RMA first and then creating an assignment problem to sequence the jobs.Proof.
We prove the case ofQ<t0; the proof for the case of Q≥t0 is similar.(9)Z3-Z1=∑j=1npjfjj-∑j=1npjfjjθj-t0=Q-t0<0.Z3-Z2=1-Di∑j=i+1n1-θjpjfjj-t0≤1-Di∑j=1n1-θjpjfjj-t0≤∑j=1n1-θjpjfjj-t0=Q-t0<0.Therefore, for the 1|MT,DE-id,RMA|Cmax problem, the situation of i=n (i.e., in which the objective function is Z3) is the optimal situation, which means the optimal job sequence can be obtained by scheduling no RMA. Then the optimal job sequence can be obtained by converting the minimization of Z3 to an assignment problem, which takes O(n3) time.Property 5.
For the1|MT,DE,RMA|Cmax problem, finding the optimal schedule of jobs and the position of RMA can be done in O(n3).Proof.
According to Lemma4, an optimal sequence can be obtained by scheduling the RMA at time zero and then sequencing the jobs by solving an assignment problem after the RMA for the case of Q≥t or sequencing the jobs by solving an assignment problem without the RMA for the case of Q<t. Therefore Lemma 4 indicates that an optimal sequence for problem 1|MT,RMA|Cmax can be obtained in O(n3) time. Property 5 holds.


## 3.2. Total Absolute Differences in Completion Time Minimization

We now analyze the1MT,DE,DRMATADC problem. The objective function is(10)TADC=∑j=1iψjpjfjj+∑j=i+1nρjθj+λpjfjj+∑j=1nn-j+1βn-j+in-iibt0,where(11)ψj=j-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1,ρj=j-1n-j+11-Dj-1+∑k=ij-2D1-Dkn-kk,λ=∑k=1iD1-Dk-1k-1n-k+1.Similarly, the right side of the above equation can be minimized by solving the following linear programming problem:(12)min∑j=1n∑r=1nΩjryjr+∑j=1nn-j+1βn-j+in-iibt0subjectto∑r=1nyjr=1,j=1,2,…,n,∑j=1nyjr=1,r=1,2,…,n,yjr=1or0,j=1,2,…,n,r=1,2,…,n,where(13)Ωjr=ψrpjfjr,r=1,…,i,ρrθj+λpjfjr,r=i+1,…,n.Property 6.
For the1|MT,DE,DRMA|TADC problem, finding the optimal schedule of jobs and the position of DRMA can be done in O(n4).Proof.
The proof is similar to that of Theorem1.Now we discuss three special cases of the main problem1|MT,DE,DRMA|TADC: the one without DRMA, denoted as 1|MT,DE|TADC, the one in which the deterioration effect is job-independent (f(r), a nondecreasing function dependent on position r; e.g., one special case is f(r)=ra, where a>0 is the job-independent deterioration factor) and DRMA is not allowed, denoted as 1|MT,DE-id|TADC, and the one in which the deterioration of RMA is not allowed, denoted as 1|MT,DE,RMA|TADC.If the schedule of DRMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the total absolute differences in completion time, the1|MT,DE|TADC problem, which has the following results.Property 7.
For the1|MT,DE|TADC problem, finding the optimal schedule of jobs can be done in O(n3).Proof.
The objective function of the1|MT,DE|TADC problem is given by(14)TADC=∑j=1nj-1n-j+1pjA=∑j=1nj-1n-j+11-Dj-1pjfjj+βn-j+D1-Dj-1∑k=j+1npkfkk=∑j=1nj-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1pjfjj+∑j=1nj-1n-j+1βn-j.It can be minimized in O(n3) time by creating an assignment problem with the coefficient ((j-1)(n-j+1)(1-D)j-1+∑k=1j-1‍(k-1)(n-k+1)D(1-D)k-1)p[j]f[j](j).If the DRMA is not allowed and the deterioration effect is job-independent, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect to minimize the total absolute differences in completion time, the1|MT,DE-id|TADC problem, which has the following results.Property 8.
For the1|MT,DE-id|TADC problem, finding the optimal schedule of jobs can be done in O(nlog⁡n).Proof.
The objective function of the1|MT,DE-id|TADC=∑i=1n‍∑j=in‍|Ci-Cj| problem is given by(15)TADC=∑j=1nj-1n-j+1pjA=∑j=1nj-1n-j+11-Dj-1pjfj+βn-j+D1-Dj-1∑k=j+1npkfk=∑j=1nj-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1pjfj+∑j=1nj-1n-j+1βn-j.We set (16)ϕj=j-1n-j+11-Dj-1+∑k=1j-1k-1n-k+1D1-Dk-1fj.According to a well-known result on two vectors proposed by Hardy et al. [45], the absolute differences in completion time can be minimized in O(nlog⁡n) time by assigning the job with the largest p[j] to the position with the smallest value of ϕj, the job with the second largest p[j] to the position with the second smallest value of ϕj, and so on. Thus the optimal job sequence can be found in O(nlog⁡n) time.If the deterioration of RMA is not allowed, the main problem is reduced to a multitasking scheduling problem with a job-independent deterioration effect and RMA to minimize the total absolute differences in completion time, the1|MT,DE,RMA|TADC problem, which has the following results.Property 9.
For the1|MT,DE,RMA|TADC problem, finding the optimal schedule of jobs and the position of RMA can be done in O(n4).Proof.
This problem can be converted to a linear programming similar to that for the1|MT,DE,DRMA|TADC problem with the difference in the last item of the objective function. In this problem it is i(n-i)ibt0 while it is i(n-i)t0 in that problem.


## 4. Extension

In the above problems, only one DRMA is considered. Now, we discuss a further extension in which multiple DRMAs are allowed. Following Ji and Cheng [33] and Zhu et al. [46], we assume that there exist at most h independent DRMAs. We denote the positions of the uth DRMA as iu if it is scheduled immediately after the completion of the primary job J[iu], where iu=0,…,n-1. The actual duration of DRMA is tuA=iubtu, where tu is its normal duration and b>0 is the deterioration index. Thus, for any job Jj scheduled as a primary job in the position immediately after the iuth DRMA, its actual processing time can be expressed as p[j]A=θu[j]p[j]′f[j](j)+β|Sj|+∑k∈Sjθu[k]Dp[k]′f[k](k), where 0<θuj≤1 is a job-dependent modifying rate, u=1,…,h. The corresponding problems can be denoted as 1|MT,DE,MDRMA|Cmax and 1|MT,DE,MDRMA|TADC, respectively, where MDRMA means multiple DRMAs.We analyze the1|MT,DE,MDRMA|Cmax problem first. The objective function can be expressed as(17)Z=Cn=∑j=ih+1n∑k=1i1D1-Dk-1+∑e=1h-1∑k=ie+1ie+1D1-Dk-1θej+1-Dihθhjpjfjj+⋯+∑j=i2+1i3∑k=1i1D1-Dk-1+∑e=12-1∑k=ie+1ie+1D1-Dk-1θej+1-Di2θ2jpjfjj+∑j=i1+1i2∑k=1i1D1-Dk-1+1-Di1θ1jpjfjj+∑j=1i1pjfjj+∑j=1nβn-j+∑u=1hiubtu.Thus, the makespan minimization problem can be represented as the following linear programming problem:LP2minZ=∑j=1n∑r=1nΛjryjr+∑u=1hiubtu+∑j=1nβn-jsubject  to∑r=1nyjr=1,j=1,2,…,n,∑j=1nyjr=1,r=1,2,…,n,yjr=1or0,j=1,2,…,n,r=1,2,…,n,where(18)Λjr=pjfjrr=1,…,i1,∑k=1i1D1-Dk-1+1-Di1θ1jpjfjr,r=i1+1,…,i2,∑k=1i1D1-Dk-1+∑e=12-1∑k=ie+1ie+1D1-Dk-1θej+1-Di2θ2jpjfjr,r=i2+1,…,i3,⋮∑k=1i1D1-Dk-1+∑e=1h-1∑k=ie+1ie+1D1-Dk-1θej+1-Dihθhjpjfjr,r=ih+1,…,n.Note that the above objective function consists of three terms. The last term is constant. The second one is also fixed and addressing the above linear programming problem LP2 is equivalent to solving the following classical assignment problem while the positions of MDRMA i1,i2,…,ih are given. This means that, to obtain the optimal multitasking job sequence (πi1∗,i2∗,…,ih∗), the assignment problem is executed at most nh times. Therefore, the following theorem holds.Theorem 10.
For the1|MT,DE,MDRMA|Cmax problem, finding the optimal schedule of jobs and the positions of MDRMA can be done O(nh+3).Similarly, we also have the following property.Property 11.
For the1|MT,DE,MDRMA|TADC problem, finding the optimal schedule of jobs and the position of DRMA can be done in O(nh+3).Proof.
The1|MT,DE,MDRMA|TADC problem can be converted to solving a linear programming problem, the objective function of which can be expressed as(19)Z=∑j=1n∑r=1nΓjryjr+∑u=1hiun-iuiubtu+∑j=1nβj-1n-j+1n-j,where(20)Γjr=∑k=1r-1k-1n-k+1D1-Dk-1pjfjr,r=1,…,i1,∑k=i1r-2kn-kD1-Dkθ1j+∑k=1i1k-1n-k+1D1-Dk-1pjfjr,r=i1+1,…,i2,∑k=i2r-2kn-kD1-Dkθ2j+∑e=12-1∑k=ie+1ie+1k-1n-k+1D1-Dk-1θej+∑k=1i1k-1n-k+1D1-Dk-1pjfjr,r=i2+1,…,i3,⋮∑k=ihr-2kn-kD1-Dkθhj+∑e=1h-1∑k=ie+1ie+1k-1n-k+1D1-Dk-1θej+∑k=1i1k-1n-k+1D1-Dk-1pjfjr,r=ih+1,…,n.Thus, similar to the proof of Theorem 10, Property 11 holds.


## 5. Conclusions

In addition to multitasking, there exist other important behavioral phenomena related to human operators that also affect productivity in human-based scheduling systems. In this study, we addressed the integration of these issues by studying multitasking scheduling problems with a deterioration effect. We showed that all the considered cases are polynomially solvable, and we proved the time complexity. Some of the results differ from those obtained without multitasking, deterioration effects, or DRMA. The results are not limited to human operator scheduling but may also be applicable to machine-based scheduling problems. Further studies may investigate different objective functions, for example, the total weighted completion time, under the context of multitasking.



---

*Source: 4750791-2017-04-12.xml*