两阶段混合流水车间调度问题研究

发布时间：2017-04-24 17:23

  本文关键词：两阶段混合流水车间调度问题研究，由笔耕文化传播整理发布。

【摘要】：本文主要研究两阶段混合流水车间的调度问题。混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP)也称柔性流水车间调度问题(Flexible Flow Shop Scheduling Problem),是一般流水车间调度问题和与并行机调度问题的结合。即使在简单的混合流水车间中调度模型中,也已经被证明是NP难问题,无法得到最优解。然而,在流程工业中,尤其是在汽车生产、冶金和化工等领域,HFSP调度问题非常具有代表性,应用日趋广泛,因此,该问题成为近年来各国专家学者关注的热点。 在实际生产过程中,生产线可以产出由不同零件装配而成的不同产品。本文研究的调度问题包含机械加工与装配操作。机械加工阶段可以看作是混合流水车间,包含两个阶段,且每个阶段都含有不同数目的并行机台。首先,本文针对包含装配阶段的两阶段混合流水车间调度问题,建立了混合整数规划数学模型,采用ILOG OPL Studio软件对模型进行验证及修正；其次,基于Johnson规则与LPT(Longest Processing Time)规则提出启发式演算法(简称为H演算法),对装配阶段中待加工的产品进行定向排序,继而指派零部件的加工顺序。同时,对离散粒子群算法及变邻域算法进行改进,建立两种新的算法：第一,采用基于工件顺序与位置相互对应的编码方式进行编码,将H演算法产生的工件序列作为初始解,提出改进离散粒子群算法；第二,采用实数编码方式,通过颠倒、插入等操作扩大搜索空间,然后通过交换操作进行局部搜索,并将H演算法产生的序列作为初始解,提出改进变邻域搜索算法；最后,应用H演算法、改进离散粒子群算法及改进变邻域算法,对包含装配阶段的两阶段混合流水车间调度问题进行求解,同时提出两个下界,实现了对三种全新演算法与原有算法求解质量的快速评价和分析。 大量的实验分析证明：H演算法具有能够得到近似最佳解、求解时间短等优点,尤其在求解大规模调度问题时,利用H演算法求解问题的近似最优解在求解时间方面具有更大的优势。
【关键词】：混合流水车间 两阶段装配 最小化最大完工时间
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497
【目录】：

• 摘要4-6
• Abstract6-8
• 目录8-10
• 第1章 绪论10-18
• 1.1 研究的背景及意义10-12
• 1.2 国内外研究现状12-16
• 1.2.1 国外研究现状12-13
• 1.2.2 国内研究现状13-15
• 1.2.3 国内外研究成果对比分析15-16
• 1.3 主要的研究内容及结构安排16-18
• 1.3.1 主要的研究内容16-17
• 1.3.2 结构安排17-18
• 第2章 两阶段混合流水车间调度问题分析与建模18-32
• 2.1 对问题的描述18-20
• 2.2 混合整数线性规划模型的建立20-27
• 2.2.1 模型的参数设计21
• 2.2.2 决策变量的定义21-22
• 2.2.3 混合整数规划模型的建立22-27
• 2.3 下界的提出27-29
• 2.4 本章小结29-32
• 第3章 三种新算法的设计32-54
• 3.1 启发式H演算法设计32-36
• 3.2 粒子群优化算法概述36-40
• 3.2.1 粒子群算法的设计思想36-37
• 3.2.2 粒子群算法的基本原理37-40
• 3.3 改进离散粒子群算法H-DPSO设计40-47
• 3.3.1 粒子的编码方案41-44
• 3.3.2 粒子的解码方案44
• 3.3.3 离散粒子群算法的基本步骤44-45
• 3.3.4 改进的离散粒子群算法H-DPSO45-47
• 3.4 改进变邻域搜索H-VNS算法的建立47-52
• 3.4.1 局部搜索策略47
• 3.4.2 变邻域搜索算法VNS的基本框架47-48
• 3.4.3 基本变邻域算法的搜索步骤48
• 3.4.4 改进变邻域搜索算法H-VNS的实现流程48-52
• 3.5 本章小结52-54
• 第4章 实验分析54-66
• 4.1 实验的目的54
• 4.2 实验的环境及参数设置54-55
• 4.3 实验的结果及对比分析55-65
• 4.4 本章小结65-66
• 第5章 结论与展望66-68
• 5.1 全文结论66-67
• 5.2 未来展望67-68
• 参考文献68-72
• 作者简介72-74
• 攻读学位期间从事主要的科研工作74-76
• 致谢76

【参考文献】

中国期刊全文数据库 前10条

1 田野;刘大有;;求解流水车间调度问题的混合粒子群算法[J];电子学报;2011年05期

2 严洪森;万晓琴;熊福力;;基于VNS-EM混合算法的两阶段装配流水车间调度[J];东南大学学报(自然科学版);2014年06期

3 王凌;周刚;许烨;金以慧;;混合流水线调度研究进展[J];化工自动化及仪表;2011年01期

4 徐俊刚,戴国忠,王宏安;生产调度理论和方法研究综述[J];计算机研究与发展;2004年02期

5 张建军;王春芳;;求解混合流水车间调度问题的改进型PSO算法[J];计算机工程与应用;2011年31期

6 轩华;;含串行批处理机的三阶段混合流水车间调度问题[J];计算机集成制造系统;2012年05期

7 刘烽;杨涛;游海;俎宇鹏;刘文明;;基于免疫克隆选择算法的混合流水车间调度问题的研究[J];计算机与网络;2011年21期

8 王圣尧;王凌;许烨;;求解相同并行机混合流水线车间调度问题的分布估计算法[J];计算机集成制造系统;2013年06期

9 宋继伟;唐加福;;基于DPSO的无等待混合流水车间调度方法[J];系统仿真学报;2010年10期

10 潘全科;朱剑英;;解决无等待流水线调度问题的变邻域搜索算法[J];中国机械工程;2006年16期

中国博士学位论文全文数据库 前1条

1 田野;粒子群优化算法及其应用研究[D];吉林大学;2010年

  本文关键词：两阶段混合流水车间调度问题研究，由笔耕文化传播整理发布。

，

本文编号：324603