计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2015年
10期
26-29
,共4页
排序%并行工件%在线算法%竞争比
排序%併行工件%在線算法%競爭比
배서%병행공건%재선산법%경쟁비
scheduling%parallel job%online algorithm%competitive ratio
与经典的排序问题不同的是，并行工件排序指的是在加工某些工件时，需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标，而竞争比的下界则是算法设计的一个重要参考。利用反证法，通过构造一个特殊的反例，分析了由此产生的全部9种可能的情形，建立了它们对应的9种线性规划模型，借助计算软件证明了前8种情形是不可能的，然后详细分析了第9种情形也是不可能的，从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。
與經典的排序問題不同的是，併行工件排序指的是在加工某些工件時，需要多箇機器同時併行工作。競爭比是評價在線算法好壞的一箇重要指標，而競爭比的下界則是算法設計的一箇重要參攷。利用反證法，通過構造一箇特殊的反例，分析瞭由此產生的全部9種可能的情形，建立瞭它們對應的9種線性規劃模型，藉助計算軟件證明瞭前8種情形是不可能的，然後詳細分析瞭第9種情形也是不可能的，從而給齣瞭三檯機併行工件排序問題的競爭比的一箇改進的下界2.07。這箇結果優于已知的最好的下界1.999。
여경전적배서문제불동적시，병행공건배서지적시재가공모사공건시，수요다개궤기동시병행공작。경쟁비시평개재선산법호배적일개중요지표，이경쟁비적하계칙시산법설계적일개중요삼고。이용반증법，통과구조일개특수적반례，분석료유차산생적전부9충가능적정형，건립료타문대응적9충선성규화모형，차조계산연건증명료전8충정형시불가능적，연후상세분석료제9충정형야시불가능적，종이급출료삼태궤병행공건배서문제적경쟁비적일개개진적하계2.07。저개결과우우이지적최호적하계1.999。
The online scheduling of parallel jobs on parallel machines is considered in this paper. Contrary to classical parallel machine scheduling problems, jobs may require processing on several machines in parallel. The standard metric for worst-case performance is the competitive ratio. By constructing certain adversary sequence, all the nine kinds of cases are analyzed. It is shown that 2.07 is a new lower bound on the competitive ratio of any online algorithm, which is better than the previous lower bound of 1.999.
