无等待流水车间调度问题的优化  

Heuristics for the No-Wait Flow Shop Problem with Makespan Criterion

作　　者：潘全科[1] 赵保华[1] 屈玉贵[1] 

机构地区：[1]中国科学技术大学计算机科学技术系

出　　处：《计算机学报》2008年第7期1147-1154,共8页Chinese Journal of Computers

基　　金：国家自然科学基金重大项目(90104010);博士后科学基金(20070410791)资助

摘　　要：文中研究了以生产周期为目标的无等待流水车间调度问题.首先,结合问题特征,提出了一种复杂度为O(n)的快速生产周期算法.其次,研究了两种插入邻域结构:基本插入邻域和多重插入邻域,并提出了快速基本插入邻域算法和最大多重插入移动算法.在此基础上,将离散粒子群算法与上述两种邻域搜索算法相结合,得到了离散粒子群优化调度算法.第三,根据问题生产周期的不规则性,给出了一种通过延长工序加工时间进一步改进调度方案的方法.最后,仿真实验表明了所得算法的可行性和有效性.This paper aims at finding a permutation of jobs for the no-wait flow shop （NWFS） scheduling problem with the objective of minimizing makespan. First, after investigating the property of the solution of NWFS, a speed-up method with the computational complexity O（n） is developed for calculating the makespan of a permutation. Second, a discrete particle swarm optimization algorithm （DPSO） is presented for solving this problem. Two kinds of neighborhood, insert neighborhood and multi-insert neighborhood consisting of multi-insert, which performs several inserts simultaneously in a single iteration of algorithm, are fused in the algorithm to balance the exploration and exploitation. A short-cut for insert neighborhood is also proposed. Third, an anomaly in NWFS is studied where increasing processing time of some operations may decrease makespan. Several theorems about this anomaly are reported, and an improvement procedure by slowing down some machines is designed for a permutation. Last, computational tests based on the well known benchmark suites in the literature show that the presented DPSO is effective and efficient on finding optimum or near-optimal solutions, and that slowing down some machines may result in significant reduction of the makespan yielded by DPSO.

关 键 词：无等待流水车间 生产周期 粒子群算法 邻域搜索算法 不规则性 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]