# Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function

Authors: Kunping Shen; Yuke Chen; Shangchia Liu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

This paper considers the combination of the general sum-of-processing-time effect and position-dependent effect on a single machine. The actual processing time of a job is defined by functions of the sum of the normal processing times of the jobs processed and its position and control parameter in the sequence. We consider two monotonic effect functions: the nondecreasing function and the nonincreasing function. Our focus is the following objective functions, including the makespan, the sum of the completion time, the sum of the weighted completion time, and the maximum lateness. For the nonincreasing effect function, polynomial algorithm is presented for the makespan problem and the sum of completion time problem, respectively. The latter two objective functions can also be solved in polynomial time if the weight or due date and the normal processing time satisfy some agreeable relations. For the nondecreasing effect function, assume that the given parameter is zero. We also show that the makespan problem can remain polynomially solvable. For the sum of the total completion time problem anda1 is the deteriorating rate of the jobs, there exists an optimal solution for a1≥M; a V-shaped property with respect to the normal processing times is obtained for 0<a1≤1. Finally, we show that the sum of the weighted completion problem and the maximum lateness problem have polynomial-time solutions for a1>M under some agreeable conditions, respectively.


---

## Body

## 1. Introduction

Recent years, position-effect and processing-time-dependent scheduling problems have been paid more attention. Significant contributions also are presented to solve these problems, including the following. Browne and Yechiali [1] gave some applications to concern the control of queues and communication systems, where there exists deterioration phenomenon in the process of awaiting processing. Kunnathur and Gupta [2] and Mosheiov [3] presented several real-life situations of deteriorating jobs, including the search for an object under worsening weather and performance of medical treatments under some deteriorated health conditions. We refer to the surveys [4] for detailed state-of-the-art reviews in this time-dependent scheduling, as well as for references to practical applications. Among most common rationales for deterioration, the authors often mention the loss of the processing quality of machinery over time and/or the decrease in the productivity of a human operator who gets tired. Cheng et al. [5] considered deteriorated-effect scheduling problems, where the actual processing time of a job means a function of the logarithm of the sum of the normal processing time of the jobs processed and the setup times are proportional to the actual processing times of the jobs processed. Yin et al. [6] addressed another deterioration model to minimize the makespan and the total completion time, where the actual processing time of a job depends on its starting time and its position. They showed that there exists optimal sequence based on the relationships between problem parameters, including the shortest processing time, longest processing time, or V-shaped with respect to the normal processing times. Rudek [7, 8] considered the general sum-of-processing time-based learning or aging effects and showed that the total weighted completion times’ problem is strongly NP-hard, respectively. Gawiejnowicz [9] gave a detail review for four decades of time-dependent scheduling, including main results, new topics, etc. Jiang et al. [10] studied general truncated sum-of-actual processing-time-based effect on the single machine. The actual processing time of a job is affected by the sum-of-actual processing times of previous jobs and by a job-dependent truncation parameter. More recent papers considered deteriorating jobs: Li et al. [11], Liang et al. [12], Gawiejnowicz and Kurc [13], and Wang et al. [14].Learning effects are divided into the following two types. (1) Position dependent: the actual processing time of jobJj depends on pj and on its position in the sequence. (2) Cumulative: the actual processing time of job Jj depends on pj and on the sum of normal processing times of jobs sequenced earlier. Biskup [15] and Cheng and Wang [16] were one of the pioneers who brought the concept of learning into the field of scheduling. Biskup [17] presented a detailed review for learning effect in 2008. Wang and Wang [18] investigated a general model with the agreeable position weight. The general models can cover the majority of existent sum-of-processing-time-based scheduling models. Luo [19] presented more general sum-of-processing-time-based scheduling models, which cover the normal processing time or the actual processing times. The distinctive proof technique is developed based on the adding-term operation, the subtracting-term operation, and the Lagrange mean value theorem. Lin [20] studied job-dependent learning effect and controllable processing time on the unrelated parallel machine. The three objective functions are considered, including the weighted sum of total completion time, total load, and total compression cost. Extensive surveys of different scheduling models can be found in Azadeh et al. [21], Pei et al. [22], and Tai [23]. More application of scheduling models, especially, many real-world problems have been explained by using mathematical models such as higher-order spectral analysis of stray flux signals for faults’ detection in induction motors, vortex theory for two-dimensional Boussinesq equations, normal complex contact metric manifolds admitting a semisymmetric metric connection, urea injection and uniformity of ammonia distribution in the SCR system of diesel engine, and new complex and hyperbolic forms for Ablowitz-Kaup-Newell-Segur wave equation with fourth order can be found in the following papers: Iglesias Mart et al. [24], Sharifi and Reasi [25], Jiao and Zheng [26], and Eskita et al. [27].Motivated on the above discussion, the general sum-of-processing-time-based effect and position-dependent effect are provided. The job processing times are defined by functions of the sum of the normal processing times of jobs processed, its position and and control parameter in the sequence. Two monotonic effect functions are studied: nondecreasing function and nonincreasing function. Our four objective functions is the makespan, the sum of completion time, the sum of the weighted completion time, and the maximum lateness. Our contribution in this paper is listed as follows:(i)
The nonincreasing effect function.(ii)
The makespan problem and the sum of the completion time problem can be solved in polynomial time.(iii)
The total weighted completion times’ problem and the lateness problem can also be solved in polynomial time if the weight or due date and the normal processing time satisfy some agreeable relations.(iv)
The nondecreasing effect function and the given parameter is zero.(v)
The makespan problem can remain polynomially solvable.(vi)
The sum of completion time problem fora1≥M>1 can be optimally solved, where a1 is the deteriorating rate of the jobs. Moreover, for the sum of the completion time problem with 0<a1≤1, a V-shaped property based on the normal processing times is obtained in an optimal sequence which satisfies some agreeable relations.(vii)
The sum of the weighted completion times’ problem and the maximum lateness problem fora1>M have polynomial-time solutions under some agreeable conditions.The rest of the paper is organized as follows. In Section 2, we give the problem description. In Sections3 and 4, we consider two different actual processing times. Our conclusion will be given in Section 5.


## 2. Problem Description

Single-machine scheduling problems can be normally narrated as follows: jobs’ set.(i)
J=J1,J2,…,Jn(ii)
pj: the normal processing time of job Jj, j=1,2,…,n(iii)
wj: the weight of job Jj, j=1,2,…,n(iv)
dj: the due date of job Jj, j=1,2,…,n(v)
pjr: the actual processing time of the job Jj scheduled in the rth position in the sequence(vi)
fx,y: a bivariate continuous convex function on x and ygx a continuous function on x with g″x≤0pl the normal processing time of a job scheduled in the lth position in a job sequence(vii)
Cjπ: the completion time of job Jj in job sequence π(viii)
Cmax=maxCj|j=1,2,…,n: the makespan(ix)
∑Cj: the total completion(x)
∑wjCj: the total weighted completion time(xi)
Lmax=maxLj=Cj−dj|j=1,2,…,n: the maximum latenessThe proposed scheduling model is considered as follows:(1)pjr=pjmaxf∑l=1r−1gpl,r,β,where β≥0 is a given control parameter. Moreover, assume that gx≥0 for x≥0, fx,0=0, and fx,1=x.Note that the bivariate functionf is only continuous convex function. Next, we will consider two monotonic function on x: nondecreasing function and nonincreasing function. For the former, assume that ∂f/∂x≤0, ∂2f/∂x2≥0 and g′x≤0. However, for the latter, we only consider the special case of the continuous convex function f, g′x≥0 and a given parameter β=0.


## 3. The Nonincreasing Functionfx,y on x

This section will consider the nonincreasing functionfx,y on x and the nonincreasing function gx on x. Four objective functions will be studied, including the makespan, the sum of the completion times, the sum of the weighted completion times, and the lateness.Theorem 1.
Problem1|pjr=pjmaxf∑l=1r−1gpl,r,β|Cmax can be obtained as an optimal schedule by nondecreasing normal processing times (the shortest processing time (SPT) rule).Proof.
The properties of the optimal solutions for some single-machine problems are proved by the pairwise job interchange technique. Letπ and π′ be two job schedules where the difference between sigma and σ′ is a pairwise interchange of two adjacent jobs Ji and Jj, i.e., σ=S1,Ji,Jj,S2 and σ′=S1,Jj,Ji,S2, where S1 and S2 are partial sequences. Assume that t0 denotes the completion time of the last job scheduled in r−1th position of S1. Under σ, the completion times of jobs Ji and Jj are(2)Ciσ=t0+pimaxf∑l=1r−1gpl,r,β,(3)Cjσ=t0+pimaxf∑l=1r−1gpl,r,β+pjmaxf∑l=1r−1gpl+gpi,r+1,β.
Underσ′, the completion times of jobs Jj and Ji are(4)Cjσ′=t0+pjmaxf∑l=1r−1gpl,r,β,(5)Ciσ′=t0+pjmaxf∑l=1r−1gpl,r,β+pimaxf∑l=1r−1gpl+gpj,r+1,β.
Note thatpi ≤ pj. Next, we will show that σ dominates σʹ. Taking the difference between (4) and (14), it is obtained that(6)Cjσ−Ciσ′=pi−pjmaxf∑l=1r−1gpl,r,β+pjmaxf∑l=1r−1gpl+gpi,r+1,β−pimaxf∑l=1r−1gpl+gpj,r+1,β.
Based on the monotonicity of functionf and g, we have(7)f∑l=1r−1gpl+gpi,r+1≤f∑l=1r−1gpl+gpj,r+1≤f∑l=1r−1gpl,r.
Next, the parameterβ will be discussed by four cases as follows:(1)
β≥f∑l=1r−1gpl,r. Then, we have(8)Cjσ−Ciσ′=pi−pjβ+pjβ−piβ=0.(2)
f∑l=1r−1gpl+gpj,r+1≤β≤f∑l=1r−1gpl,r. Then, we have(9)Cjσ−Ciσ′=pi−pjf∑l=1r−1gpl,r+pjβ−piβ=pi−pjf∑l=1r−1gpl,r−β≤0.(3)
f∑l=1r−1gpl+gpi,r+1≤β≤f∑l=1r−1gpl+gpj,r+1. Then, we have(10)Cjσ−Ciσ′=pi−pjf∑l=1r−1gpl,r+pjβ−pif∑l=1r−1gpl+gpj,r+1≤pi−pjf∑l=1r−1gpl,r−β≤0.(4)
β≤f∑l=1r−1gpl+gpi,r+1. Then, we have(11)Cjσ−Ciσ′=pi−pjf∑l=1r−1gpl,r+pjf∑l=1r−1gpl+gpi,r+1−pif∑l=1r−1gpl+gpj,r+1=pipjf∑l=1r−1gpl+gpj,r+1−f∑l=1r−1gpl,rpj−f∑l=1r−1gpl+gpi,r+1−f∑l=1r−1gpl,rpi.
Letφx=f∑l=1r−1gpl+gx,r+1−f∑l=1r−1gpl,r/x, x>0. Then, we can obtain(12)dφxdx=∂f/∂xg′xx−f∑l=1r−1gpl+gx,r+1+f∑l=1r−1gpl,rx2.
LetΦx=∂f/∂xg′xx−f∑l=1r−1gpl+gx,r+1+f∑l=1r−1gpl,r, and we have(13)dΦxdx=∂2f∂x2g′x2x+∂f∂xg″xx+∂f∂xg′x−∂f∂xg′x=∂2f∂x2g′x2x+∂f∂xg″xx.
Based on∂2f/∂x2≥0, ∂f/∂x≤0, and g″x≤0, we can obtain that dΦx/dx≥0, i.e., the function Φx is an nondecreasing function for Φx≥Φ0=f∑l=1r−1gpl,r−f∑l=1r−1gpl+g0,r+1≥0. Thus, φpi≤φpj for pi≤pj. Moreover, we have Cjσ≤Ciσ′.
Note that the completion times of the jobJh if scheduled in r+2th in the job sequence σ and σ′, respectively, are denoted as follows:(14)Chσ=Cjσ+phmaxf∑l=1r−1gpl+gpi+gpj,r+2,β,(15)Chσ′=Ciσ′+phmaxf∑l=1r−1gpl+gpi+gpj,r+2,β.
FromCjσ≤Ciσ′, we have Chσ≤Chσ′, i.e, the starting time of the first job Jh in partial job sequence S2 of job sequence σ is earlier than job sequence σ′. Therefore, we have Ckσ≤Ckσ′ for job Jk in the partial sequence S2. Hence, the optimality of the SPT rule can be showed by repeating this argument for the proposed scheduling problem.
Note thatCiσ−Cjσ′=pi−pjmaxf∑l=1r−1gpl,r,β≤0 by the equations (2) and (4). Then, the following theorem will be presented.Theorem 2.
Problem1pjr=pjmaxf∑l=1r−1gpl,r,β∑Cj can be solved by the SPT rule.For the total weighted completion time and the maximum lateness, we only show that this two problems can be solved in polynomial time under some special agreeable relations, respectively.Theorem 3.
For the problem1pjr=pjmaxf∑l=1r−1gpl,r,β∑wjCj, an optimal schedule can be obtained by the weighted smallest processing time, i.e., the WSPT rule, if the jobs have agreeable weights, i.e., pj≤pk implies wk≤wj for all jobs Jj and Jk.Proof.
Similar to the same notations in the proof of Theorem1. Let the jobs Ji and Jj satisfy the agreeable relation, i.e., pi/wi≤pj/wj which implies pi≤pj and wi≥wj. Next, we will show that ∑wjCjσ≤∑wjCjσ′.
Since partial job sequenceS1 in job sequence σ and σ′ has the same job position, then the completion time of job Jh of partial job sequence S1 is the equal, i.e., Chσ=Chσ′, h=1,2,…,r−1.
From Theorems1 and 2, we have(16)wiCiσ+wjCjσ−wiCiσ′−wjCjσ′=wiCiσ−Ciσ′+wjCjσ−Cjσ′≤jCiσ−Ciσ′+Cjσ−Cjσ′≤0.
Additionally, we haveChσ≤Chσ′ for Jh∈S2 by Theorem 1.Theorem 4.
For the problem1pjr=pjmaxf∑l=1r−1gpl,r,β∑wjCj, an optimal schedule can be obtained by the earliest due date, i.e., the EDD rule, if the jobs have agreeable weights, i.e., pj≤pk implies dj≤dk for all jobs Jj and Jk.Proof.
Using the same notations of Theorem1, we will show that Lmaxσi≤Lmaxσ′ based on the agreeable relation, i.e., pi≤pj and di≤dj. From Theorems 1 and 2, we have(17)Ljσi=Cjσ−dj≤Ciσ′−dj≤Ciσ′−di=Liσ′,Liσi=Ciσ−di≤Ciσ′−di=Liσ′.
Moreover, we can obtainLmaxσi≤Lmaxσ′. Hence, interchanging the job position will not increase the value of Lmax.


## 4. The Nondecreasing Functionfx,y on x

In this section, the special case of the nondecreasing functionfx,y on x will be given, and β=0. Firstly, some notations are defined as follows: a1 and a2 denote the deteriorating or learning rate and the learning rate, respectively. M1,M2,andM are three given positive numbers, where M1=1+∑l=1l=nβllnpl/β1, M2=maxjlnpj, and M=1+M1+M2.The special sum-of-processing-time model can be described as follows:(18)pjr=pj1+∑l=1r−1βllnpla1qra2,where a1∈0,1,M,+∞. 0≤q1≤⋯≤qn, 0≤β1≤⋯≤βn, a2<0 and lnpl≥1.Next, some useful lemmas will be given. Based onx=lnpi and λ=pj/pi, the proofs of some lemmas can be obtained by differentiation.Lemma 1.
1−λ+λ1+cxa1qa2−1+cx+clnλa1qa2≤0, for λ≥1, a1≥M, a2<0, c≥1/M1, x≥1, and q>1.Lemma 2.
1−λ+λ1+cxa1qa2−1+cx+clnλa1qa2≥0, for λ≥1, 0<a1≤1, a2<0, c≥1/M1, x≥1, and q>1.Lemma 3.
1−λ+λ2λ1+cxa1qa2−λ11+cx+clnλa1qa2≤0, for λ≥1, a1≥M, a2<0, λ1≥λ2>0, c≥1/M1, x≥1, and q>1.Similar to the notations of Theorem1, we will give the following results. Under σ, the completion times of jobs Ji and Jj are(19)Ciσ=t0+pi1+∑l=1r−1βllnpla1qra2,(20)Cjσ=t0+pi1+∑l=1r−1βllnpla1qra2+pj1+∑l=1r−1βllnpl+βrlnpia1qr+1a2.Underσ′, the completion times of jobs Jj and Ji are(21)Cjσ′=t0+pj1+∑l=1r−1βllnpla1qra2,(22)Ciσ′=t0+pj1+∑l=1r−1βllnpla1qra2+pi1+∑l=1r−1βllnpl+βrlnpja1qr+1a2.Theorem 5.
For the problem1pjr=pj1+∑l=1r−1βllnpla1qra2Cmax,(1)
a1≥M, SPT rule is optimal(2)
0<a1≤1, SPT rule is optimalProof.
Note thatpi≤pj. We will show that Cjσ≤Ciσ′. Taking the difference between (20) and (22), it is obtained that(23)Cjσ−Ciσ′=pi−pj1+∑l=1r−1βllnpla1qra2+pj1+∑l=1r−1βllnpl+βrlnpia1qr+1a2−pi1+∑l=1r−1βllnpl+βrlnpja1qr+1a2.(1)
By substitutingλ=pj/pi, c=βr/1+∑l=1r−1βllnpl, q=qr+1/qr, and x=lnpi into equation (23), it is simplified to(24)Cjσ−Ciσ′=pi1+∑l=1r−1βllnpla1qra21−λ+λ1+cxa1qa2−1+cx+clnλa1qa2.Sinceqr≤qr+1 and Lemma 1, then Cjσ≤Ciσ′. This means that the completion times of the jobs processed before jobs Jj and Ji is not change by interchange. Furthermore, Cjσ≤Ciσ′ implies that the staring times of the jobs processed after jobs cannot be decreased by interchanging σ and σ′.(2)
From case 2 and Lemma2, the result can be easily obtained.Theorem 6.
For the problem1pjr=pj1+∑l=1r−1βllnpla1qra2∑Cj, if a1≥M, then an optimal schedule can be obtained by the SPT rule.Proof.
Suppose thatpi≤pj. To show that σ dominates σ′, it suffices to show that ∑Cjσ≤∑Cjσ′. Taking the difference between (19) and (21), it is obtained that Ciσ−Cjσ′=pi−pj1+∑l=1r−1βllnpla1qra2≤0. Stem from case 1 and case 2 of Theorem 6, we have Cjσ≤Ciσ′ and Ciσ≤Cjσ′. The completion times of the jobs processed before jobs Jj and Ji are not affected by interchange. Furthermore, Cjσ′≥Ciσ implies that the staring times of the jobs processed after jobs Jj and Ji cannot decrease by interchange σ and σ′. Hence, ∑Cjσ≤∑Cjσ′.
Though we want to give an polynomial time algorithm for0<a≤1, we can present the following example to show that there does not exist an polynomial time algorithm:Example 1.
n=3, p1=5, p2=4, and p3=6. The deterioration index a1=1, the learning index a2=−1, β1=0.01, β2=0.02, and β3=0.1. The SPT sequence is J2,J1,J3, ∑CjSPT=9.68. The LPT sequence is J3,J1,J2, ∑CjSPT=10.08. Obviously, the optimal sequence is J2,J3,J1, ∑CjSPT=9.053.
From Example1, we know that the SPT rule or LPT rule cannot give an optimal solution for the proposed problem if 0<a≤1. It remains an open problem. Now, we will present that problem 1pjr=pj1+∑l=1r−1βllnpla1qra2,0<a≤1∑Cj, has an important property, i.e., V-shaped normal job processing times.Definition 1.
A schedule is V-shaped normal job processing times if jobs, processed before some job with the smallestpj, are arranged in descending order, but in ascending order if placed after it.Theorem 7.
For the problem1pjr=pj1+∑l=1r−1βllnpla1qra2,0<a1≤1∑Cj, an optimal schedule exists, which is V-shaped normal job processing times.Proof.
Consider a scheduleΣ with three consecutive jobs, Ji, Jj, and Jk, i.e., Σ=T1,Ji,Jj,Jk,T2 such that pj>pi and pj>pk. Let Σ1 (Σ2) be the schedule obtained from Σ by interchanging Ji and Jj (Jj and Jk), i.e., Σ1=T,Jj,Ji,Jk,T2 (Σ2=T1,Ji,Jk,Jj,T2). Furthermore, let τ0 denote the completion time of the last job in ℜ1, and there are r−1 jobs in T1. Then, the contribution of the three jobs to the total completion time is(25)ΔΣ=3τ0+3pi1+∑l=1r−1βllnpla1qra2+2pj1+∑l=1r−1βllnpl+βrlnpia1qr+1a2+pk1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1qr+2a2.
Similar expressions are easily obtained forΣ1 and Σ2:(26)ΔΣ1=3τ0+3pj1+∑l=1r−1βllnpla1qra2+2pi1+∑l=1r−1βllnpl+βrlnpja1qr+1a2+pk1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1qr+2a2,ΔΣ2=3τ0+3pi1+∑l=1r−1βllnpla1qra2+2pk1+∑l=1r−1βllnpl+βrlnpia1qr+1a2+pj1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpka1qr+2a2.
It follows that(27)ΔΣ−ΔΣ1=3pi−pj1+∑l=1r−1βllnpla1qra2+2pj1+∑l=1r−1βllnpl+βrlnpia1qr+1a2−2pi1+∑l=1r−1βllnpl+βrlnpja1qr+1a2+pkqr+2a21+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1−1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1,(28)ΔΣ−ΔΣ2=2pj−pk1+∑l=1r−1βllnpl+βrlnpia1qr+1a2+pk1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1qr+2a2−pj1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpka1qr+2a2.
Sinceβr≤βr+1 and pi<pj, then we have 1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1>1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1. Next, let λ=pj/pi, c=βr/1+∑l=1r−1βllnpl, x=lnpi and q=qr+1/qr. From equation (27), we have(29)ΔΣ−ΔΣ1=1+∑l=1r−1βllnpla1qra231−λ+2λ1+cxa1qa2−21+cx+clnλa1qa2+pkqr+2a21+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1−1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1.
Letu=pj/pk, d=βr+1/1+∑l=1r−1βllnpl+βrlnpi, y=lnpk, and t=qr+2/qr+1. From equation (27), we have(30)ΔΣ−ΔΣ2=pk1+∑l=1r−1βllnpl+βrlnpia1qr+1a22u−1+1+dy+dlnua1ta2−u1+dya1ta2.
Now, letΔΣ−ΔΣ1 be negative. Based on the above equations and 1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1>1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1, we have(31)31−λ+2λ1+cxa1qa2−21+cx+clnλa1qa2<0⇒21−λ+2λ1+cxa1qa2−1+cx+clnλa1qa2+1−λ+2λ1+cxa1qa2−1+cx+clnλa1qa2<0⇒21−λ+2λ1+cxa1qa2−1+cx+clnλa1qa2<0from Lemma3⇒2u−1+1+dy+dlnua1ta2−u1+dya1ta2>0.
Hence, we haveΔΣ−ΔΣ2>0.
Now, letΔΣ−ΔΣ2 be negative. Based on the above equations, we have(32)2u−1+1+dy+dlnua1ta2−u1+dya1ta2<0⇒2u−1+1+dy+dlnua1ta2−u1+dya1ta2+u−1+1+dy+dlnua1ta2−u1+dya1ta2<0from Lemma3⇒3u−1+21+dy+dlnua1ta2−2u1+dya1ta2<0⇒31−λ+2λ1+cxa1qa2−21+cx+clnλa1qa2>0.
Since1+∑l=1r−1βllnpl+βrlnpi+βr+1lnpja1>1+∑l=1r−1βllnpl+βrlnpj+βr+1lnpia1, we have ΔΣ−ΔΣ1>0.
We conclude that an optimal schedule exists, which is V-shaped normal job processing times.
Fora1≥M, we will present polynomial-time solutions under some agreeable condition to minimize the total weighted completion times and the maximum lateness, respectively.Theorem 8.
Problem1pjr=pj1+∑l=1r−1βllnpla1qra2∑wjCj can be obtained as an optimal solution by the nondecreasing order of pj/wj if the processing times and the weights are agreeable, i.e., pi≤pj⇒wi≥wj, for all the jobs Ji and Jj.Proof.
Suppose thatpj/pi≥wj/wi≥1. Since pi≤pj. Thus, we will show that σ dominates σʹ. From (19)–(22), we have(33)∑wjCjσ−∑wjCjσ′=wi+wjpi−pj1+∑l=1r−1βllnpla1qra2+wjpj1+∑l=1r−1βllnpl+βrlnpia1qr+1a2−wipi1+∑l=1r−1βllnpl+βrlnpja1qr+1a2.
By substitutingλ1=wi/wi+wj, λ2=wj/wi+wj, λ=pj/pi, c=βr/1+∑l=1r−1βllnpl, q=qr+1/qr, and x=lnpi into equation (33), it is simplified to(34)∑wjCjσ−∑wjCjσ′=wi+wjpi1+∑l=1r−1βllnpla1qra21−λ=+λ2λ1+cxa1qa1−λ11+cx+clnλa1qa1.
Sinceqr≤qr+1 and Lemma 3, we have ∑wjCjσ−∑wjCjσ′≤0.Theorem 9.
Problem1pjr=pj1+∑l=1r−1βllnpla1qra2,a1≥MLmax can be solved optimally by nondecreasing order of dj if the job processing times and the due dates are agreeable.Proof.
By definition and equations (19)–(22), the lateness of jobs Ji and Jj in σ and jobs Jj and Ji in σ′ is, respectively,(35)Liσ=Ciσ−di,Ljσ=Cjσ−dj,Ljσ′=Cjσ−dj,Liσ′=Ciσ′−di.
Suppose thatdi≤dj, which implies pi≤pj. Interchanging jobs Ji and Jj has no impact on the maximum lateness of the jobs in subsequence S1, and the maximum lateness of the jobs in subsequence S2 of σ cannot be larger than that of the jobs in S2 of σ′.
Sincepi≤pj, from Theorems 5 and 6,(36)Liσ′−Liσ=Ciσ′−Ciσ>0,Liσ′−Ljσ=Ciσ′−di−Cjσ+dj>0.
Thus, repeating this job interchange argument for all the jobs not sequenced in the EDD rule completes the proof of the last theorem.


## 5. Conclusion

The main contribution of this paper is that the machine scheduling problems with general sum-of-processing-time-based and position-dependent effect function are provided. Two monotonic effect functions, nondecreasing function and nonincreasing function, are considered. The objective functions are to minimize the makespan, the total completion time, the total weighted completion time, and the maximum lateness.The nonincreasing effect function:(1)
The makespan problem and the sum of the total completion time problem can be solved in polynomial time, respectively(2)
The sum of the weighted completion time problem can also be solved in polynomial time if the weight and the normal processing time are under agreeable relations(3)
Maximum lateness problem can also be solved in polynomial time if the due date and the normal processing time are under agreeable relationsThe nondecreasing effect function(1)
a1∈0,1,M,+∞, and the makespan problem can be optimally solved(2)
a1∈M,+∞, and the sum of the completion time problem can be optimally solved(3)
0<a1≤1, t, and the optimal sequence has a V-shaped property with respect to the normal processing times(4)
a1>M, and the total weighted completion time and the maximum lateness have polynomial-time solutions under some agreeable conditions, respectivelyIt is suggested that, for future research to investigate this open problems, the sum-of-processing-time-based deteriorating jobs and learning effect should be considered in the context of other scheduling problems or more sophisticated and efficient heuristic algorithms should be proposed.



---

*Source: 9236044-2021-07-19.xml*