调度问题微结构及柔性优化方法

多处理器、多模式等调度问题的出现，标志着调度问题正呈现出更加复杂多样、更强调柔性的发展趋势.本文采用嵌套的微结构方法，对现有调度问题进行统一表述，并且能够表述一些传统方法无法表述的复杂问题.针对主从微结构，本文用总柔性度（GFD）作为调度问题柔性的衡量指标，并按照GFD的分类给出了求解调度问题的线性规划方法.定量实验不仅表明适当的柔性能有效优化调度问题的最优解，而且针对车间设备群规模合理性给出了统计结论.     

有优先顺序约束的单件车间调度问题的一种启发式算法

本文研究单件车间调度优化问题，针对工件之间存在的加工顺序关系，给出了逆推算法对各工件的交货期进行预处理，将问题转化为一般单件车间调度问题，在此基础上运用合适的调度规则，构造了具有一定优度的启发式算法。     

决策规则在仿真调度中的应用

讨论了用决策规则解决ＦＭＳ车间调度问题的方法与规则库的具体实现，说明基于规则的仿真调度是产生可行调度方案的一条有效途径。分析了规则与性能指标的关系，对如何合理地选用规则给出了建议。     

基于多Agent协商机制的PCB装配调度系统

文中针对PCB装配调度问题设计了一个基于多Agent调度系统模型，给出了模型的体系结构与功能描述，系统将任务和优先权机制与基于合同网协议和KQML消息的竞标机制两者相结合，实现PCB装配的优化调度，详细介绍了多多Agent之间的KQML消息通信机制，给出一个应用实例。     

基于MAS技术的生产调度方法的研究

生产调度是一类复杂的系统性问题。本文探讨了多代理系统(multi—agent system，MAS)技术在生产调度研究领域的应用。在介绍传统调度方法和多代理调度系统(multi—agent scheduling system，MASS)的基础上，提出了基于多代理机制的调度实现方案，给出了MASS的体系结构。文末对以后的研究做出了一些展望。     

遗传算法在Job-Shop问题上的应用

在车间作业调度数学表达模型的基础上,应用遗传算法对车间作业调度问题进行研究,为了满足遗传算法对解的多样性的要求,提出了一个调度问题的编码方法,并定义了解锁规则且给出了解码过程,最后给出实例说明设计的有效性。     

基于人工免疫的网格资源任务调度算法

目前，网格计算作为一种新的计算范式正在兴起。资源调度是其中的一个重要研完领域。该文以AIS的克隆选择算法为基础，给出了基于人工免疫系统的网格资源调度算法。首先，对网格资源任务调度问题给出了形式化描述，随后用结构化的语言对算法进行了说明，最后通过仿真实验对算法的有效性以及算法参数对性能的影响进行了验证。     

网格计算中时间和费用限制下的任务调度算法

在网格计算中，一个好的管理系统应有出色的算法来调度用户提交的任务。前人基于不同目的已设计了各种调度算法，但通常不易施行：重点考虑工作完成时间和所耗费用，给出确定的模型以调度独立的任务。通过恰当的建模，所求解的问题将演变成0—1规划问题，而这种问题清晰明了，且有现成算法求解，从而使得时间和费用最小化。给出一个例子验证了该算法的有效性。     

用神经网络求解机器人动态调度中的近似指派问题

本文利用HOPFIELD神经网络，对机器人动态调度中的近似指派问题提出了合理的神经网络表示方法，给出了网络的能量函数表示法及神经元状态方程，从而得出了机器人动态调度中近似指派问题的快速求解策略，满足了动态调度的实时性要求。本文从理论上论证了所提算法的收敛性。软件仿真结果表明，本文提出的近似指派问题网络求解方法是有效的，计算结果是满意的。     

基于多级队列算法的ITS资源调度策略

资源调度是公交智能交通系统(ITS)建设中亟待解决的一类重要问题。文章抽象了公交资源调度问题的一般特征和要求，以多级队列算法为基础并将其加以改进，给出了一种适用于ITS的资源调度策略，并成功地应用于北京市公交抢修调度系统中。还对该策略应用中的具体的资源子集划分、多级队列建立、优先级动态调整机制及自动分配等关键技术进行了阐述。     

An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach

In this paper we consider the no-wait job shop problem with a makespan objective. This problem has usually been addressed by its decomposition into a sequencing and a timetabling problem. Here, first we focus on the timetabling problem and take advantage of the symmetry of the problem in order to suggest a new timetabling procedure. Secondly, we suggest embedding this timetabling into a recent metaheuristic named complete local search with memory.     

Greedy algorithms for a class of knapsack problems with binary weights

In this article we identify a class of two-dimensional knapsack problems with binary weights and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. Starting from the knapsack problem with two equality constraints we show that this problem can be solved efficiently by using an appropriate partitioning of the items with respect to their binary weights. Based on the results for this problem we derive an algorithm for the three-criteria unconstrained combinatorial optimization problem with two binary objectives that explores the connectedness of the set of efficient knapsacks with respect to a combinatorial definition of adjacency. Furthermore, we prove that our approach is asymptotically optimal and provide extensive computational experiments that shows that we can solve the three-criteria problem with up to one million items in less than half an hour. Finally, we derive an efficient algorithm for the two-dimensional knapsack problems with binary constraints that only takes into account the results we obtained for the unconstrained three-criteria problem with binary weights.     

确保安全QoS的WFS路由算法

中的最关键的功能组件之一就是基于QoS的路由，从本质上看QoS路由实际就是端点到端点的带结点条件限制和边条件限制的最短路径问题，在文[1]中指出这种问题是NP完全的。本文研究对丢失敏感对延时不敏感的QoS路由模型——确保安全QoS的路由算法，并提出了一种新启发式算法；首先，我们讨论QoS一般模型，然后利用图论中的WFS算法求解QoS路由，该算法的时间复杂度为O(nlog(n)+n×d×K_0)，优于化前在该问题上的求解算法。     

Fractional location problems

In this paper we analyze some variants of the classical uncapacitated facility location problem with a ratio as an objective function. Using basic concepts and results of fractional programming, we identify a class of one-level fractional location problems which can be solved in polynomial time in terms of the size of the problem. We also consider the fractional two-echelon location problem, which is a special case of the general two-level fractional location problem. For this two-level fractional location problem we identify cases for which its solution involves decomposing the problem into several one-level fractional location problems.     

A hybrid constraint programming approach to a wood procurement problem with bucking decisions

In this article, we present a wood procurement problem that arises in Eastern Canada. We solve a multi-period wood supply planning problem, while taking into account bucking decisions. Furthermore, we present a new form of flexibility which allows the harvesting capacity to change from one time period to another. We study the impact of such flexibility upon the harvesting cost. We assess the performance of the problem by comparing it with a variant where the harvesting capacity is fixed during sites’ harvesting. To address this problem, we develop a hybrid approach based on both constraint and mathematical programming. In the first phase, we propose a constraint programming model dealing with forest sites harvesting and bucking problems. The result of this model is used as part of an initial solution for the whole problem formulated as a mixed integer model. We test the two versions of the problem on a set of different demand instances and we compare their results.     

Explaining interdependent action delays in multiagent plans execution

In this paper we address the problem of diagnosing the execution of Multiagent Plans with interdependent action delays. To this end, we map our problem to the Model-Based Diagnosis setting, and solve it by devising a novel modeling and reasoning method to infer preferred diagnoses based on partial observation of the start and end times of plan actions. Interestingly, we show that the kind of problem we address can be seen as an extension to the well known disjunctive temporal problem with preferences, augmented with a (qualitative) Bayesian network that models dependencies among action delays. An extensive set of tests performed with a prototype implementation on two different problem domains proves the feasibility of the proposed methodology.     

A method for interval 0–1 nonlinear programming problem using a genetic algorithm

In this paper, we formulate an optimal design problem of system reliability as a nonlinear integer programming problem with interval coefficients, transform it into a bicriteria 0–1 nonlinear programming problem without interval coefficients, and solve it directly using GA with holding nonlinear objective functions. Also, we demonstrate the efficiency of this method with a numerical example.     

A localized protein-folding problem

This paper is concerned with a localized protein-folding problem. In computational biology, the prediction of a three-dimensional protein from its amino acid sequence is a major outstanding problem. In this paper, we will first present this problem as a computational geometry problem. Then we will describe a pattern recognition method for the localized prediction problem. Since protein-folding plays a central role in understanding the structure and function of life—building molecular computers, designing drugs and biotech products—we will provide an intelligent system approach to these practical domains. © 2001 John Wiley & Sons, Inc.     

The multi-facility median problem with Pos/Neg weights on general graphs

In this paper we discuss the multi-facility location problem on networks with positive and negative weights. As the finite dominating set for the single facility problem does not carry over to the multi-facility problem, we derive a new finite dominating set. To solve the problem, we present a straight-forward algorithm. Moreover, for the problem with just two new facilities, we show how to obtain a more efficient solution procedure by using planar arrangements. We present computational results to underline the efficiency of the improved algorithm and to test some approximations which are based on a reduced candidate set.     

On the wireless local area network design problem with performance guarantees

In this paper, we propose a model for the wireless local area network (WLAN) design problem with performance guarantees. This problem consists of selecting the location of the access points (APs) as well as the power and the channel of each AP. The performance guarantees we refer to are coverage and minimum bandwidth guarantees. Since this problem is -hard, we propose a tabu search algorithm to find solutions for real-size instances of the problem. Finally, numerical results are presented. The results show that good solutions can be found with the proposed algorithm in a reasonable amount of time.