Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems

Abstract

This paper presents a neighbourhood generation mechanism for the job shop scheduling problems (JSSPs). In order to obtain a feasible neighbour with the generation mechanism, it is only necessary to generate a permutation of an adjacent pair of operations in a scheduling of the JSSP. If there is no slack time between the adjacent pair of operations that is permuted, then it is proven, through theory and experimentation, that the new neighbour (schedule) generated is feasible. It is demonstrated that the neighbourhood generation mechanism is very efficient and effective in a simulated annealing.

Keywords:

• permutation
• slack time
• fictitious slack time
• infeasible schedule
• feasible schedule

Additional information

Notes on contributors

Marco Antonio Cruz-Chávez

Marco Antonio Cruz-Chávez is a research professor in combinatorial optimization at the Engineering and Applied Science Research Center of the Autonomous University of the State of Morelos, Mexico. His research is on algorithms and complexity problems. He applies his knowledge to the study of resource assignment problems, with application in productive sectors such as industry, transportation and education.