Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916704138821632 |
|---|---|
| author | Shi, Feng Huang, Daoyu Yan, Xiankun Neumann, Frank |
| author_facet | Shi, Feng Huang, Daoyu Yan, Xiankun Neumann, Frank |
| contents | The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influence of external factors, and the actual processing times of these jobs may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities, then separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the two variants. In addition, we investigate the experimental performance of the two algorithms for the two variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_11478 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem Shi, Feng Huang, Daoyu Yan, Xiankun Neumann, Frank Neural and Evolutionary Computing The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influence of external factors, and the actual processing times of these jobs may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities, then separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the two variants. In addition, we investigate the experimental performance of the two algorithms for the two variants. |
| title | Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2212.11478 |