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

摘要： 为了阐明在线调度的概念及其与在线算法的关系，为相关研究提供支持，对同型机在线调度问题的研究现状进行综述。描述了同型机在线调度问题的概念，以加工约束和目标函数为标准，对同型机在线调度问题进行分类。 从基本模型、允许拒绝工件以及考虑机器适用约束等角度对逐个调度工件类在线调度问题进行回顾，从极小化最大完工时间、极小化加权完工时间和以及极大化加权按期完工工件数等角度对工件随时间到达类在线调度问题进行总结，指出了现有研究的不足，并探讨了同型机在线调度问题的未来研究方向。

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