基于改进遗传算法求解柔性作业车间调度问题

摘要

The characteristics of the flexible job shop scheduling problem（FJSP） are analyzed,and an effective chromosome coding method is proposed to improve the genetic algorithm for solving the FJSP.In the genetic algorithm,each chromosome consists of machine chromosome and operation chromosome,denoting path selection and feasibility scheduling respectively,thus forming a scheduling scheme.Each gene of chromosome is encoded by a real number to enhance the efficiency of the encoding.The genetic operator thus designed does not generate illegal solutions when implementing crossover operation and mutation operation.The improved genetic algorithm is tested with an instance taken from the open literature and compared with the test results,which show that the improved genetic algorithm is effective for solving FJSP.%分析了柔性作业车间调度问题的特点,提出一种有效的染色体编码方法,以改进遗传算法求解该问题。在该算法中,每条染色体由机器染色体和工序染色体两部分组成,分别表示路径选择和可行调度,构成一种调度方案。染色体中每一位均采用实数编码提高编码和解码的效率,结合所设计的遗传算子避免非法解的产生。使用实例测试改进的遗传算法,并与其他文献中的测试结果进行比较,验证了该算法的可行性和有效性。