【平行机排序问题的近似算法】.pdf
Approximation Algorithms on Parallel Machines Scheduling(PH.D.DISSERTATION) He Yong Department of Applied Mathematics,ZhejiangUniversity October,1996
浙江大学博士学位论文 摘要 本文主要研究平行机排序问题的近似算法的设计和分析。在假定工件相 互独立,工件零时刻可加工,加工不可中断总前提下,就不同的平行机环境,不 的有效算法。全文共分七章。第二至第六章为主要部分.第二章研究P,r:C问题。首先指出在两种情况下LPT算法的最坏情 况界会变小。接着讨论Lee提出的修正LPT算法一一MLPT算法,证明了当,回答了Lee的猜想。通过分析另一个修正LPT算法 一MLPT1的最坏情况界,阐明了从最坏情况角度看,MLPT算法是已有原 始贪婪算法中最好的.第三章研究P2,r:Cmar问题,着重设计和分析它的对偶算法。
浙江大学博士学位论文 Thethesisisendedbysomediscussions.Keywords:parallelmachines scheduing,approximation algorithm,worst caseanalysis,dualapproach.