基于遗传算法的作业车间双向调度优化问题

A Bi-directional Scheduling Optimization of Job-shop Using Genetic Algorithms

提出了一种基于混合遗传算法的双向调度算法 ,用来解决以关键工件交货期和生产周期为优化目标的作业车间调度问题。在算法中 ,遗传算法在全局范围内搜索最优调度染色体 ,双向调度算法根据得到的染色体进行调度。按照订单的要求 ,作业车间的工件可分为两类 ,即关键工件和一般工件。因此 ,车间调度也可分为前向调度和反向调度两个步骤 ,对于关键工件 ,采用反向调度 ,尽可能地满足交货期的要求 ;对于一般工件 ,采用前向调度 ,利用剩余的车间资源 ,尽可能早完工。仿真结果表明该算法是可行的 ,与传统的调度算法相比 。

This work presents a bi-directional scheduling approach on the basis of combining genetic algorithm to address the reduction of makespan with the critical job's tardiness, in which the combining genetic algorithm derives the optimal operations precedence to schedule the operations in the bi-directional scheduling approach. In job shop, the unscheduled jobs can be portioned into two groups: (1) those with firm due dates (i.e. critical jobs) and (2) those with negotiable due dates. So, we turn the scheduling algorithm into two steps. In the first step, the critical jobs must be scheduled by using the backward algorithm. This step ensures that the necessary resources are allocated to the most important jobs. The second step schedules the remaining jobs with a forward algorithm, which tends to allocate resources where the previous scheduling pass did not use them.An example of scheduling is given, which proves this method is feasible and efficient.