基于一种遗传邻域万有引力算法的作业车间调度

A Novel GA-LS-GS Algorithm to Job Shop Scheduling Problem

作业车间调度问题属于NP-hard问题,是离散生产制造中广泛存在的一类组合优化问题。针对此问题,提出了一种新型遗传邻域万有引力算法。该算法借鉴万有引力搜索算法中惯性质量和欧氏距离的概念,提出了候选父代染色体个数的选择方法和染色体差距的计算方法,并以此定义了一种新的交叉策略;同时混合遗传算法与N5邻域结构,有效地求解了作业车间调度问题。通过对3个FT类和10个LA类标准测试算例的仿真,验证了本文遗传邻域万有引力算法的优越性。采用遗传邻域万有引力算法有效地解决了某水表制造企业中的大规模作业车间调度问题。

As an NP-hard combinatorial optimization scheduling problem, the job shop scheduling problem （JSSP） exists in many discrete industrial manufacturing systems. To solve the JSSP more effectively, a novel GA-LS-GS （genetic algorithm-local search-gravitational search） algorithm is developed. The ＂inertial mass＂ in the standard gravitational search algorithm （GS） is utilized to choose the number of parents＇ chromosomes, and the ＂Euclidean distance＂ in GS computes the difference between every two chromosomes. Based on the two ideas, a new crossover strategy is defined. The detailed steps of the GA-LS-GS algorithm are arranged in the way of a genetic algorithm （GA） and listed as followed：（1） Encode the JSSP by operation order-based encoding method, and initialize the population; （2） Select the parent chromosomes according to ＂inertial mass＂; （3） Embed the new crossover operation using the new crossover strategy; （4） Mutate the population by three policies：inversion, swap and shift; （5） Combine the N5 neighborhood structure to perform the local search; （6） Decode the population by active scheduling method and evaluate the fitness of them; （7） Determine whether the termination condition is reached, and carry out the main cycle or output the optimized result. Benchmark case studies including 3 FT problems and 10 LA cases are tested, and the proposed GA-LS-GS algorithm shows better computing results. Finally, two JSSP examples in a real-world water-meter manufacturing enterprise are effectively solved.