协同设计中的任务调度算法及实现

 在协同设计子任务间形成的任务前趋图的基础上,面向协同设计的实际需求,采用了两个任务调度算法：改进的AGA（Adaptive Genetic Algorithm, 自适应遗传算法）及GASA（Genetic Simulated Annealing Algorithm,遗传-模拟退火算法)。分别给出了算法的详细实现,分析并比较了算法与其它任务调度算法的效能。最后,针对较大规模的任务实例对这两个算法进行了横向比较,分析了它们的时间效率和适用场合。     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

Routing of Railway Carriages

In the context of organizing timetables for railway companies the following railway carriage routing problem occurs. Given a timetable containing rail links with departure and destination times/stations and the composition of the trains, find a routing of railway carriages such that the required carriages are always available when a train departs. The problem is formulated as an integer multi-commodity network flow problem with nonlinear objective function. We will present a local search approach for this NP-hard problem. The approach uses structural properties of the integer multi-commodity network flow formulation of the problem. Computational results for a real world instance are given.     

Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: the bottleneck lower bound

This paper studies minimizing the flow time of a cyclic schedule for repeated identical jobs, where one job is started/completed in each cycle, subject to the schedule achieving maximum throughput. We propose a branch and bound method for a single machine problem, and use this method to derive an improved lower bound for the multiple machine problem.     

The two-machine open shop problem: To fit or not to fit, that is the question

We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D₁ and D₂, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0,D₁] and [0,D₂], respectively.We formulate four simple conditions on D₁ and D₂, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D₁,D₂) for which there exists a feasible schedule.     

Minimizing breaks by maximizing cuts

We propose to solve the break minimization problem in sports scheduling by transforming it into a maximum cut problem in an undirected graph and applying a branch-and-cut algorithm. Our approach outperforms previous approaches with constraint programming and integer programming techniques.     

Block seriation problems: A unified approach. Reply to the problem of H. Garcia and J. M. Proth (Applied Stochastic Models and Data Analysis, 1, (1), 25–34 (1985))

In their article, entitled ‘Group technology in production management, the short horizon planning level’, H. Garcia and J. M. Proth have stated the following problem: starting from a (0, 1) binary matrix of size (N x M), how to divide into independent subsets the rows of this matrix simultaneously with a one-to-one corresponding partition of the columns, maximizing the presence of 1s in the intersecting blocks with a joint minimization of the presence of 0s outside of these blocks. The authors have proposed an efficient and very fast heuristic algorithm in comparison with the existing methods of a fast-growing literature on the subject. The only drawback of this algorithm is its dependence on the initial partition. In this paper, we try to improve this algorithm slightly, first in rewriting the objective function in a linear form and secondly in giving computational improvements related to this linear formulation.     

基于遗传算法的柔性作业车间柔性分批调度问题研究

针对柔性作业车间柔性分批调度问题的复杂性,采用遗传算法进行求解,在引入柔性分批方法后,并提出了染色体的两级编码方法,设计了2种交叉和变异操作方法,以防止操作中非法解的产生,提高求解效率.该算法不仅解决批量分批,而且也解决子批排序和选择加工路线的问题.对比整批调度和柔性分批调度的Makespan后,仿真结果表明,柔性分批调度可缩短生产周期,验证了采用新算法的可行性和有效性.     

基于智能优化算法的车间调度问题研究

车间的生产调度是一个非常复杂的问题,本文主要介绍车间调度问题模型以及蚁群算法、遗传算法、模拟退火算法等智能优化算法的研究情况,有效的生产调度方法和智能优化算法的应用,在很大程度上可以提高企业的效益.     

中庸算法——一种基于环型结构的并行调度算法

给出了分布式系统中的一种基于环结构的并行调度算法,以下称为中庸算法,并从理论上证明了该算法能够达到较好的负载平衡、最大限度的减少任务的迁移和通信、最大程度的计算本地化 并举例进行了说明