Journal
SWARM AND EVOLUTIONARY COMPUTATION
Volume 60, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.swevo.2020.100765
Keywords
Two-scenario-based dependent processing times; Simulated annealing hyper-heuristic; Low level heuristics
Funding
- Ministry of Science and Technology of Taiwan [MOST 109-2410-H-035-019, MOST 105-2221-E-035-053-MY3]
- National Natural Science Foundation of China [61873173]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available