A hybridization of simulated annealing and electromagnetism-like mechanism for a periodic job shop scheduling problem

摘要

In this paper, we present on a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP), which is different from cyclic scheduling. The PESP schedules a number of recurring events, such that each pair of events fulfills certain constraints during a given time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely EM-SA, which is based on electromagnetism-like mechanism (EM) and simulated annealing (SA). To evaluate this proposed EM-SA, some randomly constructed instances are solved, and the related results are compared with SA and optimum solutions obtained by the branch-and-bound (B&B) algorithm. The results demonstrate the efficiency and effectiveness of the proposed hybrid EM-SA algorithm to solve the PJSSP.