具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.     

平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

具有禁用区间的单机最小化加权完工时间和排序问题

研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.     

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

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

例谈二次函数区间最值的求解策略

如何求解二次函数在区间上的最值,是一个综合性较强的问题,影响二次函数在某区间上最值的是区间和对称轴的位置.本文就区间和对称轴动与静的变化进行分类,探索求最值的方法.     

插值多项式样条的存在唯一性

对给定的区间[a,b]上的分划。 △_N:a=x_0相似文献   

区间上的双正交小波的一种构造方法

小波分析是近十几年来十分热门的课题,早期的小波都是定义在无穷区间上的．而实际问题常常是有限区间,常用的方法是将有限区间上的数据向区间外延拓,但这样做容易产生边界误差,如何构造区间上的具有良好性质的小波,如光滑性、对称性等是非常有意义的．在文献［２］中,Cohen,Darbechies与Vial在总结了构造区间周期小波,折叠小波等方法的基础上,提出了一种新的构造方法,并把无穷区间上的Daubechies小波改造成区间上的Daubechies小波．但是,Daubechies小波没有对称性,光滑性也差．本文用类似的方法把无穷区间上的双正交小波改造…     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

连续区间上积分值的MQ拟插值算子

在某些插值问题中,插值点处的函数值是未知的,而连续区间上的积分值是已知的.如何利用连续区间上积分值信息来解决函数重构是一个重要的问题.首先,文章利用连续区间上积分值的线性组合得到结点处函数值和一阶导数值的的四阶逼近.然后,构造了一类基于连续区间上积分值的MQ拟插值算子,它称之为积分值型MQ拟插值算子.最后,给出了该MQ拟插值算子的整体误差,它具有相应的四阶逼近阶.数值实验表明,该方法是有效可行的.     

回归型支持向量机调节熵函数法的区间扩张研究

为减小由于二进制编码的舍入误差对该问题计算结果的影响,对求解回归支持向量机的一种调节熵方法进行了区间扩张,讨论了区间函数的相关定理与收敛性.对设计的区间算法做了收敛性证明,并给出了数值实验,验证了方法与算法的可行性和有效性.     

A method of constructing generalized difference sets

On the elements of the ring of residues modulo v (zτ v, 3τ v) we construct cyclic PBIB-designs with τ(v)-1 classes of connectedness, where τ(v) is the number of divisors of v. We prove the existence of cyclic BIB-designs with parameters b, v, r, k, and λ such that: 1) λ=k (and also λ=k/2 if k is even), k≥4, and (k-1) ¦ (p-1) for each prime divisor p of the number v; 2) λ=(k?l)/2, k odd, k≥3, k ¦ (p?1) for each prime divisor p of the number v.     

3-连通、高次和坚韧图周长的估计(Ⅰ)

设G是一个n阶3-连通图,周长为C(G),独立数为,若G是1-坚韧的,且,则G的每一个最长圈是控制圈且;又若G是5/3-坚韧的或,则G是Hamilton图。     

2-factors in random regular graphs

In this paper the expectation and variance of the number of 2-factors in random τ-regular graphs for any fixed tgr; ≥ 3 is analyzed and the asymptotic distribution of this variable is determined. © 1996 John Wiley & Sons, Inc.     

List edge and list total coloring of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)- total-choosable if Δ≥16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.     

The Periodic Initial Value Problem and Initial Value Problem for the Modified Boussinesq Approximation

The Boussinesq approximation, where the viscosity depends polynomially on the shear rate,finds more and more frequent use in geological practice. In this paper, we consider the periodic initial value problem and initial value problem for this modified Boussinesq approximation with the viscous part of the stress tensor τ^v = τ(e)- 2μΔe, where the nonlinear function τ(e) satisfies τ_{ij}(e)e_{ij} ≥ C|e|^p or τ_{ij}(e)e_{ij} ≥ C(|e|²+|e|^p). The existence, uniqueness and regularity of the weak solution is proved for p > \frac{2n}{n + 2}.     

On edge colorings of 1-toroidal graphs

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree Δ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree Δ for each Δ≤ 8.     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

Dirichlet型空间上的乘子

本文主要根据τ与μ的不同取值分三种情况刻划了Cn中单位球上Dirichlet 型空间上的点乘子空间M(Dτ,Dμ),并通过两个函数的构造表明:当τ≤n时,包含 关系M(Dτ)(?)Dτ和当τ>μ,τ>n-1时,包含关系M(Dτ)(?) M(Dμ)是严格的.     

循环分布图最大边数猜想的一个反例

令ｆ（ｎ）为恰有ｎ个顶点，任意两个循环长度都不相等的图的最多边数．１９７５年，Ｅｒｄｏｓ提出确定ｆ（ｎ）的问题（见［１］Ｐ２７４，Ｐｒｏｂｌｅｍ１１）．１９８６年，Ｙ．Ｓｈｉ证明了对任意自然数ｎ≥３，有ｆ（ｎ）≥ｎ＋８ｎ－２３＋１／２［］，且当３≤ｎ≤１７时，等号成立．进而猜想：对于任何自然数ｎ≥３，上述等式都成立．本文对该猜想给出一个反例．     

Packing k‐edge trees in graphs of restricted vertex degrees

Let denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τ_k (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that

• (a1) if G ∈ and s ≥ 4, then τ₂(G) ≥ v(G)/(s + 1),
• (a2) if G ∈ and G has no 5‐vertex components, then τ₂(G) ≥ v(G)4,
• (a3) if G ∈ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τ_k(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and
• (a4) the above bounds are attained for infinitely many connected graphs.

Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007