同型机在线调度问题研究进展  

Online scheduling on identical parallel machines

作　　者：刘晓东[1] 陈英武[1] 龙运军[1] 贺仁杰[1] 李菊芳[1] 

机构地区：[1]国防科技大学信息系统与管理学院,湖南长沙410073

出　　处：《计算机集成制造系统》2012年第3期513-522,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(70601035;70801062)~~

摘　　要：为了阐明在线调度的概念及其与在线算法的关系,为相关研究提供支持,对同型机在线调度问题的研究现状进行综述。描述了同型机在线调度问题的概念,以加工约束和目标函数为标准,对同型机在线调度问题进行分类。从基本模型、允许拒绝工件以及考虑机器适用约束等角度对逐个调度工件类在线调度问题进行回顾,从极小化最大完工时间、极小化加权完工时间和以及极大化加权按期完工工件数等角度对工件随时间到达类在线调度问题进行总结,指出了现有研究的不足,并探讨了同型机在线调度问题的未来研究方向。To illustrate the concept of online scheduling and the relationship between online scheduling and online al- gorithm, 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 functiorL 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 o- ver 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 fur- ther research directions of different variants identical parallel machine online scheduling problems were investigated.

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

分 类 号：O223[理学—运筹学与控制论]