一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题.第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小.本文证明该问题可在O(n1n2(n1 n2))时间内求解.     

一个具有两类工件的多目标排序的NP-困难性

文章考虑具有两个工件集的单机排序问题.第一个工件集J1以加权完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小,并证明该问题是强NP-困难的.     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

关于总误工损失的两个代理单机排序问题

研究了与总误工损失相关的两个代理的单机排序问题。第一个代理以工件的总误工损失为目标函数,第二个代理以工件的总完工时间或总误工工件数为目标函数。目标是寻找一个排序,使得在第二个代理的目标函数不超过给定的上界的条件下,第一个代理的目标函数值最小。对这两个与总误工损失相关的两个代理的单机排序问题,分别给出它们的拟多项式时间的动态规划算法。     

原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

具有错位限制且工件可退化的单机重新排序问题

重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

一类积分不等式及其应用

研究了一类新的非线性延迟积分不等式φ(u(t))≤(n_1(t)+∫_o~(a(t)) f_1(s)w_1(u(s))ds)(n_2(t)+∫_o~t f_2(s)w_2)(u9(s))ds),t∈R_+得到了新的结论,推广了已有的若干结果.并举例说明其应用.     

多小波采样定理的拓展

采样定理在数字信号通讯中发挥了十分重要的作用,因为信号通常由它的离散采样数据来恢复.Han Bin等人在[J.Comput.Appl.Math.,2009,227:254-270]中构造了广义插值加细函数向量.本文研究与广义插值加细函数向量有关的采样定理的拓展问题.具体而言,对于已知的广义插值d-加细函数向量φ=(φ_1,…,φ_r)~T,即φe(m/r+k)=δ_kδ_(e-1-m),k∈Z,m=0,1,…,r-1,e=1,…,r我们将构造一组函数{φ_(r+1),…,φ_(dr)},使得φ~ロ=(φ~T,φ_(r+1),…,φ_(dr))~T也是d-加细的,而且满足φ_e(m/(dr)+k)=δ_kδ_(θ_(d,r(e)-m))k∈Z,m=0,1,…,dr-1,e=r+1,…,dr,其中θ_(d,r(e))=e-r+R_(e-1-r,d-1),R_(e-1-r,d-1)=「(e-1-r)/(d-1)」.我们建立与φ~■有关的采样定理.显然,φ的多小波子空间采样定理的适用范围得到了拓展.给出φ~■的多小波子空间采样级数的截断误差估计.     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工;模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

完全多部图的无符号Laplacian特征多项式(英文)

For a simple graph G,let matrix Q（G）=D（G） + A（G） be it’s signless Laplacian matrix and Q G （λ）=det（λI Q） it’s signless Laplacian characteristic polynomial,where D（G） denotes the diagonal matrix of vertex degrees of G,A（G） denotes its adjacency matrix of G.If all eigenvalues of Q G （λ） are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K（n₁,n₂,···,n_t）.We prove that the complete t-partite graphs K（n,n,···,n）t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K（m,···,m）s（n,···,n）t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K（m,···,m,）s1（n,···,n,）s2（l,···,l）s3.     

一类带p-Laplace型算子的高阶两点边值问题的极值解

本文主要研究一类带p-Laplace型算子的n(≥3)阶非线性常微分方程-[φ(u(n-1)(t))]'=f(t,u(t)), a.e.t∈[a,b]满足两点边界条件u(i)(a)=Ai, i＝0,1,…,n-3, u(n-1)(a)=A, u(n-1)(b)=B的边值问题极值解的存在性,这里φ:R→R=(-∞,+∞)是递增的同胚,f:[a,b]×R→R是L 1-Carathéodory函数,A,B,Ai,Bi∈R,i=0,1,…,n-3.主要利用基于反极大值原理的单调迭代方法,得到了上述边值问题极值解的存在性结果.     

一种场站设置问题中的几个结论

本文研究如下一种场站设置问题:设S是欧空间E~m中由有限个点A_1,A_2,…,A_n组成的集合.d(A_i,A_j)表示点A_i和A_j之间的距离.令σ(S)=Σ_(1≤i相似文献   

非线性方程组的Newton流线法

为求解非线性方程组F(x)=0, 研究了Newton流方程x_t=V(x)=-(DF(x))^-1F(x),x(0)=x⁰,及数值Newton流x^j+1=x^j+hV(x^j),h∈(0,1].导出了减幅指标g_j(h)=||F(x^j+1)||/||F(x^j)||=1-h+h²d_jh<1和m重根x^*附近的表示g_j(h)=(1-h/m)^m+h²O(||x^j-x^*||).最后基于4个可计算量g_j,d_j,K_j,q_j,提出了新的Newton流线法,如果投入大量的随机初始点, 能找到所有实根、重根和复根.     

非线性分数次边值问题改进的ADM解法(英文)

We use the modified Adomian decomposition method（ADM） for solving the nonlinear fractional boundary value problem {D（^α₀） + u（x） = f（x, u（x））, 0 < x < 1, 3 < α≤ 4 u（0） = α₀ , u’’ （0） = α₂ u（1） = β₀ , u’’（1） = β₂} （1） where D（₀^α）+u is Caputo fractional derivative and α₀,α₂,β₀,β₂ is not zero at all,and f:[0,1]×R→ R is continuous.The calculated numerical results show reliability and efficiency of the algorithm given.The numerical procedure is tested on linear and nonlinear problems.     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

多扇图的Pebbling数和Graham猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图F_n1,n2,…,nm是指阶为n₁+n₂+…+n_m+1的联图P₁∨(P_n1∪P_n2∪…∪P_nm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图F_n1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。