多代理生产调度问题的理论研究

《多代理生产调度问题的理论研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ｍｍｍ．．：－博±学位论文ＤＯＣＴＯ民ＡＬＤＩＳＳＥＲＴＡＴＩＯＮ、———．一＊—＾＾？？《代理生产调度问题的理论研究．＇■■琴作者赵麵＇：，／学信息科学与工程学院．］专业系统工程指导教师—唐立新教授胃ｍｐｕｐｉｐｍ—秀誦：ｒ．二〇—五年五月四日．博±学位论文多代理生产调度问题的理论硏究赵晓丽？來六？擎二０—五年Ｓ月分类号密级ＵＤＣ学位论文多代理生产调度问题的理论研究

2、作者姓名：赵晓丽指导教师：唐立新教授东北大学工业工程与物流优化研究所申请学位级别；博±学科类别：工学学科专业名称：系统３＾论文提交日期：２０１５年３月论文答辩日期：２０１５年４月学位授予日期：答辩委员会主席：刘建昌评阅人：东北大学２０１５年３月ＡＤｉｓｓｅｒｔａｔｉｏｎｆｏｒｔｈｅＤｅｒｅｅｏｆＤｏｃｔｏｒｉｎＳｓｌ：ｅｍｓＥｎｉｎｅｅｒｉｎｇｙｇｇ－ＴｈｅｏｒｅｔｉｃａｌＲｅｓｅａｒｃｈｏｎＭｕｌｔｉａｇｅｎｔＰｒｏｄｕｃｔｉｏｎＳ

3、化ｅｄｕｌｉｎｇＰｒｏｂｌｅｍｓ巧ＺｈａｏＸｉａｏｌｉＳｕｅｒｖｉｓｏｒ：Ｐｒｏｆｅ化ｏｒＴａｎＬｉｘｉｎｐｇＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙＭａｒｃｈ２０１５独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加欧标注和致谢的地方外，不包含其他人己经发表或撰写妊一。的研究成果，也不包括本人为获得其他学位而使用过的材料与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名

4、：曰期：游斗，学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部口或机构送交论文的复印件和。磁盘，允许论文被查阅和借阅本人同意东北大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索。、交流作者和导师同意网上交流的巧间为作者获得学位后：半年□一年□一年半□两年口／学位论文作者签名：ｉ么知导师签名：）签字日期：签字日船朵Ｋ、女牛成皆分厶东北大学博壬学位论文摘要多代理生产调度问题的

5、理论研究摘要一生产调度是指对给定的组工件和多台机器，，在满足生产工艺的约束下确定每台机器上工件的顺序与时间，Ｗ使得能源、资源或效率等指标达到最优。往的调度研究主要集中在所有工件作为一一致的性能指标作为个整体考虑目标。但是随着经济的发展和人们消费水平的提高，顾客对商品的个性化和多样化的需求越来越高，传统的调度理论已不再适合这种新的需求情况下的调度问题。所Ｗ迫切需要研究考虑顾客多样性需求的多代理生产调度问题。一多代理生产调度是指每个顾客的需求对应个代理，所有代理竞争在共同的机器上

6、同时加王各自的工件，使得每个代理的目标达到最优。本文钢铁生产中不同生产阶段的工艺过程为背景一，提炼出多代理生产调度中系列问题。针对带有依赖于时间恶化工件的双代理单机调度问题、带有线性恶他工件的双代理单机批处理机调度问题、单机批处理机上多代理合作博弈问题、Ｗ及带有线性恶化工件的双代理两台机器车间调度问题进行了理论研究。对于上述问题，分别进行了复杂性分析；对于可解问题，给出了最优－算法或分配机制，；对于难解问题，给出了ＮＰ难证明，对难解问题的特殊情况分析了最优解的结构特征和性质，构造了多项

7、式或伪多项式时间的求解方法。具体肉容概括如下：１工件释放时针对带有线性恶化工件和释放时间的双代理单机调度问题，考虑了）间相同与不同两种情况如下：１当工件释放时间相同时，针对最小化代理＾的总加权（）５工一拖期工件个数使得代理件完工时间的最大费用不超过个给定上界的问题，证明了－难性，问题的ＮＰ。对于代理５工件完工时间的最大费用为最大完工时间的特殊情况分析了最优解性质，给出了伪多项式时间动态规划算法进行求解；对于代理＾的所有工件具有相等权值特殊情况，通过分析可中断问题的最优解结构与性质，给

8、出了求解问题的多项式时间最优算法。（２当工件释放时间不同时，针对最小化代理＾的总拖期王件个）５一数使得代理的总拖期工件个数不超过个给定上界的问题，证明了问题在不同数量释一一王期情况下的ＮＰ－放时间与难性。对于所有工件具有致的释放时间与工期，或同代一，理的工件具有相同恶化率和致的释放时间与工期两种特殊情况，分析了最优解性质分别给出了多项式时间动态规划算法进行求解。