一定条件下平行机排序问题的研究

《一定条件下平行机排序问题的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Y738223一定条件下平行机排序问题的研究(申请浙江大学理学硕士学位论文)培养单位学科研究生指导教师浙江大学数学系运筹学与控制论黄宜坤杨启帆教授二零零六年五月摘要论文主要研究了两类排序问题：～类是已知最大工件加工时间的半在线平行机排序问题；另一类是关于工件加工时间恶化单处理机排序问题。目标函数主要考虑了最大完工时间(G。。。)、总完工时间(∑cj)、最大延误时间(L。。。)。全文共分四章。第一章是绪论部分，主要介绍排序问题相关的‘一些基本概念和预备知识，调度理论中常用的各种专业术语和已有的一些结果。第二章主要研究了已知最大工件加工时间半在线平行机排序问题针对三台机的情况。

2、我们设计了一个竞争比为；的算法，并且证明了此界是紧的。特别地，对于m台机的情况，我们给出了此问题的一个下界为丛；地。第三章主要是关于工件加工时问恶化问题的若干研究，总结并证明了一，些性质，相应的设计了一些新的模型，给出了一些算法。第四章主要回顾了本文的一些结论，探讨了解决问题中存在的困难，并指出了以后进一步的研究方向，提出了个人看法。关键词：平行机排序，下界，虽坏情况界，EDD，SPTAbstractInthispaper,westudythesemi-onlineparallelmachineschedulingproblemwhereweknowthelargestpr

3、ocessingtimeofalljobsinadvance．Andwealsoconsiderstheschedulingproblemwithdeteriorationofprocessingtimes．Objectfunctionistominimizeschedulelength，totalcompletiontimeandmaximumlateness．Thethesisconsistsoffourchapters．Inchapter1，wegivessomeintroductionandbasicknowledgeforschedulingprob—lems，s

4、ometermsandresultsinthisfield+Inchapter2，westudiessemi—onlineversionsofP3llc‰nzwiththelargestprocess—ingtimeofalljobsisknowninadvance．WewillpresentalgorithmforP3lmaxlGn。。andthecompetitiveratioofthealgorithmisj3．Moreover,thelowerbounderwewillimproveisattheleast牮for／7／,machinecase．Inchapter3

5、，weconsidersproblemsofdeteriorationofprocessingtimes．Wesunmaarizeandshowsomequalities，andalsodesignsomealgorithmsformodelswhichwedesign．Inchapter4，wemainlyreviewedsomeconclusionsinthisarticle，discussedhassolvedthedifficultywhichinthequestionexisted，aswellasthemainpointsinfuturestudiesarebr

6、ieflyintroducedandproposeindividualview．KeyWords：Parallelmachinescheduling，lowbound、EDD，SPT第’章绪论1．1排序问题概述第一章绪论排序(又称为调度)问题是组合最优化领域中的一类重要问题，它产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度、学校课程表的制订，到宇宙的复杂庞大的飞行计划，都要用至lJhp序的理论和算法。在理论上它又和算法设计与分析、计算复杂性理论密切相关。近几十年来，排序问题得到了运筹学界、计算机科学界、工

7、程学界和管理学界极大的关注，鉴于经典问题的研究日益深入，而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入成熟期。处理机、任务或者作业和Ifl标函数三要素组成了排序问题。处理机的数量、类型和环境有很多种情况，任务或作业和资源的约束更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型。我们用Graham等人首先使用的三元组(three—fieldrepresentation)来描叙问题的类型，这样大大简化了排序问题的表示。三元组记号由三个域组成：nl卢h，它表示一个具体的排序问题，三个