Current studentsExisting staffContact us
 

On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling

Simple item page
dc.contributor.authorNeumann, F.
dc.contributor.authorWitt, C.
dc.contributor.conference24th International Joint Conference on Artificial Intelligence (IJCAI 2015) (25 Jul 2015 - 31 Jul 2015 : Buenos Aires, Argentina)
dc.contributor.editorYang, Q.
dc.contributor.editorWooldridge, M.
dc.date.issued2015
dc.description.abstractEvolutionary algorithms have been frequently used for dynamic optimization problems. With this paper, we contribute to the theoretical understanding of this research area. We present the first computational complexity analysis of evolutionary algorithms for a dynamic variant of a classical combinatorial optimization problem, namely makespan scheduling. We study the model of a strong adversary which is allowed to change one job at regular intervals. Furthermore, we investigate the setting of random changes. Our results show that randomized local search and a simple evolutionary algorithm are very effective in dynamically tracking changes made to the problem instance.
dc.description.statementofresponsibilityFrank Neumann and Carsten Witt
dc.identifier.citationIJCAI : proceedings of the conference / sponsored by the International Joint Conferences on Artificial Intelligence, 2015 / Yang, Q., Wooldridge, M. (ed./s), vol.2015-January, pp.3742-3748
dc.identifier.isbn9781577357384
dc.identifier.issn1045-0823
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/109197
dc.language.isoen
dc.publisherAAAI Press
dc.relation.granthttp://purl.org/au-research/grants/arc/DP130104395
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400
dc.rightsCopyright © 2015 International Joint Conferences on Artificial Intelligence All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.
dc.source.urihttp://www.ijcai.org/Abstract/15/526
dc.titleOn the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
RA_hdl_109197.pdf
Size:
307.58 KB
Format:
Adobe Portable Document Format
Description:
Restricted Access
Download

Collections

Computer Science publications