并行分批排序综述

A Review of Parallel Batch Scheduling

并行分批排序起源于半导体芯片制造过程.在并行分批排序中,工件可成批加工,批加工机器最多可同时加工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.