Abstract: For job-shop scheduling problem with processing flexibility, a new method based on OR-subgraph and sub-routine is proposed to describe processing flexibility. The proposed method is simple in form and permits OR-subgraph to be embedded into one another. Based on this describing method, a genetic algorithm based approach for job-shop scheduling with processing flexibility is presented, which employs a code strategy of combining OR codes, machine codes and schedule codes, and OR codes generate randomly by the maximum quantity of sub-routines and machine codes randomly by the maximum quantity of machines. These code strategies are more conductive to the operations of the crossover and mutation operators which can avoid the unreasonable solution. Several experiments have been used to test the effectiveness of the proposed approach which can provide promising results for this problem.

Key words: job-shop scheduling, genetic algorithm, processing flexibility

摘要： 针对具有工艺路径柔性的车间调度问题,提出基于OR子图和子路径的工艺路径柔性描述方法,该描述方法形式简单且允许OR子图多层嵌套。以此为基础,设计了基于遗传算法的工艺路径柔性调度算法,并采用以工艺路径编码、机器编码和工件调度编码为基础的三维染色体编码策略,其中,工艺路径编码和机器编码分别通过最大子路径数量和最大机器数量随机产生,其优势在于任意染色体均表示可行解,并可以使用简单的交叉算子和变异算子实现遗传操作且其后代亦为可行解。最后通过实验证明了算法的优化能力。

关键词: 车间调度, 遗传算法, 工艺路径柔性