改进的混合算法求解车间作业调度问题

车间作业调度问题是个典型的NP-hard问题,为了更有效的解决车间作业调度问题,提出了一种改进的混合算法(IGASA).算法设计了一种基于当前最优解的免疫算子,算子对当前最优个体中选取运行时间最少的一台机器上的工件顺序当作疫苗,并用车间调度问题的图论模型解释了此算子的合理性.最后通过大量实验证明改进的混合算法的性能的优越性,从而证明设计的免疫算子是有意义的.

An Improved Hybrid Algorithm for Job Shop Scheduling

Job shop Scheduling problem is a typical NP-hard Problem.To solve the job-shop scheduling problem more effectively,an improved hybrid algorithm(IGASA) was presented. An immune operator based on the current best solution was designed in this paper.The operator selected the work sequence of the machine whose running time of at least from the current best individual as the vaccine and the reasonableness of this operator was explained by the graph model of the Job shop Scheduling problem.The computer simulations are made on a set of benchmark problems and the results show the effectiveness of the proposed algorithm,through which the immune operator designed in this paper can been proved meaningful.