Processing math: 54%
 

Quantifying the impact of early-stage contact tracing on controlling Ebola diffusion

  • Recent experience of the Ebola outbreak in 2014 highlighted the importance of immediate response measure to impede transmission in the early stage. To this aim, efficient and effective allocation of limited resources is crucial. Among the standard interventions is the practice of following up with the recent physical contacts of the infected individuals -- known as contact tracing. In an effort to understand the effects of contact tracing protocols objectively, we explicitly develop a model of Ebola transmission incorporating contact tracing. Our modeling framework is individual-based, patient-centric, stochastic and parameterizable to suit early-stage Ebola transmission. Notably, we propose an activity driven network approach to contact tracing, and estimate the basic reproductive ratio of the epidemic growth in different scenarios. Exhaustive simulation experiments suggest that early contact tracing paired with rapid hospitalization can effectively impede the epidemic growth. Resource allocation needs to be carefully planned to enable early detection of the contacts and rapid hospitalization of the infected people.

    Citation: Narges Montazeri Shahtori, Tanvir Ferdousi, Caterina Scoglio, Faryad Darabi Sahneh. Quantifying the impact of early-stage contact tracing on controlling Ebola diffusion[J]. Mathematical Biosciences and Engineering, 2018, 15(5): 1165-1180. doi: 10.3934/mbe.2018053

    Related Papers:

    [1] Weiguo Liu, Xuyin Wang, Xiaoxiao Wang, Peizhen Zhao . Due-window assignment scheduling with past-sequence-dependent setup times. Mathematical Biosciences and Engineering, 2022, 19(3): 3110-3126. doi: 10.3934/mbe.2022144
    [2] Chunlai Liu, Chuanhui Xiong . Single machine resource allocation scheduling problems with deterioration effect and general positional effect. Mathematical Biosciences and Engineering, 2021, 18(3): 2562-2578. doi: 10.3934/mbe.2021130
    [3] Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang . Resource dependent scheduling with truncated learning effects. Mathematical Biosciences and Engineering, 2022, 19(6): 5957-5967. doi: 10.3934/mbe.2022278
    [4] Dan Yang, Zhiqiang Xie, Chunting Zhang . Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times. Mathematical Biosciences and Engineering, 2023, 20(6): 9781-9817. doi: 10.3934/mbe.2023429
    [5] Shaofeng Yan, Guohui Zhang, Jinghe Sun, Wenqiang Zhang . An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints. Mathematical Biosciences and Engineering, 2023, 20(4): 7519-7547. doi: 10.3934/mbe.2023325
    [6] Lu-Wen Liao . A branch and bound algorithm for optimal television commercial scheduling. Mathematical Biosciences and Engineering, 2022, 19(5): 4933-4945. doi: 10.3934/mbe.2022231
    [7] Zhimeng Liu, Shuguang Li . Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine. Mathematical Biosciences and Engineering, 2022, 19(7): 7337-7348. doi: 10.3934/mbe.2022346
    [8] Xue Jia, Jing Xue, Shi-Yun Wang, Ji-Bo Wang . Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times. Mathematical Biosciences and Engineering, 2022, 19(9): 8923-8934. doi: 10.3934/mbe.2022414
    [9] Weiguo Liu, Xuyin Wang, Lu Li, Peizhen Zhao . A maintenance activity scheduling with time-and-position dependent deteriorating effects. Mathematical Biosciences and Engineering, 2022, 19(11): 11756-11767. doi: 10.3934/mbe.2022547
    [10] Tianyu Cheng, Xingfu Zou . A new perspective on infection forces with demonstration by a DDE infectious disease model. Mathematical Biosciences and Engineering, 2022, 19(5): 4856-4880. doi: 10.3934/mbe.2022227
  • Recent experience of the Ebola outbreak in 2014 highlighted the importance of immediate response measure to impede transmission in the early stage. To this aim, efficient and effective allocation of limited resources is crucial. Among the standard interventions is the practice of following up with the recent physical contacts of the infected individuals -- known as contact tracing. In an effort to understand the effects of contact tracing protocols objectively, we explicitly develop a model of Ebola transmission incorporating contact tracing. Our modeling framework is individual-based, patient-centric, stochastic and parameterizable to suit early-stage Ebola transmission. Notably, we propose an activity driven network approach to contact tracing, and estimate the basic reproductive ratio of the epidemic growth in different scenarios. Exhaustive simulation experiments suggest that early contact tracing paired with rapid hospitalization can effectively impede the epidemic growth. Resource allocation needs to be carefully planned to enable early detection of the contacts and rapid hospitalization of the infected people.


    Scheduling models with setup times are widely used in manufacture and operational processes (see Allahverdi et al. [1] and Allahverdi [2]). Koulamas and Kyparisis [3,4] and Biskup and Herrmann [5] investigated single-machine scheduling with past-sequence-dependent setup times (~psdst). They showed that several regular objective function minimizations remain polynomially solvable. Wang [6] and Wang and Li [7] examined single-machine problems with learning effects and ~psdst. Hsu et al. [8] studied unrelated parallel machine scheduling problems with learning effects and ~psdst. They proved that the total completion time minimization remains polynomially solvable. Cheng et al. [9] investigated scheduling problems with ~psdst and deterioration effects in a single machine. Huang et al. [10] and Wang and Wang [11] studied scheduling jobs with ~psdst, learning and deterioration effects. They showed that the single-machine makespan and the sum of the αth (α>0) power of job completion times minimizations remain polynomially solvable. Wang et al. [12] dealt with scheduling with ~psdst and deterioration effects. Under job rejection, they showed that the the sum of scheduling cost and rejection cost minimization can be solved in polynomial time.

    In the real production scheduling, the jobs often have due dates (see Gordon et al. [13,14] and the recent survey papers Rolim and Nagano [15], and Sterna [16]). Recently, Wang [17] and Wang et al. [18] studied single-machine scheduling problems with ~psdst and due-date assignment. Under common, slack and different due-date assignment methods, Wang [17] proved that the linear weighted sum of earliness-tardiness, number of early and delayed jobs, and due date penalty minimization can be solved in polynomial time. Under common and slack due date assignment methods, Wang et al. [18] showed that the weighted sum of earliness, tardiness and due date minimization can be solved in polynomial time, where the weights are position-dependent weights. The real application of the position-dependent weights can be found in production services and resource utilization (see Brucker [19], Liu et al. [20] and Jiang et al. [21]). Hence, it would be interesting to investigate due date assignment scheduling with ~psdst and position-dependent weights. The purpose of this article is to determine the optimal due dates and job sequence to minimize the weight sum of generalized earliness-tardiness penalties, where the weights are position-dependent weights. The contributions of this study are given as follows:

    We focus on the due date assignment single-machine scheduling problems with ~psdst and position-dependent weights;

    We provide an analysis for the non-regular objective function (including earliness, tardiness, number of early and delayed jobs, and due date cost);

    We derive the structural properties of the position-dependent weights and show that three due date assignments can be solved in polynomial time, respectively.

    The problem formulation is described in Section 2. Three due-date assignments are discussed in Section 3. An example is presented in Section 4. In Section 5, the conclusions are given.

    The symbols used throughout the article are introduced in Table 1.

    Table 1.  Symbols used in this article.
    Symbol Meaning
    N number of jobs
    Jl index of job
    pl processing time of Jl
    ~psdst past-sequence-dependent setup times
    sl setup time of ~psdst of Jl
    Cl completion time of Jl
    β a normalizing constant
    dl due date of Jl
    d common due date
    q common flow allowance
    [l] lth position in a sequence
    Ll=Cldl lateness of Jl
    Ul earliness indicator viable of Jl
    Vl tardiness indicator viable of job Jl
    ζl positional-dependent weight of lateness cost
    ηl (θl) positional-dependent weight of earliness (tardiness) indicator viable
    ϑl positional-dependent weight of due date cost
    ϱ sequence of all jobs
    ~con (~slk,~dif) common (slack, different) due date

     | Show Table
    DownLoad: CSV

    Suppose there are N independent jobs ˜V={J1,J2,,JN} need to be processed on a single-machine. The ~psdst setup time s[l] of job J[l] is s[l]=βl1j=1p[j], where β0 is a normalizing constant, s[1]=0, and βl1j=1p[j]+p[l] is the total processing requirement of job J[l]. Let Ll=Cldl denote the lateness of job Jl, Ul (Vl) be earliness (tardiness) indicator viable of job Jl, i.e., if Cl<dl, Ul=1, otherwise, Ul=0; if Cl>dl, Vl=1, otherwise, Vl=0.

    For the common (~con) due date assignment, dl=d (l=1,2,,N) and d is a decision variable. For the slack (~slk) due date assignment, dl=sl+pl+q and q is a decision variable. For the different due date (~dif) assignment, dl is a decision variable for l=1,2,,N. The target is to determine dl and a sequence ϱ such that is minimized.

    M=Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), (1)

    where ζl0, ηl0, ηl0 and δl0 are given positional-dependent weight constants. From Pinedo [22], the problem can be defined as:

    1|~psdst,H|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), (2)

    where H{~con,~slk,~dif}. The literature review related to the scheduling problems with ~psdst and due date assignment is given in Table 2. For a given sequence ϱ=(J[1],J[2],,J[N]), from (Wang [17]), we have

    C[l]=lj=1(s[j]+p[j])=lj=1[1+β(lj)]p[j],l=1,2,,N. (3)
    Table 2.  Problems with ~psdst and due date assignment.
    Problem Complexity Reference
    1|~psdst,~con|Nl=1(˜αEl+˜δTl+˜ηlUl+˜θlVl+˜ϑd) O(N4) Wang [17]
    1|~psdst,~con|Nl=1(˜αEl+˜δTl+˜ϑd) O(NlogN) Wang [17]
    1|~psdst,~slk|Nl=1(˜αEl+˜δTl+˜ηlUl+˜θlVl+˜ϑq) O(N4) Wang [17]
    1|~psdst,~slk|Nl=1(˜αEl+˜δTl+˜ϑq) O(NlogN) Wang [17]
    1|~psdst,~dif|Nl=1(˜αEl+˜δTl+˜ηlUl+˜θlVl+˜ϑdj) O(NlogN) Wang [17]
    1|~psdst,~con|Nl=1ζl|L[l]|+˜ϑd O(NlogN) Wang et al. [18]
    1|~psdst,~slk|Nl=1ζl|L[l]|+˜ϑq O(NlogN) Wang et al. [18]
    1|~psdst,~con|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) O(N4) This paper
    1|~psdst,~con|Nl=1(ζl|L[l]|+ϑld[l]) O(NlogN) This paper
    1|~psdst,~slk|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) O(N4) This paper
    1|~psdst,~slk|Nl=1(ζl|L[l]|+ϑld[l]) O(NlogN) This paper
    1|~psdst,~dif|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) O(NlogN) This paper

     | Show Table
    DownLoad: CSV

    where ˜α,˜δ,˜ϑ are given constants, ˜ηl (˜θl) is the earliness (tardiness) penalty of job Jl, El=max{0,dlCl} (Tl=max{0,Cldl}) is the earliness (tardiness) of job Jl.

    Lemma 1. For 1|~psdst,H|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) (H{~con,~slk,~dif}), an optimal sequence exists such that the first job is processed at time zero and contains no machine idle time.

    Proof. The result is obvious (see Brucker [19] and Liu et al. [20]).

    Lemma 2. For any given sequence ϱ, the optimal d is equal to the completion time of some job, i.e., d=C[a], a=1,2,,N.

    Proof. For any given sequence ϱ=(J[1],J[2],,J[N]), suppose that d is not equal to the completion time of some job, i.e., C[a]<d<C[a+1], 0a<n, C[0]=0, we have

    M=al=1ζl(dC[l])+Nl=a+1ζl(C[l]d)+aj=1ηl+nj=a+1θl+Nl=1dϑl.

    (i) When d=C[a], we have

    M1=al=1ζl(C[a]C[l])+Nl=a+1ζl(C[l]C[a])+a1l=1ηl+nl=a+1θl+Nl=1C[a]ϑl.

    (ii) When d=C[a+1], we have

    M2=al=1ζl(C[a+1]C[l])+Nl=a+1ζl(C[l]C[a+1])+al=1ηl+nl=a+2θl+Nl=1C[a+1]ϑl,
    MM1=al=1ζl(dC[a])Nl=a+1ζl(dC[a])+ηa+Nl=1ϑl(dC[a])=(al=1ζlNl=a+1ζl+Nl=1ϑl)(dC[a])+ηa

    and

    MM2=al=1ζl(dC[a+1])Nl=a+1ζl(dC[a+1])+θa+1+Nl=1ϑl(dC[a+1])=(al=1ζlNl=a+1ζl+Nl=1ϑl)(dC[a+1])+θa+1.

    If al=1ζlNl=a+1ζl+Nl=1ϑl0 and C[a]<d<C[a+1], then MM10; If al=1ζlNl=a+1ζl+Nl=1ϑl0 and C[a]<d<C[a+1], then MM20. Therefore, d is the completion time of some job.

    Lemma 3. For any given sequence ϱ=(J[1],J[2],,J[N]), if θl=ϑl=0 (l=1,2,N), there exists an optimal common due date d=C[a], where a is determined by

    a1l=1ζlNl=aζl+Nl=1ϑl0 (4)

    and

    al=1ζlNl=a+1ζl+Nl=1ϑl0. (5)

    Proof. From Lemma 2, when d=C[a], we have

    M=a1l=1ζl(C[a]C[l])+Nl=a+1ζl(C[l]C[a])+Nl=1C[a]ϑl.

    (i) When d reduces ε (i.e., d=C[a]ε), we have

    M=a1l=1ζl(C[a]εC[l])+Nl=aζl(C[l]C[a]+ε)+Nl=1(C[a]ε)ϑl.

    (ii) When d increases ε (i.e., d=C[a]+ε), we have

    M=al=1ζl(C[a]+εC[l])+Nl=a+1ζl(C[l]C[a]ε)+Nl=1(C[a]+ε)ϑl.

    Hence, we have

    MM=ε(a1l=1ζlNl=aζl+Nl=1ϑl)0
    MM=ε(al=1ζlNl=a+1ζl+Nl=1ϑl)0,

    i.e., a is determined by a1l=1ζlNl=aζl+Nl=1ϑl0 and al=1ζlNl=a+1ζl+Nl=1ϑl0.

    From Lemma 2, if d=C[a], the objective function is:

    M=Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+dϑl)=a1l=1ζl(C[a]C[l])+Nl=a+1ζl(C[l]C[a])+a1l=1ηl+Nl=a+1θl+Nl=1C[a]ϑl=a1l=1ζl{aj=1[1+β(aj)]p[j]lj=1[1+β(lj)]p[j]}+Nl=a+1ζl{lj=1[1+β(lj)]p[j]aj=1[1+β(aj)]p[j]}+a1l=1ηl+Nl=a+1θl+Nl=1ϑl{aj=1[1+β(aj)]p[j]}=Nl=1Ψlp[l]+a1l=1ηl+Nl=a+1θl, (6)

    where

    Ψl={β(a1)ζ1+β(a2)ζ2+β(a3)ζ3++βζa1+βζa+1+2βζa+2++β(Na)ζN+[1+β(a1)]Nj=1ϑj,l=1,(1+β(a2))ζ1+β(a2)ζ2+β(a3)ζ3++βζa1+βζa+1+2βζa+2++β(Na)ζN+[1+β(a2)]Nj=1ϑj,l=2,(1+β(a3))(ζ1+ζ2)+β(a3)ζ3+βζa1+βζa+1+2βζa+2++β(Na)ζN+[1+β(a3)]Nj=1ϑj,l=3,(1+β)(ζ1+ζ2++ζa2)+βζa1+βζa+1+2βζa+2++β(Na)ζN+(1+β)Nj=1ϑj,l=a1,ζ1+ζ2++ζa1+βζa+1+2βζa+2++β(Na)ζN+Nj=1ϑj,l=a,ζa+1+(1+β)ζa+2+(1+2β)ζa+3++(1+β(Na1))ζN,l=a+1,ζa+2+(1+β)ζa+3+(1+2β)ζa+4++(1+β(Na2))ζN,l=a+2,ζN1+(1+β)ζN,N1,ζN,N. (7)

    Let xl,r=1 if Jl is placed in rth position, and xl,r=0; otherwise. From Eq (6), the optimalsequence of 1|~psdst,~con|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) can be formulatedasthe following assignmentproblem:

    Min Nl=1Nr=1Θl,rxl,r (8)
    s.t.{Nh=1xl,r=1,r=1,2,...,N,Nr=1xl,r=1,l=1,2,...,N,xl,r=0or1, (9)

    where

    Θl,r={Ψrpl+ηr,r=1,2,...,a1,Ψrpl,r=a,Ψrpl+θr,r=a+1,a+2,...,N, (10)

    and Ψr is given by Eq (7).

    Based on the above analysis, to solve 1|~psdst,~con|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), Algorithm 1 was summarized as follows:

    Algorithm 1
    Require: β, pl,ζl,ηl,θl,ϑl for 1lN.
    Ensure: An optimal sequence ϱ, optimal common due date d.
    Step 1. For each a (a=1,2,,N), calculate Ψr (see Eq (7)) and Θl,r (see Eq (10)), to solve the assignment problem (8)–(10), a suboptimal sequence ϱ(a) and objective function value M(a) can be obtained.
    Step 2. The (global) optimal sequence (i.e., ϱ) is the one with the minimum value
    M=min{M(a)|a=1,2,,N}.
    Step 3. Set d=C[a].

     | Show Table
    DownLoad: CSV

    Theorem 1. The 1|~psdst,~con|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) can be solved by Algorithm 1, and time complexity was O(N4).

    Proof. The correctness of Algorithm 1 follows the above analysis. In Step 1, for each a, solving the assignment problem needs O(N3) time; Steps 2 and 3 require O(N) time; a=1,2,,N. Therefore, the total time complexity was O(N4).

    Lemma 4. (Hardy et al. [23]). "The sum of products Nl=1albl is minimized if sequence a1,a2,,aN is ordered nondecreasingly and sequence b1,b2,,bN is ordered nonincreasingly or vice versa."

    If ηl=θl=0, a can be determined by Lemma 3 (see Eqs (4) and (5)), We

    M=Nl=1(ζl|L[l]|+ϑld[l])=Nl=1Ψlp[l], (11)

    where Ωj is given by Eq (6).

    Equation (11) can be minimized by Lemma 4 in O(NlogN) time (i.e., al=Ψl,bl=pl), hence, to solve 1|~psdst,~con|Nl=1(ζl|L[l]|+ϑld[l]), the following algorithm was summarized as follows:

    Theorem 2. The 1|~psdst,~con|Nl=1(ζl|L[l]|+ϑld[l]) can be solved by Algorithm 2, and time complexity was O(NlogN).

    Algorithm 2
    Require: β, pl,ζl,ϑl for 1lN.
    Ensure: An optimal sequence ϱ, optimal common due date d.
    Step 1. Calculate a by Lemma 3 (see Eqs (4) and (5)).
    Step 2. By using Lemma 4 (let al=Ψl,bl=pl) to determine the optimal job sequence (i.e., ϱ), i.e., place the largest pl at the smallest Ψl position, place the second largest pl at the second smallest Ψl position, etc.
    Step 3. Set d=C[a].

     | Show Table
    DownLoad: CSV

    Similarly, we have

    Lemma 5. For any given sequence ϱ of 1|~psdst,~slk|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), an optimal sequence exists in which

    1) C[l]d[l] implies C[l1]d[l1] and C[l]d[l] implies C[l+1]d[l+1] for all l;

    2) the optimal q is equal to the completion time of some job, i.e., q=C[b1], b=1,2,,N.

    Lemma 6. For any given sequence ϱ=(J[1],J[2],,J[N]), if θl=ϑl=0 (l=1,2,N), there exists an optimal common due date q=C[b1], where b is determined by

    b1l=1ζlNl=bζl+Nl=1ϑl0 (12)

    and

    bl=1ζlNl=b+1ζl+Nl=1ϑl0. (13)

    Proof. From Lemma 5, when q=C[b1], we have

    M=b1l=1ζl(s[b]+p[b]+C[b1]C[l])+Nl=b+1ζl(C[l]s[b]p[b]C[b1])+Nl=1ϑl(s[b]+p[b]+C[b1]).

    (i) When q reduces ε (i.e., q=C[b1]ε), we have

    M=b1l=1ζl(s[b]+p[b]+C[b1]εC[l])+Nl=bζl(C[l]s[b]p[b]C[b1]+ε)+Nl=1(s[b]+p[b]+C[b1]ε)ϑl.

    (ii) When q increases ε (i.e., q=C[b1]+ε), we have

    M=bl=1ζl(s[b]+p[b]+C[b1]+εC[l])+Nl=b+1ζl(C[l]s[b]p[b]C[b1]ε)+Nl=1(s[b]+p[b]+C[b1]+ε)ϑl.

    Hence, we have

    MM=ε(b1l=1ζlNl=bζl+Nl=1ϑl)0
    MM=ε(bl=1ζlNl=b+1ζl+Nl=1ϑl)0,

    i.e., b is determined by b1l=1ζlNl=bζl+Nl=1ϑl0 and bl=1ζlNl=b+1ζl+Nl=1ϑl0.

    From Lemma 5, if q=C[b1] (i.e., d[l]=s[l]+p[l]+C[b1]), the objective function is:

    M=Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])=b1l=1ζl(s[l]+p[l]+C[b1]C[l])+Nl=b+1ζl(C[l]s[l]p[l]C[b1])+b1l=1ηl+Nl=b+1θl+Nl=1(s[l]+p[l]+C[b1])ϑl=b1l=1ζl(C[b1]C[l1])+Nl=b+1ζl(C[l1]C[b1])+b1l=1ηl+Nl=b+1θl+Nl=1(s[l]+p[l])ϑl+Nl=1C[b1]ϑl=b1l=1ζl{b1j=1[1+β(b1j)]p[j]l1j=1[1+β(l1j)]p[j]}+Nl=b+1ζl{l1j=1[1+β(l1j)]p[j]b1j=1[1+β(b1j)]p[j]}+b1l=1ηl+Nl=b+1θl+Nl=1(βl1j=1p[j]+p[l])ϑl+Nl=1ϑl{b1j=1[1+β(b1j)]p[j]}=Nl=1Φlp[l]+b1l=1ηl+Nl=b+1θl, (14)

    where

    Φl={(1+β(b2))ζ1+β(b2)ζ2+β(b3)ζ3++βζb1+βζb+1+2βζb+2++β(Nb)ζN+[1+β(b2)]Nj=1ϑj+ϑ1+βNj=2ϑj,l=1,(1+β(b3))(ζ1+ζ2)+β(b3)ζ3+β(b4)ζ4++βζb1+βζb+1+2βζb+2++β(Nb)ζN+[1+β(b3)]Nj=1ϑj+ϑ2+βNj=3ϑj,l=2,(1+β(b4))(ζ1+ζ2+ζ3)+β(b4)ζ4++βζb1+βζb+1+2βζb+2++β(Nb)ζN+[1+β(b4)]Nj=1ϑj+ϑ3+βNj=4ϑj,l=3,(1+β)(ζ1+ζ2++ζb2)+βζb1+βζb+1+2βζb+2++β(Nb)ζN+(1+β)Nj=1ϑj+ϑb2+βNj=b1ϑj,l=b2,ζ1+ζ2++ζb1+βζb+1+2βζb+2++β(Nb)ζN+Nj=1ϑj+ϑb1+βNj=bϑj,l=b1,ζb+1+(1+β)ζb+2+(1+2β)ζb+3++(1+β(Nb1))ζN+ϑb+βNj=b+1ϑj,l=b,ζb+2+(1+β)ζb+3+(1+2β)ζb+4++(1+β(Nb2))ζN+ϑb+1+βNj=b+2ϑj,l=b+1,ζN+ϑN1+βϑN,N1,ϑN,N. (15)

    Similarly, from Eq (14), the optimal sequence of 1|~psdst,~slk|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) can be obtained as follows:

    Min Nl=1Nr=1Ξl,rxl,r (16)
    s.t.{Nh=1xl,r=1,r=1,2,...,N,Nr=1xl,r=1,l=1,2,...,N,xl,r=0or1, (17)

    where

    Ξl,r={Φrpl+ηr,r=1,2,...,b1,Φrpl,r=b,Φrpl+θr,r=b+1,b+2,...,N, (18)

    and Φr is given by (15).

    Similarly, to solve 1|~psdst,~slk|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), the following algorithm can be proposed:

    Theorem 3. The 1|~psdst,~slk|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) can be solved by Algorithm 3, and time complexity was O(N4).

    Algorithm 3
    Require: β, pl,ζl,ηl,θl,ϑl for 1lN.
    Ensure: An optimal sequence ϱ, optimal common flow allowance q.
    Step 1. For each b (b=1,2,,N), calculate Φr (see Eq (15)) and Ξl,r (see Eq (18)), to solve the assignment problem (16)–(18), a suboptimal sequence ϱ(b) and objective function value M(b) can be obtained.
    Step 2. The (global) optimal sequence (i.e., ϱ) is the one with the minimum value
    M=min{M(b)|b=1,2,,N}.
    Step 3. Set q=C[b1].

     | Show Table
    DownLoad: CSV

    Similarly, if ηl=θl=0, we have

    Theorem 4. The problem 1|~psdst,~slk|Nl=1(ζl|L[l]|+ϑld[l]) can be solved in O(NlogN) time.

    Lemma 7. For a given sequence π of 1|~psdst,~dif|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]), an optimal solution exists such that d[l]C[l].

    Proof. For a given sequence ϱ, the objective function for job J[l] was:

    M[l]=ζl|C[l]d[l]|+ηlU[l]+θlV[l]+ϑld[l]. (19)

    If d[l]>C[l] (i.e., the job J[l] is an early job), it follows that

    M[l]=ζl(d[l]C[l])+ηlU[l]+ϑld[l].

    Move d[l] to the left such that d[l]=C[l], we have

    M[l]=ϑld[l]=ϑlC[l]<M[l],

    therefore, d[l]C[l].

    Lemma 8. For a given sequence ϱ, if ϑlζl, d[l]=0; otherwise d[l]=C[l] (l=1,2,,N).

    Proof. For a given sequence ϱ, from Lemma 7, we have d[l]C[l] and

    M[l]=ζl(C[l]d[l])+θlV[l]+ϑld[l]=ζlC[l]+θl+(ϑlζl)d[l]. (20)

    From Eq (20), when ϑlζl0, d[l] was equal to 0; otherwise, then d[l] was equal to C[l].

    From Lemma 8, if ϑlζl, we have d[l]=0 and

    M=Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])=Nl=1ζlC[l]+Nl=1θl. (21)

    If ϑl<ζl, we have d[l]=C[l] and

    M=Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])=Nl=1ϑlC[l]. (22)

    From Eqs (21) and (22), minimizing Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) is equal to minimizing the expression

    M=Nl=1min{ϑl,ζl}C[l]=Nl=1min{ϑl,ζl}lj=1[1+β(lj)]p[j]=Nl=1Υlp[l], (23)

    where

    Υl={min{ϑ1,ζ1}+(1+β)min{ϑ2,ζ2}++(1+(N1)β)min{ϑN,ζN},l=1,min{ϑ2,ζ2}+(1+β)min{ϑ3,ζ3}++(1+(N2)β)min{ϑN,ζN},l=2,min{ϑN1,ζN1}+(1+β)min{ϑN,ζN},N1,min{ϑN,ζN},N, (24)

    i.e.,

    Υl=Nj=l[1+β(jl)]min{ϑj,ζj},    l=1,2,,N. (24')

    Obviously, Eq (23) can be minimized by Lemma 4.

    Theorem 5. The 1|~psdst,~dif|Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) can be solved by Algorithm 4, and time complexity was O(NlogN).

    Algorithm 4
    Require: β, pl,ζl,ηl,θl,ϑl for 1lN.
    Ensure: An optimal sequence ϱ, optimal common due date dl.
    Step 1. By using Lemma 4 (let al=Υl,bl=pl) to determine the optimal job sequence (i.e., ϱ), i.e., place the largest pl at the smallest Υl position, place the second largest pl at the second smallest Υl position, etc.
    Step 2. If ϑlζl, d[l]=0; otherwise d[l]=C[l] (l=1,2,,N).

     | Show Table
    DownLoad: CSV

    We present an example to illustrate the calculation steps and results of the three due date assignments.

    Example 1. Consider a 6-job problem, where β=1, p1=7, p2=9, p3=4, p4=6, p5=8, p6=5, ζl,ηl,θl and ϑl are given in Table 3.

    Table 3.  Values of ζl,ηl,θl and ϑl.
    l=1 l=2 l=3 l=4 l=5 l=6
    ζl 6 8 14 3 15 7
    ηl 8 4 9 10 12 5
    θl 10 8 6 5 14 17
    ϑl 12 16 7 13 8 9

     | Show Table
    DownLoad: CSV

    From Algorithm 1, For the ~con assignment, if a=1, the values Ψ1=205,Ψ2=140,Ψ3=93,Ψ4=54,Ψ5=29,Ψ6=7, (see Eqs (7) or (7')) and Θl,r (see Eq (10)) are given in Table 4. By the assignment problems (8)–(10), the sequence is ϱ(1)=(J3,J6,J4,J1,J5,J2) and M(1)=2801. Similarly, for a=2,3,4,5,6, the results are shown in Table 5. From Table 5, the optimal sequence is ϱ=(J3,J6,J4,J1,J5,J2), M=2801 and d=C[2]=14.

    Table 4.  Values Θl,r for a=1.
    r=1 r=2 r=3 r=4 r=5 r=6
    J1 1435 988 657 383 217 66
    J2 1845 1268 843 491 275 80
    J3 820 568 378 221 130 45
    J4 1230 848 564 329 188 59
    J5 1640 1128 750 437 246 73
    J6 1025 708 471 275 159 52

     | Show Table
    DownLoad: CSV
    Table 5.  Results for ~con.
    a ϱ(a) M(a)
    1 (J3,J6,J4,J1,J5,J2) 2801
    2 (J3,J6,J4,J1,J5,J2) 3017
    3 (J3,J6,J4,J1,J5,J2) 3615
    4 (J3,J6,J4,J1,J5,J2) 5335
    5 (J3,J6,J4,J1,J5,J2) 7451
    6 (J3,J6,J4,J1,J5,J2) 11,382

     | Show Table
    DownLoad: CSV

    For the ~slk assignment, the results are shown in Table 6. From Table 6, the optimal sequence is ϱ=(J3,J6,J4,J1,J5,J2), M=2832 and q=C[0]=0.

    Table 6.  Results for ~slk.
    b ϱ(b) M(b)
    1 (J3,J6,J4,J1,J5,J2) 2832
    2 (J3,J6,J4,J1,J5,J2) 2928
    3 (J3,J6,J4,J1,J5,J2) 3286
    4 (J3,J6,J4,J1,J5,J2) 4310
    5 (J3,J6,J4,J1,J5,J2) 5934
    6 (J3,J6,J4,J1,J5,J2) 9049

     | Show Table
    DownLoad: CSV

    For the ~dif assignment, Υ1=137,Υ2=98,Υ3=65,Υ4=40,Υ5=22,Υ6=7, the optimal sequence is ϱ=(J3,J6,J4,J1,J5,J2), M^* = 1987 , d_3^* = 0 , d_6^* = 0 , d_4^* = {C}_{4} = 28 , d_1^* = 0 , d_5^* = {C}_{5} = 80 and d_2^* = 0 .

    Under \widetilde{con} , \widetilde{slk} and \widetilde{dif} assignments, the single-machine scheduling problem with \widetilde{psdst} and position-dependent weights had been addressed. The goal was to minimize the weighted sum of lateness, number of early and delayed jobs and due date cost. Here we showed that the problem remains polynomially solvable. If the due dates are given, from Brucker [19], the problem 1|{\widetilde{psdst}}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}\right) is NP-dard. For future research, we suggest some interesting topics as follows:

    1) Considering the problem 1|{\widetilde{psdst}}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}\right) ;

    2) Investigating the problem in a flow shop setting;

    3) Studying the group technology problem with learning effects (deterioration effects) and/or resource allocation (see Wang et al. [24], Huang [25] and Liu and Xiong [26]);

    4) Investigating scenario-dependent processing times (see Wu et al. [27] and Wu et al. [28]).

    This research was supported by the National Natural Science Regional Foundation of China (71861031 and 72061029).

    The authors declare that they have no conflicts of interest.

    [1] [ C. Browne,H. Gulbudak,G. Webb, Modeling contact tracing in outbreaks with application to Ebola, Journal of Theoretical Biology, 384 (2015): 33-49.
    [2] [ G. Chowell,C. Viboud, Is it growing exponentially fast?-Impact of assuming exponential growth for characterizing and forecasting epidemics with initial near-exponential growth dynamics, Infectious Disease Modelling, 1 (2016): 71-78.
    [3] [ O. Diekmann,J. A. P. Heesterbeek,J. A. J. Metz, On the definition and the computation of the basic reproduction ratio R_{0} in models for infectious diseases in heterogeneous populations, Journal of Mathematical Biology, 28 (1990): 365-382.
    [4] [ M. G. Dixon,I. J. Schafer, Ebola Viral Disease Outbreak - West Africa, 2014, MMWR Morb Mortal Wkly Rep, 63 (2014): 548-551.
    [5] [ K. T. Eames,M. J. Keeling, Contact tracing and disease control, Proceedings of the Royal Society of London B: Biological Sciences, 270 (2003): 2565-2571.
    [6] [ F. O. Fasina, A. Shittu, D. Lazarus, O. Tomori, L. Simonsen, C. Viboud and G. Chowell, Transmission dynamics and control of Ebola virus disease outbreak in Nigeria, July to September 2014, Eurosurveillance, 19 (2014), 20920.
    [7] [ M. Greiner,D. Pfeiffer,R. D. Smith, Principles and practical application of the receiver-operating characteristic analysis for diagnostic tests, Preventive Veterinary Medicine, 45 (2000): 23-41.
    [8] [ J. M. Heffernan,R. J. Smith,L. M. Wahl, Perspectives on the basic reproductive ratio, Journal of the Royal Society Interface, 2 (2005): 281-293.
    [9] [ M. J. Keeling and P. Rohani, Modeling Infectious Diseases in Humans and Animals, Princeton University Press, Princeton, NJ, 2008.
    [10] [ I. Z. Kiss,D. M. Green,R. R. Kao, Disease contact tracing in random and clustered networks, Proceedings of the Royal Society of London B: Biological Sciences, 272 (2005): 1407-1414.
    [11] [ D. Klinkenberg,C. Fraser,H. Heesterbeek, The effectiveness of contact tracing in emerging epidemics, PloS One, 1 (2006): e12.
    [12] [ S. Liu,N. Perra,M. Karsai,A. Vespignani, Controlling contagion processes in activity driven networks, Physical review letters, 112 (2014): 118702.
    [13] [ A. S. da Mata and R. Pastor-Satorras, Slow relaxation dynamics and aging in random walks on activity driven temporal networks, The European Physical Journal B, 88 (2015), Art. 38, 8 pp.
    [14] [ N. Perra, B. Gonçalves, R. Pastor-Satorras and A. Vespignani, Activity Driven Modeling of Time Varying Networks, Scientific Reports, 2012.
    [15] [ N. Perra,A. Baronchelli,D. Mocanu,B. Gonc'calves,R. Pastor-Satorras,A. Vespignani, Random walks and search in time-varying networks, Physical review letters, 109 (2012): 238701.
    [16] [ A. Rizzo,B. Pedalino,M. Porfiri, A network model for Ebola spreading, Journal of theoretical biology, 394 (2016): 212-222.
    [17] [ A. Rizzo,M. Frasca,M. Porfiri, Effect of individual behavior on epidemic spreading in activity-driven networks, Physical Review E, 90 (2014): 042801.
    [18] [ A. Rizzo and M. Porfiri, Toward a realistic modeling of epidemic spreading with activity driven networks, in Temporal Network Epidemiology (N. Masuda and P. Holme), Springer, (2017), 317-319.
    [19] [ N. M. Shahtori,C. Scoglio,A. Pourhabib,F. D. Sahneh, Sequential Monte Carlo filtering estimation of Ebola progression in West Africa, American Control Conference(ACC), null (2016): 1277-1282.
    [20] [ M. D. Shirley,S. P. Rushton, The impacts of network topology on disease spread, Ecological Complexity, 2 (2005): 287-299.
    [21] [ F. Shuaib,R. Gunnala,E. O. Musa,F. J. Mahoney,O. Oguntimehin,P. M. Nguku,S. B. Nyanti,N. Knight,N. S. Gwarzo,O. Idigbe,A. Nasidi,J. F. Vertefeuille, Ebola virus disease outbreak-Nigeria, July-September 2014, MMWR Morb Mortal Wkly Rep, 63 (2014): 867-872.
    [22] [ M. Starnini,R. Pastor-Satorras, Temporal percolation in activity-driven networks, Physical Review E, 89 (2014): 032807.
    [23] [ M. Starnini,R. Pastor-Satorras, Topological properties of a time-integrated activity-driven network, Physical Review E, 87 (2013): 062807.
    [24] [ K. Sun, A. Baronchelli and N. Perra, Contrasting effects of strong ties on SIR and SIS processes in temporal networks, The European Physical Journal B, 88 (2015), Art. 326, 8 pp.
    [25] [ L. Zino,A. Rizzo,M. Porfiri, Continuous-Time Discrete-Distribution Theory for Activity-Driven Networks, Physical Review Letters, 117 (2016): 228302.
    [26] [ Cases of Ebola Diagnosed in the United States, 2014. Available from: https://www.cdc.gov/vhf/ebola/outbreaks/2014-west-africa/united-states-imported-case.html.
    [27] [ Implementation and Management of Contact Tracing for Ebola Virus Disease, Emergency Guideline by the World Health Organization, 2015. Available from: https://www.cdc.gov/vhf/ebola/pdf/contact-tracing-guidelines.pdf.
  • This article has been cited by:

    1. Xue Jia, Jing Xue, Shi-Yun Wang, Ji-Bo Wang, Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times, 2022, 19, 1551-0018, 8923, 10.3934/mbe.2022414
    2. Jia-Xuan Yan, Na Ren, Hong-Bin Bei, Han Bao, Ji-Bo Wang, Study on resource allocation scheduling problem with learning factors and group technology, 2023, 19, 1547-5816, 3419, 10.3934/jimo.2022091
    3. Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang, Resource dependent scheduling with truncated learning effects, 2022, 19, 1551-0018, 5957, 10.3934/mbe.2022278
    4. Daniel Alejandro Rossit, Fernando Tohmé, Máximo Méndez-Babey, Mariano Frutos, Diego Broz, Diego Gabriel Rossit, Special Issue: Mathematical Problems in Production Research, 2022, 19, 1551-0018, 9291, 10.3934/mbe.2022431
    5. Wei Wu, Dan-Yang Lv, Ji-Bo Wang, Two Due-Date Assignment Scheduling with Location-Dependent Weights and a Deteriorating Maintenance Activity, 2023, 11, 2079-8954, 150, 10.3390/systems11030150
    6. Zhiyong Luo, Xintong Liu, Shanxin Tan, Haifeng Xu, Jiahui Liu, Multi-Objective Multi-Stage Optimize Scheduling Algorithm for Nonlinear Virtual Work-Flow Based on Pareto, 2023, 11, 2227-9717, 1147, 10.3390/pr11041147
    7. Yifu Feng, Zonghai Hu, Rui Si, Ji-Bo Wang, Study on Due-Date Assignment Scheduling with Setup Times and General Truncated Learning Effects, 2023, 0217-5959, 10.1142/S0217595923500069
    8. Weiguo Liu, Xuyin Wang, Group Technology Scheduling with Due-Date Assignment and Controllable Processing Times, 2023, 11, 2227-9717, 1271, 10.3390/pr11041271
    9. Mümtaz İpek, İsmail Hakkı Cedimoğlu, Due Date Determination in Dynamic Job Shop Scheduling with Artificial Neural Network, 2025, 8, 2651-3927, 84, 10.38016/jista.1620633
  • Reader Comments
  • © 2018 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(4617) PDF downloads(1000) Cited by(17)

Figures and Tables

Figures(7)  /  Tables(2)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog