带有松弛量的平行工序顺序化优化方法探究.pdf

华北电力大学(北京)
硕士学位论文
带有松弛量的平行工序顺序化优化方法探究
姓名:韩璐
申请学位级别:硕士
专业:应用数学
指导教师:邱启荣
20080115
摘要带有松弛变量的平行工序顺序优化的问题是指从��龆懒⒔�械钠叫泄�序中选择�龅髡�K承蚬ば蛄吹挠呕�侍狻8梦侍馇∈窍钅颗判蛑锌悸腔�����������.��,������间和带有任意松弛变量问题中的一种。其自身的复杂性使得传统的运筹学中的线性规划和启发式方法都不是解决该问题的较好的办法。本文针对该问题,针对网络中工序本身具有的机动时间的特性。按照由此推导出的亏值定理从网络自身的规律出发。推导出工序后移定理和最大亏值定理。在此基础上制定出合理的调整工序的目标函数和每次选择调整工序的优化方法。最终解决了平行序链顺序化最优决策的问题。在最优顺序链的基础上,调整得到整个序链全部工序顺序都优化过后的初始序链。在此基础上,基于在初始序链的基础上通过删除合适的工序可以得到带有松弛量的平行工序的顺序优化序链的想法。依靠推导出的去工序定理和最小亏值序链定理给出了选择最优被删除工序的依据和方法。最终解决了带有松弛变量的平行工序的顺序化优化问题。关键词:排序;机动时间;松弛变量;亏值����也������������.�������������瓵�����������.����甀������瑃������,�����瑃����篠�����籄�������籖���������;�����
喁△:工序∞的后单时差强:工序∞的最早开始时间%:工序�叩淖钤缃崾�奔�△%:工序�俚那暗ナ辈�巧:工序�叩幕��奔�五:路线�某ざ燃绰烦ぁ�五�,�:路线卢�,�的路长。五�疲郝废遬�,曲的路长。△略:工序①�那肮灿檬辈�晖△:工序�俚暮蠊灿檬辈�蜴△:工序�俚暮蠊灿檬辈�职:节点。的后共用时差主要符号表三岛:工序�叩淖畛倏J际奔�￡弓:工序�叩淖畛俳崾�奔�肛:路线。��琲�涸吹恽儆虢诘恪V�渎废摺�����瑆�航诘恪S牖愕恽嶂�渎废摺�以:源点③与节点。之间的最大路长。以’:源点⑨与节点。之问的最大路长所在的路线,又称节点。的前主链。“:节点。与汇点⑨之间的最大路长。.�
如�汗�ば騩①的所有路线中最大路长所在的老路线,或称过�诘奶卣髀废摺�“。:节点。与汇点⑨之间的最大路长所在的路线,又称节点。的后主链。�:关键路线。�:最大路长。心:过工序�艿娜我饴废摺�
导师签名:耳窟彰学位论文作者签名:一鞋监熟盗关于学位论文使用授权的说明声明期:旦圣焦珏���期:一�—乡尸华北电力大学堕垒墨塑堕旦日期:本人完全了解华北电力大学有关保留、使用学位论文的规定,即:①学校有权保管、并向有关部门送交学位论文的原件与复印件;②学校可以采用影印、缩印或其它复制手段复制并保存学位论文;③学校可允许学位论文被查阅或借阅;④学校可以学术交流为目的,复制赠送和交换学位论文:⑤同意学校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。�婷艿难�宦畚脑诮饷芎笞袷卮斯娑�作者签名:日本人郑重声明:此处所提交的硕士学位论文《带有松弛量的平行工序顺序化优化方法探究》,是本人在华北电力大学攻读硕士学位期间,在导师指导下进行的研究工作和取得的研究成果。据本人所知,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得华北电力大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。
引言顺序工序链的优化问题的枚举量是�軲�U庠对洞笥诨趵傻����獾拿毒倭縈�必是个工序调整为顺序工序链的优化问题是考虑机动时间和松弛变量的平行工序顺序优化问题至今为止还未找出多项式算法。从Ⅳ个平行工序中选择��堍�个工序调整为在国内,平行工序的顺序优化问题被称为单个工序链的顺序优化问题圆,单个工序链的可能在机器排序问题中的应用,但缺少对它们应用的描述:文献��在研究项目排序中网络计划技术产生在�世纪�年代,最初只用于工期的管理。随着技术经济分析的需要,引进了成本和费用率的概念,从而使网络技术可以更准确的进行概预算,有力的控制工程的进度和成本。项目管理尤其是项目进度管理与网络计划技术结合得非常紧密。当前,资源限制下的项目进度管理��绻て谧钚』�是项目管理研究的热点问题。资源限制的考虑使得原先一些项目计划与控制中已成为体系的一些基本概念不再成立。例如,关键路线的概念,它表示决定项目总工期的工序链,但在资源有限条件下它的这一特性也不再有效�诘�松弛量与工序机动时间�闹掷嘈投及��的概念在该条件下也类似。关于这些概念在考虑了资源限制的条件下不能在使用的例子,参见文献�】。在资源限制条件下项目的分析与优化从存理论的角度