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

文中研究了以生产周期为目标的无等待流水车间调度问题.首先,结合问题特征,提出了一种复杂度为O(n)的快速生产周期算法.其次,研究了两种插入邻域结构:基本插入邻域和多重插入邻域,并提出了快速基本插入邻域算法和最大多重插入移动算法.在此基础上,将离散粒子群算法与上述两种邻域搜索算法相结合,得到了离散粒子群优化调度算法.第三,根据问题生产周期的不规则性,给出了一种通过延长工序加工时间进一步改进调度方案的方法.最后,仿真实验表明了所得算法的可行性和有效性.

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

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.