可拆分平行机排序问题研究

平行机排序问题是把n个产品安排到m台机器上加工，使其总费用最小．通常的平行机排序问题都假设（C1）：任何产品不能在不同机器上同时加工．但是，如果把产品的加工时间看成一个产品量的需求，就可以假设（C2）：允许同一产品拆分在不同机器上同时加工．本文首先回顾了C1假设下平行机排序问题已有的结果，然后基于假设C2，讨论了各种费用目标下问题的算法及其复杂性．在没有生产准备时间的情况下，给出了一些问题的多项式算法和线性规划方法．在有独立生产准备时间的情况下，给出了P／split／Cmax问题的启发式算法及其算法分析．     

机器排序的几个问题及结果

本文以生产计划中的能力受限单机排序问题、加工过程中产品可以拆分到不同机器上加工的平行机排序问题和基于ＪＩＴ生产哲理的平行机排序问题为主，按能力受限单机排序问题、正则目标函数平行机排序问题变形和非正则目标函数平行机排序问题，介绍它们的模型和最近的几个理论研究结果．同时提出有待研究的问题．     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时,该问题等价于图上的最大匹配问题,因此存在组合强多项式时间算法;但量当机器台数为3或者多于3时,该问题是强NP困难的．     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带有装卸服务器的两台平行机调度问题的LS和LPT算法

研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

两台平行机完工时间平方和最小的排序问题

在两个竞争公司进行零和博弈过程中, 最大化两个公司收益的乘积, 在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和. 给出了该问题修改的延缓开始\ LPT\ 算法: 首先, 将工件按照加工时间$\p_j\ $的\ LPT\ 序重新标记; 若加工时间最长的前\ $2m$\ 个工件的总加工时间\ $P(2m)< (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m+1$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+2$\ 个工件安排加工; 否则,\ $P(2m)\geq (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+1$\ 个工件安排加工. 证明了该算法的最差性能比不超过\ $1+ ( \frac{1}{2m+2} )^2$, 且界是紧的.     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n~(k+2))/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n~(k-1))/((k-1)!).     

Improving an Upper Bound on the Stability Number of a Graph

In previous works an upper bound on the stability number of a graph based on quadratic programming was introduced and several of its properties were given. The graphs for which this bound is attained has been known as graphs with convex-QP stability number. This paper proposes a new upper bound on the stability number whose determination is also done by quadratic programming. It is proved that the new bound improves the above mentioned bound and several computational tests asserting its interest for large graphs are presented. In addition a necessary and sufficient condition for a graph to attain the new bound is proved. As a consequence a graph with convex-QP stability number also attains the new bound. On the other hand it is shown the existence of graphs attaining the new bound that do not belong to the class of graphs with convex-QP stability number. This allows to assert that the class of graphs with convex-QP stability number is strictly included in the class of graphs that attain the introduced bound. Some conclusions and lines for future work finalize the paper.     

A new decomposition approach for the single machine total tardiness scheduling problem

This paper deals with the single machine total tardiness problem. From Emmons’ basic dominance conditions a new partition theorem is derived which generalises Lawler’s decomposition rule and leads to a new double decomposition procedure. This procedure is embedded into a branch and bound method which applies a new lower bound based on due dates reassignment. The branch and bound method is tested on problems with size up to 150 jobs.     

第四类Caftan-Hartogs域上Bergman度量与Einstein-Kahler度量等价

In this paper,we discuss the invariaut complete metric on the Cartan-Hartogs domain of the fourth type.Firstly,we find a new invariant complete metric,and prove the equivalence between Bergman metric and the new metric;Secondly,the Ricci curvature of the new metric has the super bound and lower bound;Thirdly,we prove that the holomorphic sectional curvature of the new metric has the negative supper bound;Finally,we obtain the equivalence between Bergman metric and Einstein-Kahler metric on the Cartan-Hartogs domain of the fourth type.     

NEW LOWER BOUNDS FOR LEE DISCREPANCY ON TWO AND THREE MIXED LEVELS FACTORIALS

The objective of this paper is to study the issue of uniformity on asymmetrical designs with two and three mixed levels in terms of Lee discrepancy.Based on the known formulation,we present a new lower bound of Lee discrepancy of fractional factorial designs with two and three mixed levels.Our new lower bound is sharper and more valid than other existing lower bounds in literature,which is a useful complement to the lower bound theory of discrepancies.     

On computation of the steady-state probability distribution of probabilistic Boolean networks with gene perturbation

Given a Probabilistic Boolean Network (PBN), an important problem is to study its steady-state probability distribution for network analysis. In this paper, we present a new perturbation bound of the steady-state probability distribution of PBNs with gene perturbation. The main contribution of our results is that this new bound is established without additional condition required by the existing method. The other contribution of this paper is to propose a fast algorithm based on the special structure of a transition probability matrix of PBNs with gene perturbation to compute its steady-state probability distribution. Experimental results are given to demonstrate the effectiveness of the new bound, and the efficiency of the proposed method.     

On quasigroups with few associative triples

There are numerous application of quasigroups in cryptology. It turns out that quasigroups with the relatively small number of associative triples can be utilized in designs of hash functions. In this paper we provide both a new lower bound and a new upper bound on the minimum number of associative triples over quasigroups of a given order.     

The characterization of binary constant weight codes meeting the bound of Fu and Shen

Fu and Shen gave an upper bound on binary constant weight codes. In this paper, we present a new proof for the bound of Fu and Shen and characterize binary constant weight codes meeting this bound. It is shown that binary constant weight codes meet the bound of Fu and Shen if and only if they are generated from certain symmetric designs and quasi-symmetric designs in combinatorial design theory. In particular, it turns out that the existence of binary codes with even length meeting the Grey–Rankin bound is equivalent to the existence of certain binary constant weight codes meeting the bound of Fu and Shen. Furthermore, some examples are listed to illustrate these results. Finally, we obtain a new upper bound on binary constant weight codes which improves on the bound of Fu and Shen in certain case. This research is supported in part by the DSTA research grant R-394-000-025-422 and the National Natural Science Foundation of China under the Grant 60402031, and the NSFC-GDSF joint fund under the Grant U0675001     

An Upper Bound to the Chromatic Number of a Uniform Hypergraph without Cycles of Length Two or Three

In this paper, we establish a new upper bound to the chromatic number of a uniform hypergraph having no cycles of length two or three. The proof is based on a recent lower bound to the chromatic polynomial.     

A heuristic for the stability number of a graph based on convex quadratic programming and tabu search

Recently, a characterization of the Lovász theta number based on convex quadratic programming was established. As a consequence of this formulation, we introduce a new upper bound on the stability number of a graph that slightly improves the theta number. Like this number, the new bound can be characterized as the minimum of a function whose values are the optimum values of convex quadratic programs. This paper is oriented mainly to the following question: how can the new bound be used to approximate the maximum stable set for large graphs? With this in mind we present a two-phase heuristic for the stability problem that begins by computing suboptimal solutions using the new bound definition. In the second phase a multi-start tabu search heuristic is implemented. The results of applying this heuristic to some DIMACS benchmark graphs are reported.     

Efficient embeddings of grids into grids

In this paper we explore one-to-one embeddings of two-dimensional grids into their ideal two-dimensional grids. The presented results are optimal or considerably close to the optimum. For embedding grids into grids of smaller aspect ratio, we prove a new lower bound on the dilation matching a known upper bound. The edge-congestion provided by our matrix-based construction differs from the here presented lower bound by at most one. For embedding grids into grids of larger aspect ratio, we establish five as an upper bound on the dilation and four as an upper bound on the edge-congestion, which are improvements over previous results.