作业车间调度问题的多种群遗传算法

针对最小化完工时间的作业车间调度问题提出一个多种群遗传算法,该算法基于工艺约束定义个体的编码方式,基于工件操作构造遗传算子,保证了所有个体的可行性;多种群算法通过各个种群之间的相互竞争和良种共享,提高了资源的利用效率,有效地克服个体早熟,改善了算法的收敛性能.典型测试算例表明该算法是非常有效的.     

求解Job shop的一种快速混合算法

结合车间调度问题本身的特点,采用关键路径块邻域结构,混合禁忌搜索算法和粒子群优化算法,设计了一种快速混合调度算法.该算法对预选择的块邻域解的性能进行快速估计,对不可行解尽早舍去,大大减小了邻域解的搜索空间.仿真结果表明,该算法在求解平均时间和性能方面均具备明显优势.     

一种基于动态聚合方法的网格任务调度算法

网格中的资源都是动态的,传统的静态任务调度算法不能适应网格的动态特性.通过对资源在未来一段时间内的状态进行预测,可以提高调度算法的性能.文中提出了一种用动态聚合进行调度的算法.首先对处理器的负载进行取样,然后根据网格任务的执行时间,对处理器的取样值进行动态聚合,再利用AR（p）模型进行预测,最后利用预测到的值作为参数对网格任务进行调度,把网格任务分配给每个处理器,使得每个处理器完成子任务的时间都相同,从而使得整个任务的执行时间最短.实验表明,这种算法能很好地适应处理器负载高度变化的情况.     

基于改进的禁忌搜索算法求解车间作业调度问题

本文描述了一种解决车间作业调度最短完工时间问题的有效禁忌搜索算法,建立了该问题的数学模型,并提出了新的邻域构造方法。该算法利用改进的插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解。实验结果表明该算法是可行和有效的。     

求解模糊柔性作业车间调度的多目标进化算法

针对实际制造车间中工序加工时间具有不确定性,将加工时间采用模糊数表示,建立一种多目标模糊柔性作业车间调度模型,并提出了有效求解该模型的多目标进化算法.算法采用混合机器分配和工序排序策略的方法产生初始种群,并采用插入空隙法对染色体进行解码.定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子,并将所提支配关系和拥挤算子运用于快速非支配排序.接着,提出一种基于移动模糊关键工序的局部搜索策略.实验部分首先通过田口试验方法来研究关键参数对算法性能的影响;其次,将所提算法与三种不同的优化算法作对比.实验结果验证了所提算法的有效性.     

求解模糊作业车间调度问题的群体邻域搜索算法

 本文提出一种群体邻域搜索算法(Swarm-based Neighborhood Search,SNS),用于最小化模糊作业车间调度问题(Fuzzy Job Shop Scheduling Problem,FJSSP)的模糊makespan.该算法使用基于有序工序的编码,通过锦标赛选择和概率为1的动态调整互换操作更新群体.对调度结果的理论分析表明,模糊makespan能反映解的优劣.理论分析及大量实验证明,SNS具有较强的全局和局部优化能力,以及较快的收敛速度,在求解FJSSP方面具有较强的优势.     

带运输资源约束柔性作业车间调度问题的人工蜂群算法

本文针对一类柔性作业车间调度问题,综合考虑运输资源约束、工件间准备时间约束等条件,以最小化最大完工时间和能耗为目标,提出了一种改进的人工蜂群优化算法.为求解该问题,算法采用二维向量编码,即调度向量记录工件的调度顺序,机床分配向量记录工件分配可用机床情况,解码过程充分考虑运输资源、工件间准备时间等约束条件.在局部搜索策略...     

变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用

本文针对最小化完工时间的Job Shop调度问题提出一种变邻域结构Tabu搜索算法,该算法使用的邻域结构随算法的进程而改变,不仅邻域规模小,而且仍保持了可达性这一重要的属性.对不同规模的实例进行了数值计算,计算结果表明,该算法具有非常高的效率,且初始解对算法的影响很小.     

A Performance Study on a Multiagent E-Scheduling and Coordination Framework for Maintenance Networks

Many maintenance networks as well as supply networks and virtual enterprises consist of multiple organizations. A common problem arising in these different domains is multiorganization scheduling and coordination. The traditional centralized methods are not appropriate because of the existence of private information and decision-making authorities at different organizations. Although many distributed mechanisms have been presented for supply networks and virtual enterprises, they may not be effective for maintenance networks because of the difficulties of scheduling the tightly related maintenance operations and handling the massive uncertainties involved. These difficulties as well as the heterogeneity of the distributed environment make it challenging to develop an efficient framework for maintenance networks that can obtain a high-quality solution under different conditions, schedule in a timely manner, solve large-scale problems, and so on. In this paper, a price-based multiagent scheduling and coordination framework for maintenance networks is explored, and a systematic experimental study is carried out to evaluate the effects of different factors on its performance. The results show that the framework is able to overcome these difficulties and could be a step toward the next generation of e-scheduling for maintenance networks     

DIET — A Scalable, Robust and Adaptable Multi-Agent Platform for Information Management

The complexity of the global information infrastructure demands new approaches to managing distributed information. The Decentralised Information Ecosystem Technologies (DIET) project has produced a software platform based on a lightweight, scalable, multi-agent system that can be used to support a variety of information management applications that deal with some of this complexity. This paper describes the main components of the DIET software platform, and several examples of its application. It also considers the diversity of potential applications for this technology. This revised version was published online in July 2006 with corrections to the Cover Date.     

Research on Multi-objective Job Shop Scheduling with Dual Particle Swarm Algorithm Based on Greedy Strategy

In order to solve the multi-objective job shop scheduling problem effectively, this paper proposes a greedy strategy to establish the mathematical model of minimizing the maximum completion time, the average flow time and the machine idle time. The algorithm sets up a dual-population structure: leading-population and searching-population. Firstly, the algorithm calculates the fitness values of every particle for each population for the three objectives, and the optimize solutions will be incorporated in the individual optimal value set and the global optimal value set accordingly. Then the algorithm performs a crossover operation which includes two types: one is the leading-cross to lead the searching-population to convergence to the optimal solution quickly, and the other is intro-population crossover of each population in order to increase the diversity of individuals. The mutation operation of each population is followed to further enhance the diversity of individuals. And the simulated annealing algorithm is employed to avoid the algorithm falling into the local optimum effectively. The simulation experiments of various scale instances are carried out and compared with the simulation results of the other two popular algorithms to verify the effectiveness of the algorithm. The simulation results show that the proposed algorithm is superior to the other two algorithms in both the quality of the solution and the time-consuming.     

求解流水车间调度问题的混合粒子群算法

本文提出了一种混合的元启发式方法HDCPSO用于求解置换流水车间调度问题中的最小化完成时间.该算法将粒子群算法和迭代贪心算法(Iterative Greedy,IG)相结合,利用IG算法中的作业毁坏(Destruction)和构造(Construction)操作来对粒子进行变异,降低群体发生早熟的可能.引入了个体徘徊概...     

A Scheduling Framework for UWB & Cellular Networks

The max-min fair scheduling problem in wireless ad-hoc networks is a non-convex optimization problem. A general framework is presented for this optimization problem and analyzed to obtain a dual problem, which involves solving a series of optimization sub-problems. In the limit of infinite bandwidth ( ), the scheduling solution reduces to simultaneous transmission (spread spectrum) on all links (Negi and Rajeswaran, INFOCOM '04 (March 2004)). This motivates the analysis of the scheduling problem in the Ultra Wide Band (UWB) regime ( , but finite), a model for certain practical radios. A quadratic (in 1/W) lower bound to the single link capacity function is developed, which simplifies the dual sub-problem to a quadratic optimization (Negi and Rajeswaran, GLOBECOM '04, (Dec. 2004)). The solution to this sub-problem is then obtained under both total power and power spectral density constraints. This solution is utilized to iteratively construct the schedule (sub-band sizes) and power allocation, thus optimally solving the UWB max-min fair scheduling problem, to within any desired precision. Simulations on medium sized networks demonstrate the excellent performance of this scheme. A cellular architecture (not necessarily UWB) may also be considered in this framework. It is proved that Frequency Division Multiple Access is the optimal scheduling for a multi-band cellular architecture. This work was supported in part by the National Science Foundation under Career award 0347455. Arjunan Rajeswaran received his Masters degree in Electrical and Computer Engineering from Carnegie Mellon University in 2003. Since August 2003, he has been pursuing his doctoral research at Carnegie Mellon. His reserach interests lie in the area of wireless networks. His focus is in the application of information and communication theoretic tools towards wireless network design. Several IEEE publications reflect his curent research on Medium Access Control design and performance. Arjunan received the best student paper award at IEEE/ACM Broadnets 2004. Gyouhwan Kim received his B.S. and M.S. degree in Electronic Engineering from Sogang University in Korea, in 1994 and 1996, respectively. Since 1996, he has been working in the CDMA cellular system development team in Samsung Electronics. Currently, he is also working toward the Ph.D degree in the Department of Electrical and Computer Engineering at Carnegie Mellon University. His main research interests are in wireless networks and communication theory. Rohit Negi received the B.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, India in 1995. He received the M.S. and Ph.D. degrees from Stanford University, CA, USA, in 1996 and 2000 respectively, both in Electrical Engineering. He has received the President of India Gold medal in 1995. Since 2000, he has been with the Electrical and Computer Engineering department at Carnegie Mellon University, Pittsburgh, PA, USA, where he is an Assistant Professor. His research interests include signal processing, coding for communications systems, information theory, networking, cross-layer optimization and sensor networks.     

Robust Routing and Scheduling in Wireless Mesh Networks under Dynamic Traffic Conditions

Joint routing-and-scheduling has been considered in wireless mesh networks for its significant performance improvement. While existing work assumes it, accurate traffic information is usually not available due to traffic dynamics, as well as inaccuracy and delay in its measurement and dissemination. In addition, the joint routing and scheduling usually requires a centralized controller to calculate the optimal routing and scheduling and distribute such policies to all the nodes. Thus, even if the accurate traffic information is always available, the central controller has to compute the routing and scheduling repeatedly because the traffic demands change continuously. This leads to prohibitive computation and distribution overhead. Therefore, in this paper, we propose a joint routing-scheduling scheme that achieves robust performance under traffic information uncertainty. In particular, it achieves worst-case optimal performance under a range of traffic conditions. This unique feature validates the use of centralized routing and scheduling in wireless mesh networks. As long as the traffic variation is within the estimation range, the routing and scheduling do not need to be recomputed and redistributed. Through extensive simulations, we show that our proposed scheme meets the objective (i.e., optimizes the worst-case performance). Moreover, although it only guarantees the worst-case performance in theory, its average performance is also good. For example, our proposed scheme can perform better than a fixed optimal routing and scheduling scheme in more than 80 percent of 500 random traffic instances. Our scheme provides insights on the desired properties of multipath routing, namely, spatial reuse and load balancing.     

一种平衡的全局指令调度新框架研究

全局指令调度可以分为结构驱动和剖析驱动两类。我们展示了一种新算法,尝试结合以上两类方法各自的特点,同时避免它们的一些缺点。该算法可以在寄存器分配之前和之后调用,它已经在Open64编译器上实现,其结果在BWDSP100处理器上得到了评估。     

A Service-Curve Framework for Packet Scheduling With Switch Configuration Delays

In modern packet switches, technology limitations may introduce switch configuration delays that are non-negligible compared with the time required to transmit a single packet. In this paper, we propose a methodology for scheduling of packets, in the context of these technology limitations. If the total tolerable delay through a packet switch is at least on the order of the switch configuration delay, we show that a near 100% utilization of the communication links is possible, while providing strict quality of service guarantees. The main idea is to increase the quantum with which data is scheduled and switched to beyond that of a single packet. This also decreases the rate at which scheduling need to be made, and hence decreases the implementation complexity. The quality of service guarantees we consider are in terms of a service curve. Specifically, we present a framework for the provision of service curves while coping with non-negligible switch configuration delays.     

基于PSO的置换流水车间调度算法

置换流水车间调度问题(PFSP)是典型的具有工程背景的组合优化问题.对该问题的研究具有重要的理论意义与应用价值.本文针对PFSP问题提出了新的基于粒子群优化(PSO)的调度算法.论文分析了广义粒子群优化(GPSO)模型中信息流动拓扑结构的缺陷,提出新的基于种群的元启发式算法信息共享机制SISM.基于SISM信息共享机制的PSO调度算法利用PFSP问题的邻域知识指导个体的局部搜索.与历史文献中该问题的代表性算法比较,该算法可在调度质量与计算费用之间获得较好的平衡.仿真实例验证了该调度算法的有效性.     

无线传感器/执行器网络任务动态调度策略

针对任务在各执行器的协作问题,提出一种动态调度策略,根据执行器节点的剩余能量和工作状态,利用混合模拟退火的微粒群算法,在任务时效期内,统一安排各任务在执行器上的执行周期,最小化最大完成时间.仿真结果表明,算法具有良好的收敛性能,各执行器的任务完成响应时间和能耗均衡情况均得到改善.