A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem

作者：Jamili Amin^*; Shafia Mohammad Ali; Tavakkoli Moghaddam Reza

来源：International Journal of Advanced Manufacturing Technology, 2011, 54(1-4): 309-322.

DOI：10.1007/s00170-010-2932-8

• Periodic job shop scheduling
• Periodic event scheduling problem
• Particle swarm optimization
• Simulated annealing

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP.

• 出版日期2011-4