基于分枝定界的动态流水车间最大完工时间问题研究

《基于分枝定界的动态流水车间最大完工时间问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、，．＾而．．一．．来化Ａ學靈日：巧±学位论文ｆＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＳＤＥＧＲＥＥＳ论文题目基于分枝定界的动态流水车间最大完工时间问题研究作者林琳学院软件学院专业软件工程指导教师任涛副教授ｍｍ备注１Ｉ二〇—五年六一月日副Ｍｂ麵密级分类号ＵＤＣ学位论文基于分枝定界的动态流水车间最大完工时间问题研究作者姓名；林琳指导教师：任涛副教授东北大学软件学院申请学位级别；硕±学科类别：工学学科专业名称：软件工程

2、论文提交日期：２０１５年６月论文答辩日期；２０１５年６月学位授予日期；２０１５年７月答辩委员会主席：姜慧研评阅人：于海白丹宇东北大学２０１５年６月ＡＴｈｅｓｉｓｉｎＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＯｎＤｙｎａｍｉｃＦｌｏｗＳｈｏｐＭａｋｅｓｐａｎＰｒｏｂｌｅｍｓＢａｓｅｄｏｎＢｒａｎｃｈａｎｄＢｏｕｎｄＡｌｏｒｉｔｈｍｇＢＬｉｎＬｉｎｙ＇Ｓｕｐｅｒｖｉｓｏｒ：ＡｓｓｏｃｉａｔｅＰｒｏ佐ｓｓｏｒ民ｅｊ約ａｏＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ化

3、ｎｅ２０１５独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研巧成果除加标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果一，也不包括本人为获得其他学位而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名；日期／已．／：＞０／学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部口或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本

4、人同意东北大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：一半年□一年□年半□两年□＂＂学位论文作者签名：１＾＾导师签名；／、ｂ：－、ｉ／ミ签字曰期；Ｔ＾ｄ７．签字曰期；＾＾／－－Ｉ东北大学硕去学位论文摘要基于分枝定界的动态流水车间最大完工时间问题硏究摘要在流水车间中，每个工件必须在不同机器上按照相同的加工路径进行加工，目标是确定使得目标函数最优的工件的加工序列一，在任何时刻，每台机器至多可加工个工件一，且每个王件至多

5、可在台机器上进行加工，所有机器按照相同的机器顺序加工工件，当某个工件在某台机器上进行加王时，该过程不可Ｗ彼中断。流水车间调度问题广泛存在于工业生产中，且大部分流水车间调度问题被证明是无法在多项式时间内求得最优解的ＮＰ难问题。即使是求解小规模的流水车间调度问题也是比较困难的。本文针对Ｈ类动态流水车间调度问题，极小化最大完工时间为目标函数进行了研究，分别提出了相应的分枝定界算法Ｗ获得小规模问题的最优解。最后通过数值实验仿真验证了算法的有效性。论文的主要内容概括如下：，针对带有到达时间的流水车间极小化最大完工时间问题

6、首先，提出对应的分枝定界算法，同时，提出分枝定界算法的分枝策略、剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与ＣＰＬＥＸ软件中的算法进行对比，验证了分枝定界算法在解决带有到达时间的流水车间极小化最大完工时间问题时具有较好的性能。其次，针对阻塞流水车间极小化最大完工时间问题，提出对应的分枝定界算法。同时，提出分枝定界算法的剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与ＣＰＬＥＸ软件中的算法进行对比，验证了分枝定界算法在解决小规模的阻塞流水车间极小化最大完工时间问题时的有效性。再

7、次，针对带有学习效应的流水车间极小化最大完工时间问题，提出对应的分枝定界算法，同时，提出分枝定界算法的分枝策略、剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与ＣＰＬＥＸ软件中的算法进行对比，验证了分枝定界算法在学习效应分别为线性函数、幕函数和指数函数时的有效性。最后，总结了本文所做的主要工作，对未来的研究方向进斤了展望。关键词：流水车间；最大完工时间；动态算法；分枝定界算法－ＩＩ－东北欠学硕去学位论文ＡｂｓｔｒａｃｔＯｎＤｎａｍｉｃＦｌｏｗＳｈｏＭａｋｅｓａｎＰｒｏｂｌｅｍｓｙ

8、ｐｐＢａｓｅｄｏｎＢｒａｎｃｈａｎｄＢｏｕｎｄＡｌｏｒｉｔｈｍｇＡｂｓｔｒａｃｔＩｎａｆｌｏｗｓｈｏｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｅａｃｈｏｂｍｕｓｔｂｅｏｃｅｓ