制造系统柔性作业车间调度问题及算法优化

发布时间：2020-05-07 00:12

【摘要】：随着先进制造技术、先进管理模式以及信息化的快速发展,市场需求逐渐由单一化向多元化转变,个性化、定制化产品成为制造业企业的发展趋势。制造企业面临着资源多样化、信息共享化、竞争全球化以及新技术变革的制造环境,即是挑战又是机遇。如何更好地将制造系统内的柔性资源进行科学的配置调度是制造企业发展的核心环节。然而,随着制造系统复杂性的增加和柔性资源数量的增加,优化调度的复杂性和难度也急剧增加,因此,该问题的研究即有实践价值,也具有理论意义。研究制造系统在确定环境下柔性加工车间的调度问题(Flexible Job-Shop Scheduling Problem,FJSP)是本文的焦点,以柔性作业车间调度的单目标优化为起点,用改进的遗传算法以工件最大完工时间为目标进行优化。遗传算法作为一个功能强大且经常使用的演化策略,全局搜索能力强,然而,该算法局部搜索能力较弱,导致可行解在全局搜索之前陷入局部最优的可能。为了克服这个缺点,采用禁忌搜索算法引导局部搜索过程,该混合算法能够使搜索空间充分多样化。具体过程中,用分段式集成编码以及基于插入式贪婪算法解码,以染色体结构为基础提出了有效遗传算子。通过对基准问题的计算测试,所提出的算法在解的质量及效率方面取得显著的提高。根据现实制造系统中调度所关注的热点问题,除了机器负载、总拖期时间以及常见的完工时间以外,引入动态费率和静态费率,重新建立了多目标柔性作业车间调度模型,该模型充分考虑了生产成本与运行成本,更加符合柔性作业车间调度处理。针对NSGA-II算法在求解FJSP局部收敛的缺陷,利用免疫和熵原理改进选择策略,引入分布函数改进精英保留策略,更好地维持种群的多样性,成功地避免算法早熟和局部收敛的问题。通过基准问题的测试计算及实例仿真,本文所构建的多目标柔性作业车间模型及其改进算法是可行及有效的。最后,结合制造企业面临的低碳、节能问题,以总延期时间和总碳足迹最小化为目标,建立低碳排放约束的柔性作业车间调度模型。通过运用本文提出的NSGA-II算法获得了满意的帕累托最优解集。鉴于碳足迹优化方法的新颖性,采用MOGA和SPEA2算法作为对比算法,通过算例以及多项评价标准的比较,验证了碳足迹车间调度优化方法以及NSGA-II算法的可行性及有效性。
【图文】：

甘特图,可行解,有向图,可行调度

图2.1 3×3FJSP的一个可行解的有向图图2.2 相对应的甘特图以获得工序的关键路径，从起点节点到终点节点的最长的长度等于可行调度的最大完工时间，一个可行调度解析取图描述调度问题的目标是如何获得一个非循环有向（或关键路径的长度）最小。，，关键路径为 0*2111121333 O O O O O 。其

甘特图,甘特图,关键路径,最大完工时间

sD ，每个非循环都有一个可行的调度方案与之对应。例如图2.1中相对应的甘特图为图2.2所示，其中机器1上的选择为{,,}1211132S OOO，机器2上的选择 {,,}2311223S OOO，机器3上的选择 {,,}3221333S OOO。图2.1 3×3FJSP的一个可行解的有向图图2.2 相对应的甘特图从析取图中可以获得工序的关键路径，从起点节点到终点节点的最长路径被称作关键路径，关键路径的长度等于可行调度的最大完工时间，一个可行调度解中有存在多条关键路径的可能。析取图描述调度问题的目标是如何获得一个非循环有向图sD ，使得sD中最长路径的长度（或关键路径的长度）最小。如图 2.1 所示，关键路径为 0*2111121333 O O O O O 。其中21O 、11O 、12O 、13O 、33O 表示关键工序。关键路径的变化是改变最大完工时间的关键
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18;F273

【相似文献】