Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136883
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling Problem |
Author: | Shi, F. Yan, X. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2022 / Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tusar, T. (ed./s), vol.13399, pp.526-541 |
Publisher: | Springer |
Publisher Place: | Online |
Issue Date: | 2022 |
Series/Report no.: | Lecture Notes in Computer Science; 13399 |
ISBN: | 9783031147203 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (10 Sep 2022 - 14 Sep 2022 : Dortmund, Germany) |
Editor: | Rudolph, G. Kononova, A.V. Aguirre, H. Kerschke, P. Ochoa, G. Tusar, T. |
Statement of Responsibility: | Feng Shi, Xiankun Yan, Frank Neumann |
Abstract: | 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. |
Keywords: | Chance-constraint; Makespan scheduling problem; RLS; (1 + 1) EA |
Rights: | © 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG |
DOI: | 10.1007/978-3-031-14721-0_37 |
Grant ID: | http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://link.springer.com/book/10.1007/978-3-031-14721-0 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.