基于DNA进化算法求解工件尺寸不同的单机批调度问题

DNA Evolutionary Algorithm for Scheduling a Single Batch-processing Machine with Non-identical Job Sizes

工件尺寸不同的批调度问题兼具古典调度和批调度的性质,单机环境下该问题的制造跨度为NP完全问题.本文提出一种改进的DNA进化算法对单机问题的制造跨度进行优化,引入分裂、水平选择、变异、垂直选择四种算子,对其中的垂直选择算子做了重新设计,采用概率选择机制对变异个体进行选择,避免进化过程陷入局部最优.在解码时,采用Batch First Fit算法对进化过程产生的解作分批处理.实验中对各类不同规模的算例均进行仿真,结果表明改进的DNA进化算法的有效性.

The problem of batch-processing machines with non-identical job sizes is a combination of classical scheduling and batch scheduling, The makespan on a single batch-processing machine with non-identical job sizes is NP-complete. In this paper DNA Evolutionary Algorithm （DEA） is applied to minimize the makespan on a single machine. Four operators of DEA are adopted in the evolution including division.level selection.mutation and vertical selection. The vertical selection operator was redesigned by using the probability-based mechanism to escape local optimum. The solutions produced by the algorithm were divided into batches with Batch First Fit algorithm. In the experiment, all levels of instances were simulated and the results demonstrated the efficiency of the proposed algorithm.