带服务等级的排序问题的若干研究y(申请浙江大学理学硕士学位论文)73823l培养单位运筹学与控制论勇学科研究生指导教师浙江大学数学系萍何教授二00六年三月周摘要本文主要研究具有服务等级的平行机排序问题预先赋予每个任务和每台机出了求解这类问题的新算法．从而大大改进了已知文献中的结果2一未T．全文共对m=3的情形给出了一个最坏情况界为i十({)‘的算法，并证明了这个界是紧况界为i4+({)‘，其中≈是预先给定得迭代次数．函数为极小化最大的机器完工时间．给出了一个最坏情况界为{+({)‘的算法．器一个服务等级标号，使得服务等级低的机器既能加工服务等级低的任务，又能加工服务等级高的任务，而服务等级高的机器只能加工服务等级高的任务．目标函数是极小化最大机器完工时间．这类问题最先是Hwang等提出来的．本文给第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识．第一章主要研究了具有两个服务等级的m台平行机排序问题．目标函数是极小化最大的机器完工时间(Ckax)．给出了一个修正的M矿LT，F，T算法，其最坏情第三章主要研究了一般情况下具有服务等级的m台平行机排序问题．目标关键词：、F行机排序，服务等级，最坏情况界，FFD，MULTIFIT分为三章．的．machineis；+({)‘，whereof；+({)。．We2一示b．The2+(j)‘forAbstractjobservice(orprovision．WeMMFMULTIFIT．TheofMMFWords：Parallelsevice，Worst-casemainlyGoS)levels．Eachherconstraintsatisfied．Wem=3andMUl0IFITThisthesisstudiesparallelschedulingundergradeofserviceprovision．EachlabelledwithprespecifiedisallowedbeprocessedbyparticularonlywhentheGoSlevellessthantevelmachine．Thegoaltominimizemaximumcompletiontime，calledmakespan．ThisproblemproposedHwanga1．recently．Forthisproblem，wepresentalgorithm，whichimprovedknownresultconsistsofthreechapters．Thefirstchaptergivessomeintroductionprelimilariesforprob·lems．Thesecondinvestigatesgradessevicealgorithmmodifiedfromratiokdesirednnm—iteration．Thethirdconsidersgeneralconsideration．Themakespanthatallre-areworst—casealgorihtmshowboundiSKeyscheduling，Graderatio，FFDnewtwoworstcasequestsfurthertightIIaetnocasean第一章绪论1．1排序问题fh：仇个变速机．processors)．流水作业、开放作业、异顺序作业和柔性流水作业的具排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题．由于它在现实计算机系统中多方面的应用，排序问题早已成为理论计算机学界的研究领域之一，并已拥有大量结果．除了在计算机科学领域以外，排序问题还在管理科学和工程技术等诸多方面具有大量的应用．近几十年来，排序问题得到了运筹学界、计算机科学界、工程学界和管理学界极大的关注，鉴于经典问题的研究日益深入，而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入成熟期，按照学术界多年来形成的惯例，一般用所谓的三参数表示法(three—fieldrepresentation妞／卢／7来表示一个具体的排序问题，三个参数＆，p和，y分别刻画了机器状况，工件特征和目标函数，一卜-面我们分别对每个参数所代表的含义作具体介Q域表示处理机的数量、类型和环境，它可以为l：单处理机Pm：仇个同速机．Qm：m个恒速机．Fm：m个处理机，流水作业．Om：m个处理机，开放作业．Jra：m个处理机，异顺序作业．FFs：s类处理机，柔性流水作业．其中同速机、恒速机和变速机这三种机器状况的具体含义如下：如果所有的处理机都具有相同的速度，称之为同速机(identicalprocessors)；如果处理机的速度不同，但是每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速机(uniformpr