并行分批排序问题综述  

Parallel Batch Scheduling:A Survey

作　　者：张玉忠[1] 曹志刚[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,日照山东276826

出　　处：《数学进展》2008年第4期392-408,共17页Advances in Mathematics（China）

基　　金：国家自然科学基金(NO．10671108);山东省自然科学基金(NO．Y2005A04)资助．

摘　　要：并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序问题的最新进展作了全面的介绍,指出了许多尚未解决的问题和许多新的研究方向,给出了丰富的参考文献,旨在把感兴趣的读者迅速带到此研究领域的前沿.Parallel batch scheduling is a new kind of scheduling which came into our attention in the early 90s last century. Batch scheduling arises in the semiconductor industry and has various applications; On the other hand, it generalizes the classical scheduling model by breaking the constraint that one machine can merely process one job at any time. Due to the two reasons stated above, batch scheduling is gaining more and more attention recently and new results are welling up. In this paper, we present an overall survey on batch scheduling in three aspects： the off-line model, the model with non-identical job sizes and the on-line model. We propose many open problems and brandnew sub-fields deserving further research and abundant references are provided as well aiming to take the interested readers rapidly to the research frontier.

关 键 词：并行分批排序 NP-困难 近似算法 

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