Several variants of simulated annealing hyper-heuristic for a single-machine scheduling with two-scenario-based dependent processing times
| Autor: | Jia-Cheng Lin, Danyu Bai, Chin-Chia Wu, Shuenn-Ren Cheng, Lining Xing, Juin-Han Chen, Win-Chin Lin |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
Scenario based Single-machine scheduling General Computer Science Computer science General Mathematics 05 social sciences 050301 education 02 engineering and technology Upper and lower bounds Simulated annealing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Pairwise comparison Hyper-heuristic Heuristics 0503 education Working environment |
| Zdroj: | Swarm and Evolutionary Computation. 60:100765 |
| ISSN: | 2210-6502 |
| Popis: | 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 two-scenario-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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect