一定条件下平行机排序问题的研究Y(申请浙江大学理学硕士学位论文)培养单位指导教师运筹学与控制论黄宜坤738223学科研究生浙江大学数学系杨启帆教授二零零六年五月摘要主要考虑了最大完工时间(G。。。)、总完工时间(∑cj)、最大延误时间(L。。。)。全机的情况。我们设计了一个竞争比为；的算法，并且证明了此界是紧的。特别地，对于m台机的情况，我们给出了此问题的一个下界为丛；地。论文主要研究了两类排序问题：～类是已知最大工件加工时间的半在线平行机排序问题；另一类是关于工件加工时间恶化单处理机排序问题。目标函数文共分四章。第一章是绪论部分，主要介绍排序问题相关的‘一些基本概念和预备知识，调度理论中常用的各种专业术语和已有的一些结果。第二章主要研究了已知最大工件加工时间半在线平行机排序问题针对三台第三章主要是关于工件加工时问恶化问题的若干研究，总结并证明了一，些性质，相应的设计了一些新的模型，给出了一些算法。第四章主要回顾了本文的一些结论，探讨了解决问题中存在的困难，并指出了以后进一步的研究方向，提出了个人看法。关键词：平行机排序，下界，虽坏情况界，EDD，SPTleast牮for／7／,machineofP3llc‰nzP3lmaxlGn。。Abstractjobstimes．Objectknowledgeadvance．Weandtimes．WeWords：Parallelmachinemaximumpresentj3．Moreover,thesunmaarizeInthispaper,westudythesemi-onlineparallelschedulingproblemwhereweknowlargestprocessingtimeofallinadvance．Andalsoconsiderswithdeteriorationfunctionisminimizeschedulelength，totalcompletionlateness．Thethesisconsistsfourchapters．chapter1，wegivessomeintroductionbasicforprob—lems，sometermsresultsfield+2，westudiessemi—onlineversionsprocess—ingknownwillalgorithmcompetitiveratiolowerbounderimprove3，weproblemsshowqualities，anddesignalgorithmsmodelswhichdesign．4，wemainlyreviewedconclusionsarticle，discussedhassolveddifficultyquestionexisted，aswellmainpointsfuturebrieflyintroducedproposeindividualview．Keyscheduling，lowbound、EDD，SPTtoatcase．areas1．1排序问题概述第一章绪论排序(又称为调度)问题是组合最优化领域中的一类重要问题，它产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度、学校课程表的制订，到宇宙的复杂庞大的飞行计划，都要用至lJhp序的理论和算法。在理论上它又和算法设计与分析、计算复杂性理论密切相关。近几十年来，排序问题得到了运筹学界、计算机科学界、工程学界和管理学界极大的关注，鉴于经典问题的研究日益深入，而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入成熟期。处理机、任务或者作业和Ifl标函数三要素组成了排序问题。处理机的数量、类型和环境有很多种情况，任务或作业和资源的约束更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型。我们用Graham等人首先使用的三元组(three—fieldrepresentation)来描叙问题的类型，这样大大简化了排序问题的表示。三元组记号由三个域组成：nl卢h，它表示一个具体的排序问题，三个参数域％卢和1分别刻画了机器状况，工件特征和目标函数．下面我们分别对每个参数所代表的含义作具体介绍。o域表示处理机的数量、类型和环境，它可以为1：单处理机．Pm：m个同速机．0m：仇个恒速机．Rm：m个变速机．Fm：m个处理机，流水作业．Om：m个处理机，开放作业．Jm：m个处理机，异顺序作业．第’章绪论完工时间，最大延误时间，最大误工时间等，在此我们就不⋯‘介绍了。有关排序称C‰。。=maxG为该排序的最大完工时f自J(makespan)，Ck。=rainL沩该排序的最小机器负载。于是C★。。和c毫t。就可看成