A hybrid PSO-TS approach for proportionate multiprocessor open shop scheduling

摘要

In this paper, a hybrid particle swarm optimization (PSO)-tabu search (TS) approach is proposed for solving the proportionate multiprocessor open shop scheduling problem (PMOSP) with the objective of minimizing the makespan. The PSO part of the proposed approach is used for randomly searching the machine selection decisions, while the TS part conducts local improvements for the routing and sequencing subproblems. Experimentations are conducted on 100 benchmark problems which are divided into four equal sets with 2, 4, 8 and 16 processing centers. The analysis shows that the proposed hybrid approach produces competitive results compared to previously developed TS and genetic algorithm approaches, especially for intermediate size problems of 4 and 8 processing centers. The average optimality gap of the proposed approach is found to be below 5.6% from the lower bound for the four sets, and ten new upper bounds are found, among them two are provably optimal.