两台同类机极大化机器最小负载问题的分析.pdf

摘要 摘要 本论文研究两台同类机极大化机器最小负载的排序问题。模型要求在两台 速度之比为q的机器上加工工件，并已知工件加工时不可中断，目标是使负载 最小的机器其加工时间最大化。本文分析了用己尸T算法解离线模型的最坏情况 界，给出了证明最坏情况界是紧的实例。其次，针对已知工件从大到小到达的 半在线模型，本文根据L竹算法在口的某些区间段达不到问题下界的情况，设 计了最优算法，并证明了算法的竞争比。其中最坏情况界和竞争比都表示为参 数q的分段函数。最后，针对处于不同区间段上的g，分别给出以q为函数的实 例来说明半在线问题的下界，从竞争比的角度证明了算法的最优性。全文共 分为三章，第一章介绍了论文用到的排序知识和相关研究结果；第二章介绍 了L刀算法最坏情况界的证明思路和具体证明过程；第三章介绍了最优算法的 证明过程和问题的下界。 关键词：同类机，加工时间，三PT算法，最坏情况界，竞争比，下界 Abstract Abstract Thisthesis the maximizationontwounifonilma·· study non—preemptive problem onemachineis as chines，where timesefficientoneachtaskasisthe the q other,with of the theworse-caseratioof goalmaximizingmakespan．We LPT。 analyze Algorithm and instanceto the ofthe thesemi—online give provetightnessratio．Secondly,westudy arriveoneoneintheorderof version：jobs sizes．We by non—increasingdesignoptimal intheintervalswhere LPT isnotthe algorithms Algorithm one，and optimal prove the ratioofthe worse-caseratioandthe ratio competitive algorithms．The competitive ale as functionsof which asfunctionsof givenpiecewise last，instances q．At express ale to the q given lowerboundsofthe includesthree