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.
1.
Introduction
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.
2.
Problem definition
The symbols used throughout the article are introduced in Table 1.
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]=β∑l−1j=1p[j], where β≥0 is a normalizing constant, s[1]=0, and β∑l−1j=1p[j]+p[l] is the total processing requirement of job J[l]. Let Ll=Cl−dl 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.
where ζl≥0, ηl≥0, ηl≥0 and δl≥0 are given positional-dependent weight constants. From Pinedo [22], the problem can be defined as:
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
where ˜α,˜δ,˜ϑ are given constants, ˜ηl (˜θl) is the earliness (tardiness) penalty of job Jl, El=max{0,dl−Cl} (Tl=max{0,Cl−dl}) is the earliness (tardiness) of job Jl.
3.
Main results
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]).
3.1. The 1|~psdst,~con|∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])
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], 0≤a<n, C[0]=0, we have
(i) When d=C[a], we have
(ii) When d=C[a+1], we have
and
If ∑al=1ζl−∑Nl=a+1ζl+∑Nl=1ϑl≥0 and C[a]<d<C[a+1], then M−M1≥0; If ∑al=1ζl−∑Nl=a+1ζl+∑Nl=1ϑl≤0 and C[a]<d<C[a+1], then M−M2≥0. 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
and
Proof. From Lemma 2, when d=C[a], we have
(i) When d reduces ε (i.e., d=C[a]−ε), we have
(ii) When d increases ε (i.e., d=C[a]+ε), we have
Hence, we have
i.e., a is determined by ∑a−1l=1ζl−∑Nl=aζl+∑Nl=1ϑl≤0 and ∑al=1ζl−∑Nl=a+1ζl+∑Nl=1ϑl≥0.
From Lemma 2, if d=C[a], the objective function is:
where
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:
where
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:
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
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).
3.2. The 1|~psdst,~slk|∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])
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[l−1]≤d[l−1] 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[b−1], 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[b−1], where b is determined by
and
Proof. From Lemma 5, when q=C[b−1], we have
(i) When q reduces ε (i.e., q=C[b−1]−ε), we have
(ii) When q increases ε (i.e., q=C[b−1]+ε), we have
Hence, we have
i.e., b is determined by ∑b−1l=1ζl−∑Nl=bζl+∑Nl=1ϑl≤0 and ∑bl=1ζl−∑Nl=b+1ζl+∑Nl=1ϑl≥0.
From Lemma 5, if q=C[b−1] (i.e., d[l]=s[l]+p[l]+C[b−1]), the objective function is:
where
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:
where
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).
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.
3.3. The 1|~psdst,~dif|∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l])
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:
If d[l]>C[l] (i.e., the job J[l] is an early job), it follows that
Move d[l] to the left such that d[l]=C[l], we have
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
From Eq (20), when ϑl−ζl≥0, 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
If ϑl<ζl, we have d[l]=C[l] and
From Eqs (21) and (22), minimizing ∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]+ϑld[l]) is equal to minimizing the expression
where
i.e.,
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).
4.
Numerical example
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.
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.
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.
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 .
5.
Conclusions
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]).
Acknowledgments
This research was supported by the National Natural Science Regional Foundation of China (71861031 and 72061029).
Conflict of interest
The authors declare that they have no conflicts of interest.