基于粒子群优化的开放式车间调度

开放式车间调度(OSP)是重要的调度问题,它在制造领域中的应用非常广泛。优化调度算法是调度理论的重要研究内容。基于人工智能的元启发式算法是解决该问题的常用方法。分析了一种新的元启发式算法——粒子群优化(PSO)在信息共享机制上的缺陷,提出新的基于群体智能的信息共享机制。在该信息共享机制的基础上, 设计新的基于PSO的元启发式调度算法——PSO-OSP。该算法利用问题的邻域知识指导局部搜索,可克服元启发式算法随机性引起的盲目搜索。该算法应用于开放式车间调度问题的标准测试实例。仿真结果显示,PSO-OSP算法在加快收敛速度的同时提高了开放式车间调度解的质量。

PSO BASED SCHEDULING ALGORITHM FOR OPEN SHOP SCHEDULING PROBLEM

Open shop scheduling is an important scheduling problem and has wide engineering applications in manufacturing. Optimization algorithms are important research content in scheduling theory. Artificial intelligence based meta-heuristic algorithms are effective methods for this problem. A new meta-heuristic based on particle swarm optimization (PSO) is proposed to obtain optimized open shop schedule. First, the limitation of information sharing mechanism in PSO model is discussed, and then new information sharing mechanism based on swarm intelligence is put forward. Based on the new information sharing mechanism, a new PSO based on scheduling algorithm-PSO-OSP is proposed. The proposed algorithm utilizes neighborhood knowledge to direct its local search procedure which can overcome the blindness or randomness introduced by meta-heuristics. Finally, OSP benchmarks are used to test its efficiency. Simulation results show that the new proposed algorithm can improve the convergence speed and obtain optimized open shop schedules.