In this paper we examine ultimate dynamics of the four-dimensional model describing interactions between tumor cells, effector immune cells, interleukin -2 and transforming growth factor-beta. This model was elaborated by Arciero et al. and is obtained from the Kirschner-Panetta type model by introducing two various treatments. We provide ultimate upper bounds for all variables of this model and two lower bounds and, besides, study when dynamics of this model possesses a global attracting set. The nonexistence conditions of compact invariant sets are derived. We obtain bounds for treatment parameters s1,2 under which all trajectories in the positive orthant tend to the tumor-free equilibrium point. Conditions imposed on under which the tumor population persists are presented as well. Finally, we compare tumor eradication/ persistence bounds and discuss our results.
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=C4=28, d∗1=0, d∗5=C5=80 and d∗2=0.
5.
Conclusions
Under ~con, ~slk and ~dif assignments, the single-machine scheduling problem with ~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|~psdst|∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]) is NP-dard. For future research, we suggest some interesting topics as follows:
1) Considering the problem 1|~psdst|∑Nl=1(ζl|L[l]|+ηlU[l]+θlV[l]);
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.