Several variants of simulated annealing hyper-heuristic for a single-machine scheduling with two-scenario-based dependent processing times

Many practical productions are full of significant uncertainties. For example, the working environment may change, machines may breakdown, workers may become unstable, etc. In such an environment, job processing times should not be fixed numbers. In light of this situation, we investigate a single-machine problem with twoscenario-based processing times, where the goal is to minimize the maximum total completion times over two scenarios. When the uncertainty of the job processing times is confronted, the robust version of this problem is NP-hard, even for very restricted cases. To solve this problem, we derive some dominance rules and a lower bound for developing branch-and-bound algorithms to find optimal solutions. As for determining approximate solutions, we propose five heuristics, adopting combined two-scenario-based dependent processing times, to produce initial solutions and then improve each with a pairwise interchange. Further, we propose a simulated annealing hyper-heuristic incorporating the proposed seven low level heuristics to solve this problem as well. Finally, the performances of all proposed algorithms are tested and reported.

Automated summary

The study focuses on a single-machine problem with scenario-based processing times to minimize maximum total completion times. A robust version of the problem, when faced with uncertainty, is proved to be NP-hard. Dominance rules and a lower bound were derived for developing branch-and-bound algorithms, along with five heuristics and a simulated annealing hyper-heuristic to find optimal and approximate solutions. Performance of proposed algorithms is tested and reported.