限制性总完成时间跨度问题及其算法设计

《限制性总完成时间跨度问题及其算法设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号０１５７密级公开ＵＤＣ编号《余尖聲巧女研堯４缘隹俗Ａ巧目报制性总完成时间巧度间面及其３ｔ巧役计ＴｉｔｌｅＴｈｅＰｒｏｂｌｅｍｏｆＭａｋｅｓｐａｎｏｆＴｏ化１ＣｏｍｐｌｅｔｉｏｎＴｉｍｅｗｉｔｈＲｅｓｔｒｉｃｔｉｏｎｓａｎｄＤｅｓｉｇｎｏｆＩｔｓＡｌｇｏｒｉｔｈｍｓ学院（所、中私）数学与统计学院专业名称计篇数堂研巧生姓名规玉洁学号１２０１３０Ｑ０８Ｑ２导师姓名李建平职称教授２０１６年５月ＩＩ扉页：论文独创性声明及使用授权

2、本论文是作者在导师指导下取得的研巧成果。除了文中特别加标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不存在劉窃或抄一袭行为。与作者同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下；学校有权保留本论文（含电子版），也可Ｗ采用影印、缩印或其他复制手段保存论文；学校有权公布论文的全部或部分内容，可Ｗ将论文用于查阅或借阅服务：学校有权向有关机构送交学位论文用于学术规范审查、化会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检

3、索服务。（内部或保密的论文在解密后应遵循此规定）从、、人珠导师答名！ｋｂ研究牛篇名：举：日期；摘要一本论文主要研充限制性总完成时间跨度问题，该问题是平行机排序问题的种推广形式一。在限制性总完成时间跨度问题中，每项工作只能在给定的若干台机器一旦开始被加王上进行加工，工作，中途不能停止，直到加工完毕，问；在加王过程中一。题的目标是要寻找个最优分配方案，使得该方案的总完成时间跨度达到最小为了解决限制性总完成时间跨度问题，本文利用最小总完成时间优先原则和最小总加工时间优先原则，分别设计了两种不同的启发式算法，称为

4、ＳＴＣ优先算法和ＳＭＳ优２先算法，其时间复杂性分别为０ｎ＋ｒｒｍｌｏｇｎ和０ｎｌｏｇｎ＋ｍ，该里ｍ和ｎ分别（（））（（））表示机器数目和工作数目。关键词：总完成时间；跨度；启发式算法；时间复杂性１ＡｂｓｔｒａｃｔＩ打ｔｈｉｓｔｈｅｓｉｓｗｅｓｔｕｄｔｈｅｒｏｂｌｅｍｏｆｔｈｅｍａｋｅｓａｎｏｆｔｏｔａｌｃｏｍｌｅｔｏ打ｔｉｍｅｉ，ｙｐｐｐｗｉｔｈｒｅｓｔｒｉｃｔｉｏｎｓｗｈｉｃｈｉｓ岔ｅｎｅｒａｌｉｚａｔｉｏｎｏｆｔｈｅａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎ．

5、Ｉｎｏｕｒ，ｇｐｇ打ｅｗｐｒｏｂｌｅｍ，ｅａｃｈｊｏｂｃａｎｏｎｌｙｂｅｐｒｏｃｅｓｓｅｄｏｎｓｏｍｅｓｐｅｃｉｆｉｅｄｍａｃｈｉｎｅｓ；Ｄｕｒｉｎｇｔｈｅｐｒｏｃｅｓｓ江ｏｂｓｔａｒｔｓｔｏｂｅｒｏｃｅｓｓｅｄ化ｃａｎ打ｏｔｂｅｉ凸ｔｅｒｒｕｐｔｅｄｕｎｔｉｌｔｈｅｏｂ，ｊｐ，ｊｉｉｓｃｏｍｐｌｅｔｅｌｙｅｘｅｃｕｔｅｄ．Ｔｈｅｏｂｅｃｔｉｖｅｉｓｔｏｆｉ凸ｄａｎａｌｌｏｃａｔｏ打ｓｃｈｅｍｅｔｏｍｉｎｉｍｉｚｅｊｔｈｅｍａｋｅｓｐａｎｏｆ

6、ｔｏｔａｌｃｏｍｐｌｅｔｉｏｎｔｉｍｅ．Ｕｓｉｎｇｔｈｅｐｒｉｏｒｉｔｙｏｆｔｈｅｓｈｏｒｔｅｓｔｔｏｔａｌｃｏｍｐｌｅｔｉｏｎｔｉｍｅａｎｄｔｈｅｓｈｏｒｔｅｓｔｍａｋｅｓｐａｎｗｅｄｅｓｉｎｔｗｏｈｅｕｒｉｓｔｉｃａｌｒｉｔｈｍｓ，ｇｇｏ，ｃａｌｌｅｄａｓＳＴＣｆｉｒｓｔａｌｇｏｒｉｔｈｍａｎｄＳＭＳｆｉｒｓｔａｌｇｏｒｉｔｈｍｗｈｏｓｅｔｉｍｅｃｏｍｌｅｘｉｔａｒｅ，ｐｙ２０（（打＋ｍｎｌｏｇｎａ打ｄ０ｎ（ｌｏｇ打＋ｍ）），ｒｅｓｐｅｃｔｉｖｅｌｙ

7、）ｗｈｅｒｅｍａｎｄ化ｄｅ打ｏｔｅｔｈｅ））（ｎｕｍｂｅｒｏｆｍａｃｈｉｎｅｓａｎｄｏｂｓｒｅｓｅｃｔｉｖｅｌｙ．ｊ，ｐｏｔａＭａｋ－Ｋｅｗｏｒｄｓｌｃｏｍｉｏ打ｔｉｍｓｔｉｃｌｉｙ：Ｔｐｌｅｔｅｅｓａｎ打ｅｕｒｉａｏｒｔｈｍＴｉｍｅｃｏｍ；ｐ；ｇ；ｐｌｅｘｉｔｙ目录摘要ｉＡｂｓｔｒａｃｔｉｉ一第章引Ｓ１１１．１理论背景、１．２［司题来源２１．３主要结果３１４论文．结构３第二章预备知识日２．１组合最优化理论５２．

8、２完成时间跨度问题及算法设计策略７２．３总完成时间跨度问题及算法设计策略９第Ｈ章限制性总完成时间跨度问题及算法设计１２３．１ＳＴＣ优先算法