流水车间排列排序专家系统—PFSCH

摘要

流水车间排列排序问题可以简单表示为:n/m/p/Fmax,其含义为,n个不同的工件（J1,J2,…,Jn）要经m台机器（M1,M2…,Mm）加工;加工路线为M1—M2—…—Mm,n个工件在每台机器上的加工顺序都一样;p表示排列排序;目标函数是使最长流程时间Fmax（加工周期）最短.n个工件有n!种不同的加工顺序.现已证明,n/m/p/Fmax（m≥3）问题属于NP难题,找不到多项式时间算法.因此,人们提出了若干个启发式算法,其中最著名的是Campbell等人提出的启发式算法（简称为CDS法）.Dannenbring曾比较过11种不同的启发式算法的效果,指出“快速接近扩展搜索法（RAES法）”的结果最好.但是,RAES法实质上还是一种列举法,它不从问题本身的结构出发,具有很大的盲目性.