可行批调度问题及其遗传算法

Feasible Batch Scheduling Problem and Its Genetic Algorithm

对判定问题一是否存在使所有需求都可按时满足的调度一进行了研究，通过将其转化成等价的可行批调度问题，分析可行批调度的性质，把问题的解自然表示成了二进制编码的形式，在此基础上，提出了相应的遗传算法，它克服了调度研究中常用的基于排列编码的遗传算法的缺点。

A discrimination problem, i. e., whether there exists a schedule in which all demands can be satisfied in time, is studied. Its equivalent feasible batch scheduling problem (FBSP) is obtained. By analyzing the features of the FBSP, the solutions to the batch scheduling problem(BSP) are represented in binary codes naturally. Based on it, a genetic algorithm, which can overcome the drawback of permutation-based GA that is often used in scheduling, is presented. Computational results show the effectiveness of the algorithm.