关键词: 调度, 在线算法, 竞争比分析, 下界, 同型机

Abstract: To illustrate the concept of online scheduling and the relationship between online scheduling and online algorithm, the research status of parallel machine　s online scheduling was discussed. The concept of online identical parallel machine scheduling problem was introduced, and classification was made according to machining constraint and objective function. The online scheduling problem of scheduling jobs one by one was reviewed by considering basic model, allowable refusal workpieces and applicable constraint. The online scheduling problem of job arrive over time was summarized through perspective of minimizing total makspan, minimizing total weighted completion time and maximizing weighted completion time. Thus the deficiencies of existing research were found, and the further research directions of different variants identical parallel machine online scheduling problems were investigated.

Key words: scheduling, online algorithms, competitive analysis, lower bound, identical parallel machines