Processing math: 55%
Research article

Effect of correlating adjacent neurons for identifying communications: Feasibility experiment in a cultured neuronal network

  • Neuronal networks have fluctuating characteristics, unlike the stable characteristics seen in computers. The underlying mechanisms that drive reliable communication among neuronal networks and their ability to perform intelligible tasks remain unknown. Recently, in an attempt to resolve this issue, we showed that stimulated neurons communicate via spikes that propagate temporally, in the form of spike trains. We named this phenomenon “spike wave propagation”. In these previous studies, using neural networks cultured from rat hippocampal neurons, we found that multiple neurons, e.g., 3 neurons, correlate to identify various spike wave propagations in a cultured neuronal network. Specifically, the number of classifiable neurons in the neuronal network increased through correlation of spike trains between current and adjacent neurons. Although we previously obtained similar findings through stimulation, here we report these observations on a physiological level. Considering that individual spike wave propagation corresponds to individual communication, a correlation between some adjacent neurons to improve the quality of communication classification in a neuronal network, similar to a diversity antenna, which is used to improve the quality of communication in artificial data communication systems, is suggested.

    Citation: Yoshi Nishitani, Chie Hosokawa, Yuko Mizuno-Matsumoto, Tomomitsu Miyoshi, Shinichi Tamura. Effect of correlating adjacent neurons for identifying communications: Feasibility experiment in a cultured neuronal network[J]. AIMS Neuroscience, 2018, 5(1): 18-31. doi: 10.3934/Neuroscience.2018.1.18

    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
  • Neuronal networks have fluctuating characteristics, unlike the stable characteristics seen in computers. The underlying mechanisms that drive reliable communication among neuronal networks and their ability to perform intelligible tasks remain unknown. Recently, in an attempt to resolve this issue, we showed that stimulated neurons communicate via spikes that propagate temporally, in the form of spike trains. We named this phenomenon “spike wave propagation”. In these previous studies, using neural networks cultured from rat hippocampal neurons, we found that multiple neurons, e.g., 3 neurons, correlate to identify various spike wave propagations in a cultured neuronal network. Specifically, the number of classifiable neurons in the neuronal network increased through correlation of spike trains between current and adjacent neurons. Although we previously obtained similar findings through stimulation, here we report these observations on a physiological level. Considering that individual spike wave propagation corresponds to individual communication, a correlation between some adjacent neurons to improve the quality of communication classification in a neuronal network, similar to a diversity antenna, which is used to improve the quality of communication in artificial data communication systems, is suggested.


    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 \widetilde{dif} assignment, \Upsilon_1 = 137, \Upsilon_2 = 98, \Upsilon_3 = 65, \Upsilon_4 = 40, \Upsilon_5 = 22, \Upsilon_6 = 7 , the optimal sequence is \varrho^* = (J_3, J_6, J_4, J_1, J_5, J_2) , 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] Bonifazi P, Goldin M, Picardo MA, et al. (2009) GABAergic hub neurons orchestrate synchrony in developing hippocampal networks.Science 326: 1419-1424.
    [2] Lecerf C (1998) The double loop as a model of a learning neural system. Proceedings World Multiconference on Systemics.Cybernetics Informatics 1: 587-594.
    [3] Choe Y (2002) Analogical Cascade: A theory on the role of the thalamo-cortical loop in brain function.Neurocomputing 52: 713-719.
    [4] Tamura S, Mizuno-Matsumoto Y, Chen YW, et al. (2009) Association and abstraction on neural circuit loop and coding.IIHMSP 10-07: 546-549 (appears in IEEE Xplore).
    [5] Thorpre S, Fize D, Marlot C (1996) Speed of processing in the human visual system.Nature 381: 520.
    [6] Cessac B, Paugam-Moisy H, Viéville T (2010) Overview of facts and issues about neural coding by spike.J Physiol-Paris 104: 5-18.
    [7] Kliper O, Horn D, Quenet B, et al. (2004) Analysis of spatiotemporal patterns in a model of olfaction.Neurocomputing 58: 1027-1032.
    [8] Fujita K, Kashimori Y, Kambara T (2007) Spatiotemporal burst coding for extracting features of spatiotemporally varying stimuli.Biol Cybern 97: 293-305.
    [9] Tyukin I, Tyukina T, Van LC (2009) Invariant template matching in systems with spatiotemporal coding: A matter of instability.Neural Networks 22: 425-449.
    [10] Mohemmed A, Schliebs S, Matsuda S, et al. (2013) Training spiking neural networks to associate spatio-temporal input–output spike patterns.Neurocomputing 107: 3-10.
    [11] Olshausen BA, Field DJ (1996) Emergence of simple-cell receptive field properties by learning a sparse code for natural images.Nature 381: 607-609.
    [12] Bell AJ, Sejnowski TJ (1997) The “independent components” of natural scenes are edge filters.Vision Res 37: 3327-3338.
    [13] Aviel Y, Horn D, Abeles M (2004) Synfire waves in small balanced networks.Neural Computation 58-60: 123-127.
    [14] Abeles M (1982) Local Cortical Circuits: An Electrophysiological study Berlin: Springer.
    [15] Abeles M (2009) Synfire chains.Scholarpedia 4: 1441Available from: http://www.scholarpedia.org/article/Synfire_chains.
    [16] Izhikevich EM (2014) Polychronization: Computation with spikes.Neural Comput 18: 245-282.
    [17] Perc M (2007) Fluctuating excitability: A mechanism for self-sustained information flow in excite arrays.Chaos Soliton Fract 32: 1118-1124.
    [18] Zhang H, Wang Q, Perc M, et al. (2013) Synaptic plasticity induced transition of spike propagation in neuronal networks.Commun Nonlinear Sci 18: 601-615.
    [19] Mizuno-Matsumoto Y, Okazaki K, Kato A, et al. (1999) Visualization of epileptogenic phenomena using crosscorrelation analysis: Localization of epileptic foci and propagation of epileptiform discharges.IEEE Trans Biomed Eng 46: 271-279.
    [20] Mizuno-Matsumoto Y, Ishijima M, Shinosaki K, et al. (2001) Transient global amnesia (TGA) in an MEG study.Brain Topogr 13: 269-274.
    [21] Nishitani Y, Hosokawa C, Mizuno-Matsumoto Y, et al. (2012) Detection of M-sequences from spike sequence in neuronal networks.Comput Intell Neurosci 2012: 167-185.
    [22] Nishitani Y, Hosokawa C, Mizuno-Matsumoto Y, et al. (2014) Synchronized code sequences from spike trains in cultured neuronal networks.Int J Eng Ind 5: 13-24.
    [23] Tamura S, Nishitani Y, Hosokawa C, et al. (2016) Simulation of code spectrum and code flow of cultured neuronal networks.Comput Intell Neurosci 2016: 1-12.
    [24] Nishitani Y, Hosokawa C, Mizuno-Matsumoto Y, et al. (2016) Classification of spike wave propagations in a cultured neuronal network: Investigating a brain communication mechanism.AIMS Neurosci 4: 1-13.
    [25] Hourani H (2004) Overview of diversity techniques in wireless communication systems, postgraduate course in radio communications.
    [26] Buzsáki G (2010) Neural syntax: cell assemblies, synapsembles, and readers.Neuron 68: 362-385.
    [27] Rumelhart DE, Hinton GE, Williams RJ (1986) Learning representations by back-propagating errors.Nature 323: 533-536.
  • 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(5492) PDF downloads(1015) Cited by(1)

Figures and Tables

Figures(11)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog