双机流水车间问题基于冲突窗口的滚动调度算法

发布时间：2017-11-25 20:14

  本文关键词：双机流水车间问题基于冲突窗口的滚动调度算法

  更多相关文章： 流水车间 滚动调度 冲突窗口 大规模仿真

【摘要】：生产调度问题存在于大量实际制造业中,构成了各种先进制造模式共同关注的核心内容和重要组成部分,对于车辆调度、铁路调度、航空调度、企业多项目管理的等资源调度问题,也大多可以利用生产调度的基本原理,可以说,生产调度这一基本原型应用领域是非常广泛的。同时,生产调度问题也是一类非常典型的组合优化问题,在求解方面具备相当的难度,其计算量通常随调度问题规模呈指数增长,绝大多数调度问题都属于NP完备问题。因此,无论在实际工业生产方面,还是在理论学术研究方面,对生产调度问题的研究都有着非常重要的意义。生产调度的算法可简单概括为精确算法、启发式算法和人工智能算法。精确算法能获得最优解,但是计算效率低,遇到大规模的复杂问题,这种算法有时甚至难以获得解。由此而发展起来的启发式算法则是利用启发式规则,在较短的时间内便能获得相对不错的解,目前已扩展了相当多的启发式规则。随着科技进步,人工智能算法是目前研究较为集中的一种算法,它具有搜素效率高,适应性强和鲁棒性能好等特点,但是这类算法也不能保证获得最优解。由于流水车间的特点,本文主要着眼于启发式算法。在启发式算法下,本文采用滚动调度策略,研究了流水车间双机调度问题。滚动调度策略下,将一个大规模问题分解为许多子问题,可使问题规模大大减小,有效缩短求解时间。滚动调度多用于单机情形,此次将其应用于流水车间双机情形,同时跳出传统的滚动调度策略框架,即基于时间的滚动调度和基于工件数的滚动调度,提出本文新的滚动调度算法——基于冲突窗口的滚动调度算法。该算法充分利用了流水车间双机问题的特点,结合了经典的Johnson规则。在本文中描述了冲突窗口的形成,子问题的最优调度,列述了算法的基本思路和步骤。另外,本文采用大规模仿真的方法,将本算法与另三种算法,即基于时间的滚动调度算法、基于工件数的滚动调度算法和贪婪Johnson算法进行了大量对比,这三类算法是流水车间比较传统的算法。仿真模拟了各算法在工件数为10到500个时的具体表现,并通过控制参数使得工件的到达呈现不同的紧密程度。最终实验结果显示,除了工件数为10时,基于时间的滚动调度算法比基于冲突窗口的滚动调度求解的质量更优,其余情况下,基于冲突窗口的滚动调度平均表现都是最好的,另外本论文提出的算法在计算量上相对另两种滚动调度算法具有绝对的优势,即使解决500个工件的大规模问题,效率也非常高,贪婪Johnson算法虽然在时间上也具有优势,但在四种算法中解的质量最差。最后本文将基于冲突窗口的滚动调度应用于带有季节性需求特征的具体实例中,以探讨其实际应用价值。通过仿真的方法,基于冲突窗口的滚动调度相较于基于时间的滚动调度能更好地处理需求波动大的季节性产品,其求解速度更快,求解质量更好。
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TB497

【参考文献】

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

1 方剑,席裕庚;基于遗传算法的滚动调度策略[J];控制理论与应用;1997年04期

2 ;Rolling optimization algorithm based on collision window for single machine scheduling problem[J];Journal of Systems Engineering and Electronics;2005年04期

3 钱斌;王凌;黄德先;江永亨;王雄;;动态零等待流水线调度问题的滚动策略及优化算法[J];控制与决策;2009年04期

4 唐聃;黄健;;流水车间调度问题的启发式算法研究[J];电子科技大学学报;2013年06期

5 黄健仓;;建设企业多项目管理中的资源调度问题研究[J];中国软科学;2016年01期

6 范华丽;熊禾根;蒋国璋;李公法;;动态车间作业调度问题中调度规则算法研究综述[J];计算机应用研究;2016年03期

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

1 刘延风;置换流水车间调度问题的几种智能算法[D];西安电子科技大学;2012年

，

本文编号：1227240