Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs

Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is O(n²\frac(1+logm)m)O(n^{2}\frac{(1+\log m)}{m}) . The best previous algorithm for this problem has complexity O(mn ³) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

基于遗传算法的岩体参数辨识研究

目前,对于岩体流固耦合分析研究已经很多,而耦合分析常常受困于计算参数的取值,因此对两场耦合模型中的计算参数反演分析是非常必要的.根据实测的水头、位移资料,利用遗传算法,建立了等效连续岩体渗流场与应力场耦合计算参数辨识模型.并对某算例在库水位下降情况下,以渗流场与应力场耦合正分析计算结果作为"实测值",进行两场耦合参数辨识分析.从参数辨识的结果来看,验证了所提出的思路、方法以及程序的正确性和可行性.两场耦合计算参数进行反演分.析,对于两场耦合模型的建立和计算结果的可靠性是非常有意义的.     

遗传-蚁群混合算法在高温超导匀场磁体优化设计中的应用

遗传算法具有很强的自适应性、鲁棒性和全局搜索能力,但其局部搜索能力相对较弱,计算后期易出现进化缓慢、过早收敛等问题,蚁群算法是近几年迅速发展起来的一种新的全局优化算法,具有正反馈机制,但是计算初期由于信息素差别小,初始收敛速度较慢.本文将这两种优化方法结合起来,充分发挥各自的优势,形成了遗传-蚁群混合算法,并选用测试函数对算法的优化性能作了对比计算,最后以高温超导匀场磁体为实际应用目标,以绕制磁体所用超导带长度为目标函数对磁体结构进行优化设计,优化方案比原始方案节省7.32%的超导带材用量.     

非线性Galerkin算法的收敛性和复杂性

本文给出了数值求解非线性发展方程的全离散非线性Ｇａｌｅｒｋｉｎ算法,即将空间离散时的谱非线性Ｇａｌｅｒｋｉｎ算法和时间离散的Ｅｕｌｅｒ差分格式相结合,得到了显式和隐式两种全离散数值格式,相应地也考虑了显式和隐式的Ｇａｌｅｒｋｉｎ全离散格式,并分别分析了上述四种全离散格式的收敛性和复杂性,经过比较得出结论;在某些约束条件下,非线性Ｇａｌｅｒｋｉｎ算法和Ｇａｌｅｒｋｉｎ算法具有相同阶的收敛速度,然而前     

一个关于二次规划问题的分段线性同伦算法

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。     

Reliability analysis and optimization of weighted voting systems with continuous states input

Weighted voting systems are widely used in many practical fields such as target detection, human organization, pattern recognition, etc. In this paper, a new model for weighted voting systems with continuous state inputs is formulated. We derive the analytical expression for the reliability of the entire system under certain distribution assumptions. A more general Monte Carlo algorithm is also given to numerically analyze the model and evaluate the reliability. This paper further proposes a reliability optimization problem of weighted voting systems under cost constraints. A genetic algorithm is introduced and applied as the optimization technique for the model formulated. A numerical example is then presented to illustrate the ideas.     

A constructive approach to the problem of program correctness

As an alternative to methods by which the correctness of given programs can be established a posteriori, this paper proposes to control the process of program generation such as to produce a priori correct programs. An example is treated to show the form that such a control might then take. This example comes from the field of parallel programming; the way in which it is treated is representative of the way in which a whole multiprogramming system has actually been constructed.     

On Steiner Versions of (bi)Connectivity in Network Problems

The notions of connectivity and biconnectivity can be generalized in the Steiner sense, i.e., they are restricted to a given subset of the vertices of a graph. We illustrate this generalization on two problems. The first problem is the bottleneck biconnected subgraph problem, the second one is the so-called bipartition problem. The adapted algorithms to solve the Steiner versions of these problems exploit depth-first search to attain respectively a running time of O(|E|+|V|log|V|) and O(|E|+|V|) with E denoting the set of edges and V the set of vertices of the given graph.Final version received: October 15, 2003