并行分批排序综述  

A Review of Parallel Batch Scheduling

作　　者：井彩霞 吴瑞强 贾兆红[3] JING Cai-xia;WU Rui-qiang;JIA Zhao-hong(School of Economics and Management,Tiangong University,Tianjin 300387,China;Research and Development Center,Tianjin Dawning Storage Technology Limited Company,Tianjin 300384,China;School of Computer Science and Technology,Anhui University,Hefei 230601,China)

机构地区：[1]天津工业大学经济与管理学院,天津300387 [2]天津曙光存储科技有限公司存储产品研发部,天津300384 [3]安徽大学计算机科学与技术学院,安徽合肥230601

出　　处：《运筹与管理》2020年第1期223-239,共17页Operations Research and Management Science

基　　金：天津市高等学校创新团队培养计划(TD13-5038);国家自然科学基金(71971002);教育部青年基金资助项目(15YJC630041);安徽省自然科学基金资助项目(1608085MG154)。

摘　　要：并行分批排序起源于半导体芯片制造过程.在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时.首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向.Parallel batch scheduling arises from semiconductor manufacturing.In this type of scheduling,jobs are processed in batch and the batch processing machine is capable of processing up to B jobs simultaneously as a batch.The processing time of a batch is equal to the longest processing time of the jobs in the batch.Firstly,achievements of parallel batch scheduling with different traditional machine environments and objective functions are introduced,where machine environments mainly refer to single machine and parallel machines,and objective functions are makespan,total completion time,maximum lateness,number of tardy jobs,total tardiness and maximum tardiness;then 16 new problems derived from general problems by combining with new characteristics are classified,and they are parallel batch scheduling problems with non-identical job sizes,problems with multi-objectives or new objectives,problems subject to precedence constraints,problems with transportation time,discretely controllable processing time,deteriorating jobs,learning effect,forbidden intervals,due windows,energy consumption consideration,rejection,bathing cost,job processing time compatibilities,two-agent,rescheduling and semi-continuous respectively;and research directions of parallel batch scheduling in the future are looked forward to at last.

关 键 词：并行分批排序 时间复杂性 启发式算法 智能算法 近似算法 综述 

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