关键词:
离散工业过程
绿色调度
柔性作业车间调度
混合流水车间调度
帝国竞争算法
多目标优化
关键目标
摘要:
制造业是我国国民经济的重要支柱,也是能源与环境问题的主要来源。随着国民经济快速增长和环境的不断恶化,绿色制造作为现代化制造模式引起了学术界和工业界的广泛关注。离散工业是制造业的重要组成部分,亟需在提高经济指标的同时,降低对环境的影响。离散工业过程绿色调度通过资源分配、操作排序和运作模式的合理优化,实现节能、减排、降耗,提高经济效益,同时实现制造过程的绿色化,其研究具有更高的现实意义和应用价值。本文围绕离散工业过程绿色调度问题,主要包括绿色柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)和绿色混合流水车间调度问题(hybrid flow shop scheduling problem,HFSP),深入研究了目标重要性程度相同并且具有不同约束的绿色FJSP以及目标重要性程度不同且考虑关键目标的上述两类绿色调度问题;结合反馈和帝国分层等新型优化机理,设计多种新型帝国竞争算法(imperialist competitive algorithm,ICA)以获得问题高质量的优化结果。本文主要研究工作如下:(1)针对具有总能耗约束的绿色FJSP,提出了一种基于ICA和变邻域搜索(variable neighborhood search,VNS)的两阶段元启发式算法,在总能耗不超过给定阈值的条件下最小化最大完成时间(makespan)和总延迟时间。第一阶段将原问题转化为具有总能耗等目标的三目标绿色FJSP,设计新型ICA对问题求解并根据ICA优化结果确定总能耗阈值;第二阶段给出了新旧解的比较原则和非劣解集更新策略,设计了高效的VNS对原问题求解。计算结果表明两阶段元启发式算法具有较强的优势。(2)研究了考虑运输的绿色FJSP,提出了反馈型ICA以同时最小化makespan、总延迟时间和总能耗。该算法运用反馈实现同化和革命参数以及邻域结构的自适应选择;不是所有殖民地都进行同化,参与同化的殖民地可以执行多次同化并有多个学习对象;设计了新型帝国竞争策略以增强帝国间信息交流并强化种群中部分最差解的搜索。大量计算实验验证了反馈型ICA在求解所研究问题方面的优越性。(3)针对高维多目标绿色FJSP,提出了一种改进型ICA以同时最小化总能耗、最大延迟时间、makespan和最大机器负荷,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化操作,并应用新型革命策略和帝国竞争方法。最后通过大量实验验证了新策略对改进型ICA性能的显著影响,以及新型ICA在求解高维多目标绿色FJSP方面较强的优势。(4)针对考虑关键目标的绿色FJSP,设计了一种差异化ICA在充分优化关键目标makespan和总延迟时间的同时持续改进非关键目标总能耗。该算法采用新型同化策略使得帝国内每个解至少存在多个学习对象并区别对待帝国内的最好解和其它殖民地;新型帝国竞争中给出了归一化总成本新定义并引入了殖民国家的全局搜索。通过实验系统地分析了总能耗的恶化程度与关键目标的改善程度之间的关系,并验证了差异化ICA的有效性与优势。(5)研究了以总延迟时间、makespan和总能耗为目标的绿色HFSP,其中总能耗重要性低于其他两个目标。采用新定义的支配关系处理目标间的相对重要性并提出了一种双层ICA,其中第一层只包含最强帝国,第二层为其他帝国。每个帝国在不同的搜索阶段执行不同的同化和革命方法,最强帝国不参与帝国竞争;每隔一定代数,记忆集与最强帝国结合重新构建新的帝国;为避免将最弱帝国中的最弱殖民地分配给取胜帝国,随机选择记忆集中的一个解加入取胜帝国。大量计算实验表明双层ICA在求解上述绿色HFSP方面具有较强的搜索优势。