Solve job shop scheduling problem with sequence dependent setup times using a simulated annealing algorithm with different neighborhood search structure

Adel Abdelmoez Ibrahim, Mohamed Ramadan Mansour, Mohammad Mahmoud Hamed, Mohamed Adel Elbaz


This paper examines job shop scheduling problems with sequence dependent setup
times under objective function minimization of makespan (JSSP/SDST/Cmax). An
effective meta-heuristic, simulated annealing is developed to potentially solve the
problem. Simulated annealing is a well-recognized algorithm and historically
classified as a local-search-based meta-heuristic. The performance of the simulated
annealing critically depends on its operators and parameters. The proposed
algorithm to an effective meta-heuristic simulated annealing with novel operators to
potentially solve the problem. In this paper, proposed Simulated Annealing an
effective neighborhood search structure based on insertion neighborhoods as well
as analyzing the behavior of simulated annealing with different types of operators
and parameters. The results showed that the proposed Simulated Annealing PSA
algorithm gives less makespan value and CPU time with different problem size
taken from the OR- library compared to previous well known SA algorithm. It note
when changed in some factors with proposed NS the makespan change for the
better. In independent setup times it compared the result with the solution from
OR- library, have been results indicated the proposed simulated annealing
algorithm near from best solution, with medium and large problems, and in small
problems given best solution. It can say when the No. of temperatures between T0
and Tf increases with the proposed neighbors will improve the solution, but not


  • There are currently no refbacks.