Loading [MathJax]/jax/output/SVG/jax.js
 

The four-dimensional Kirschner-Panetta type cancer model: How to obtain tumor eradication?

  • 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.

    Citation: Alexander P. Krishchenko, Konstantin E. Starkov. The four-dimensional Kirschner-Panetta type cancer model: How to obtain tumor eradication?[J]. Mathematical Biosciences and Engineering, 2018, 15(5): 1243-1254. doi: 10.3934/mbe.2018057

    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
  • 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.


    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, d3=0, d6=0, d4=C4=28, d1=0, d5=C5=80 and d2=0.

    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]).

    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] [ J. C. Arciero,T. L. Jackson,D. E. Kirschner, A mathematical model of tumor-immune evasion and siRNA treatment, Discrete Contin. Dynamic. Syst. Ser. B, 4 (2004): 39-58.
    [2] [ D. Kirschner,J. Panetta, Modelling immunotherapy of the tumor-immune interaction, J. Math. Biol., 37 (1998): 235-252.
    [3] [ D. Kirschner,A. V. Tsygvintsev, On the global dynamics of a model for tumor immunotherapy, Math. Biosci. Engin., 6 (2009): 573-583.
    [4] [ A. P. Krishchenko, Estimations of domains with cycles, Comput. & Math. Appl., 34 (1997): 325-332.
    [5] [ A. P. Krishchenko, Localization of invariant compact sets of dynamical systems, Differential Equations, 41 (2005): 1669-1676.
    [6] [ A. P. Krishchenko,K. E. Starkov, Localization of compact invariant sets of the Lorenz system, Phys. Lett. A, 353 (2006): 383-388.
    [7] [ A. P. Krishchenko,K. E. Starkov, On the global dynamics of a chronic myelogenous leukemia model, Commun. Nonlin. Sci. Numer. Simul., 33 (2016): 174-183.
    [8] [ F. Salazar-Onfray, Interleukin-10: A cytokine used by tumors to escape immunosurveillance, Medical Oncology, 16 (1999): 86-94.
    [9] [ K. E. Starkov, On dynamic tumor eradication conditions under combined chemical/anti-angiogenic therapies, Phys. Lett. A, 382 (2018): 387-393.
    [10] [ K. E. Starkov,S. Bunimovich-Mendrazitsky, Dynamical properties and tumor clearance conditions for a nine-dimensional model of bladder cancer immunotherapy, Math. Biosci. Eng., 13 (2016): 1059-1075.
    [11] [ K. E. Starkov,D. Gamboa, Localization of compact invariant sets and global stability in analysis of one tumor growth model, Mathematical Methods in the Applied Sciences, 37 (2014): 2854-2863.
    [12] [ K. E. Starkov and L. Jimenez Beristain, Dynamic analysis of the melanoma model: from cancer persistence to its eradication Internat. J. Bifur. Chaos Appl. Sci. Engrg. , 27 (2017), 1750151, 11pp.
    [13] [ K. E. Starkov,A. P. Krishchenko, On the global dynamics of one cancer tumor growth model, Commun. Nonlin. Sci. Numer. Simul., 19 (2014): 1486-1495.
    [14] [ K. E. Starkov,A. P. Krishchenko, Ultimate dynamics of the Kirschner-Panetta model: Tumor eradication and related problems, Phys. Lett. A, 381 (2017): 3409-3416.
    [15] [ K. E. Starkov,A. Pogromsky, Global dynamics of the Owen-Sherratt model describing the tumor-macrophage interactions, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 23 (2013): 1350020, 9pp.
    [16] [ K. E. de Visser,W. M. Kast, Effects of TGF-ß on the immune system: Implications for cancer immunotherapy, Journal of Immunotherapy, 20 (1997): 165-177.
    [17] [ S. Wojtowicz-Praga, Reversal of tumor-induced immunosuppression: A new approach to cancer therapy, Journal of Immunotherapy, 20 (1997): 165-177.
  • 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(4214) PDF downloads(987) Cited by(3)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog