求解作业车间调度问题的一种改进遗传算法

An Improved Genetic Algorithm for Job-shop Scheduling Problem

为了避免遗传算法的早熟收敛问题,降低算法对初始种群的敏感程度,提高收敛速度,建立了以工件完工时间最小和加工设备利用率最高为目标的数学模型,并提出一种改进遗传算法。在约束条件处理中引入可能解空间概念;设计了适应路径柔性调度问题的基于工序的编码。父代个体和交叉变异得到的个体在选择操作中具有同等选择机会,保证最优个体保留到下一代,又能保持子代的多样性。在遗传过程中引入修正种群,实现多种群杂交,以保持种群的多样性。应用实例分析和工程实践表明,算法稳定可靠,运行效率大大提高。

In order to avoid premature convergent problem,lower algorithm＇s sensitivity to original population,improve convergent speed,build job-shop scheduling problem＇s mathematics model whose target is reducing work pieces＇ make span and improving machining device＇s utilization rate,put forward an improved genetic algorithm.Introduce a concept of possible solution domain in restriction condition treatment;design working procedure based coding suitable for route flexible scheduling problem.Father individual and all the individuals derived from crossover and mutation have the same selection opportunity in selection operation to ensure the best individual coming into next generation and keep filial generation＇s diversification.In genetic processing,introduce correctional populatlon,reallze multi-population cross in order to keep population＇s diversification.Application example analysis and engineering practice indicate that this improved genetic algorithm is very stable and credible and its running efficiency has been greatly improved.