CAJ | 학술논문

本文研究一类并行工件平行机在线排序问题。给定2台平行机和一组按列表到达的并行工件，对每一到达的工件进行机器指派和确定开工时间，使得机器完工时间的lp范数最小。本文首先分析了LS算法的竞争比，其值为2；其次证明了任何在线算法的竞争比不小于4/3。
본문연구일류병행공건평행궤재선배서문제。급정2태평행궤화일조안렬표도체적병행공건，대매일도체적공건진행궤기지파화학정개공시간，사득궤기완공시간적lp범수최소。본문수선분석료LS산법적경쟁비，기치위2；기차증명료임하재선산법적경쟁비불소우4/3。
We study the online scheduling problem of parallel jobs. Parallel jobs means it may require a number of ma-chines at the same time. Given two identical machines and a job sequence arrive over list,we need to assign the arrival jobs to some machines and determine its starting time such that the lp norm of the machine completion time vector is minimized. We ifrst proof that the performance ratio of the classic LS algorithm is two,then we show that the competitive ratio is at least 4/3 for any online scheduling algorithm.