There are two phases to the proposed MTSA algorithm procedure: the initialisation phase and the iteration phase.

Technology Overview
To improve the algorithm’s performance, this study proposed an effective and efficient multi-temperature simulated annealing (MTSA) algorithm. The proposed MTSA algorithm combines the advantages of the basic SA algorithm for effectively achieving search convergence with that of the multi-temperature method for escaping local optimality.

Applications & Benefits
The experimental and statistical results obtained in this study showed that MTSA outperformed the state-of-the-art meta-heuristic algorithms in the literature, and confirmed the effectiveness and robustness of the proposed lower bound. Due to the universality and extreme complexity of the J_m|h_jk|C_max problem, this work eliminates the gap between practical applications and scheduling theory by providing an effective and efficient algorithm for making realistic scheduling decisions.

Abstract：
This paper proposes an effective and efficient multi-temperature simulated annealing (MTSA) algorithm to minimise the makespan of a job-shop under the constraint that machines are not continuously available for processing during the whole scheduling horizon. The proposed MTSA algorithm uses an embedded multi-temperature mechanism to vary the thermal transition probabilities of the simulated annealing algorithm. This mechanism can help prevent the algorithm from becoming trapped in a local minimum and ensures its movement towards a broad region of the search space containing optimal solutions. An effective and robust lower bound is developed for the problem to evaluate the quality of solutions. Extensive computational results show that the proposed MTSA algorithm significantly outperforms the state-of-the-art meta-heuristic algorithms reported in the literature. The proposed algorithm and lower bound can assist further research in the scheduling research field as it is both effective and efficient in handling job-shop scheduling problems with machine availability constraints.

Minimising makespan in job-shops with deterministic machine availability constraints
Author：Shih-Wei Lin, Kuo-Ching Ying
Year：2022
Source publication：International Journal of Production Research Volume 59, Issue 14, Pages 4403 - 4415
Subfield Highest percentage：99%    Management Science and Operations Research   #2/184

https://www.tandfonline.com/doi/full/10.1080/00207543.2020.1764125