论文部分内容阅读
在竞争激烈的全球环境背景下,生产调度问题越来越受专家关注,其本质是目标优化的过程。混合流水车间问题(Hybrid Flowshop Problem,HFP)是一种较为常见的生产调度问题,基于石油化工背景产生,广泛存在于化工、钢铁,制药等制造车间。同时,HFP已被证实是NP-hard问题,使用传统的方法很难得到满意的方案,特别是更为复杂的HFP,可能根本得不到解。故而,对HFP的研究,在现实生产和学术理论方面均具有一定的意义。从中间存储策略来看,HFP的研究可分为无限中间存储、有限中间存储(即有限缓冲)、无中间缓冲(即含阻塞)和零等待四类,传统的HFP一般假定相邻阶段间的缓冲容量是无限的,然而,由于生产工艺和设备的限制,中间缓冲能力通常会受到一定限制。因此,本文主要针对中间缓冲能力受限的情况展开对带无关并行机的HFP的研究。具体包括如下:(1)针对带有限缓冲和无关并行机的HFP,提出一种基于遗传算法和禁忌搜索的混合启发式算法(Hybrid Heuristic based on Genetic Algorithm and Tabu Search,HH-GA&TS)解决最小化完工时间问题,在该算法中,设计了基于多阶段并行加工的二维矩阵编码方案,并引入参数自适应策略、三种邻域规则,禁忌搜索。最后仿真实验证明,相较于结合NEH启发式的改进GA(NEHIGA)、GA和TS,所提算法求解效果更好。(2)针对零等待和无关并行机的HFP,提出一种混合遗传模拟退火(Hybrid Genetic Simulated Annealing,HGSA)算法解决最小化总流程时间问题,HGSA算法采用改进的NEH规则来产生初始种群,为满足无等待约束,设计了一种差值平移法解码方案,并引入多种领域结构和SA来进一步提升解得多样性,最后通过仿真实验测试了不同规模问题实例,对比了HGSA与在文献中提出的几种启发式算法,结果表明所提算法求解质量优于其他几种算法。(3)在以往带阻塞和无关并行机的HFP研究中,大部分探讨的是完工时间问题,并且很少考虑生产与运输的协调问题,然而在实际生产中,运输需要独立于生产来考虑。故本文针对带阻塞和无关并行机的HFP,考虑了运输时间和释放时间,提出一种嵌入局部搜索有效的遗传算法(Effective GA with Local Search,EGA&LS)解决最小化总加权完工时间目标,仿真实验对比了EGA&LS、遗传参数自适应策略改进GA(IAGA)、NEH-IGA、传统GA四种算法,结果表明所提算法求解质量更佳且适合解决大规模问题。