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.
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.