An Improved Gravitational Search Algorithm to the Hybrid Flowshop with Unrelated Parallel Machines Scheduling Problem

The hybrid flowshop scheduling problem with unrelated parallel machines exists in many industrial manufacturers, which is an NP-hard combinatorial optimization problem. To solve this problem more effectively, an improved gravitational search (IGS) algorithm is proposed which combines three strategies: generate new individuals using the mutation strategy of the standard differential evolution (DE) algorithm and preserve the optimal solution via a greedy strategy; substitute the exponential gravitational constant of the standard gravitational search (GS) algorithm with a linear function; improve the velocity update formula of the standard GS algorithm by mixing a adaptive weight and the global search strategy of the standard particle swarm optimization (PSO) algorithm. Benchmark examples are solved to demonstrate the proposed IGS algorithm is superior to the standard genetic algorithm, DE, GS, DE with local search, estimation of distribution algorithm and artificial bee colony algorithms. Two more examples from a real-world water-meter manufacturing enterprise are effectively solved.