Abstract:
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.