基于两步法的NEH算法求解混合Flowshop的调度问题_文档.doc

基于两步法的NEH算法求解混合Flowshop的调度问题 李霄峰 曹杰 史金飞 （东南大学机械工程系, 南京210096） 摘要:　本文针对混合Flowshop系统的最小化Makespan调度问题，提出基于两步法的NEH启发式算法来对工件进行排序，采用FAM算法来分配设备，并给出其最优值的下界检验该算法。仿真结果表明,该算法优于目前最好的其它启发式算法，能够较好地解决混合Flowshop的调度问题。 关键词：混合Flowshop;下界值;makespan;调度 A New Approach of Two-Step NEH Heuristic for Hybrid Flowshop Scheduling Li Xiaofeng Cao Jie, Shi Jinfei （Department of mechanical engineering, Dongnan University, Nanjin 210096 ） Abstract: This paper proposes a scheduling approach of Two-Step NEH heuristic to minimize makespan problem in hybrid flowshop, in which improved NEH heuristic algorithm is used to get a sequence of jobs and the first available machine (FAM) rule is designed for allocating devices for jobs. A lower bound is proposed to check this algorithm’s deviation of the optimum makespan. The simulation result shows that the algorithm can get a good schedule for hybrid flowshop. Keywords: Hybrid Flowshop;lower bound;makespan;scheduling 引言 具有多机并行设备的Flowshop, 也称混合流水车间：Hybrid Flowshop(HFS)，柔性流水线：Flexible Flow Line(FFL)，是基本Flowshop的推广。如果所有级的设备数量为1，则是经典的Flowshop问题。 HFS调度近年来吸引了许多学者的注意，这是因为许多生产过程不是简单的平行设备、或者流水线作业，而是多级多机的HFS。在化工处理、石油工业、钢铁生产、柔性制造环境中具有许多此类的生产系统。Narasimhan和Mangiameli(1987)采用一些启发式算法解决两级有相同设备的混合流水线调度问题[1]。Gupta(1988)对两级的HFS调度问题进行了研究[2]。Hunsucker等(1989)对九种优先级规则进行仿真，评价各规则在flowtime和makespan指标方面的优劣[3]。Guinet等(1996)提出用经典的Flowshop的启发式算法如CDS、NEH、Tow求解HFS调度问题[4]。结果表明NEH效果最好，但是需要较多的时间。 1 HFS的调度问题 问题描述：Hybrid Flowshop是由多级的Flowshop构成，每级由个相同的设备组成。每台设备每次只能一次加工一个工件。在每级，有一个有限或无限容量的缓冲区。调度任务是一组待加工的工件，每个工件加工任务都是从第一级开始依次加工到最后一级，不允许抢先作业，加工任务不能分割。调度目的产生一个调度，使得工件的最大完工时间(makespan)最小。一个调度由加工工件的设备以及在设备上加工排序构成，即设备分配和任务排序。 对于传统的Flowshop问题，当设备的数量大于2时，求解最小makespan问题是强NP-hard问题，同样，并行机的问题也是NP-hard问题，因此，即使两级的HFS问题也是NP-完全问题，现有的分枝定界算法只能解决小规模的工件调度[4]。因此，能够在多项式时间内求近优解的启发式算法一直是实际应用中解决中大规模HFS问题的有效方法。 2启发式算法解决HFS调度问题 在过去的研究中，许多学者用Flowshop的著名的启发式算法如CDS、NEH、Tow等对HFS系统中工件进行排序。启发式求解HFS问题可分为两步：工件的排序和设备的分配。本文提出一种改进的NEH算法，用于工件的排序；采用最先空闲设备(FAM)分配规则。 2.1基于两步法的NEH算法（TNEH） NEH算法 Nawaz，Enscore和Ham启发式算法(1983)简称NEH启发