期刊
PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XVII, PPSN 2022, PT II
卷 13399, 期 -, 页码 526-541出版社
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-031-14721-0_37
关键词
Chance-constraint; Makespan scheduling problem; RLS; (1+1) EA
资金
- National Natural Science Foundation of China [62072476, 61872048]
- Hunan Provincial Natural Science Foundation of China [2021JJ40791]
- Australian Research Council (ARC) [FT200100536]
This paper investigates a chance-constrained version of the Makespan Scheduling problem and analyzes the performance of two algorithms. The processing times of jobs in real life scenarios are often stochastic and may be influenced by external factors.
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 an expected value with a variance under the influence of external factors, and these actual processing times may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the performance of Randomized Local Search and (1 + 1) EA for it. More specifically, we study two variants of the Chance-constrained Makespan Scheduling problem and analyze the expected runtime of the two algorithms to obtain an optimal or almost optimal solution to the instances of the two variants.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据