<div class="csl-bib-body">
<div class="csl-entry">EITER, T., GEIBINGER, T., MUSLIU, N., OETSCH, J., SKOČOVSKÝ, P., & STEPANOVA, D. (2023). Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling. <i>Theory and Practice of Logic Programming</i>, <i>23</i>(6), 1281–1306. https://doi.org/10.1017/S1471068423000017</div>
</div>
-
dc.identifier.issn
1471-0684
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/191696
-
dc.description.abstract
We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of answer-set programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising knowledge representation and reasoning (KRR) paradigm for this problem and is competitive with state-of-the-art constraint programming (CP) and Mixed-Integer Programming (MIP) solvers.
en
dc.language.iso
en
-
dc.publisher
CAMBRIDGE UNIV PRESS
-
dc.relation.ispartof
Theory and Practice of Logic Programming
-
dc.subject
Answer Set Programming
en
dc.subject
Parallel Machine Scheduling
en
dc.subject
Lexicographical Optimisation
en
dc.title
Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling
en
dc.type
Article
en
dc.type
Artikel
de
dc.description.startpage
1281
-
dc.description.endpage
1306
-
dc.type.category
Short/Brief/Rapid Communication
-
tuw.container.volume
23
-
tuw.container.issue
6
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.publication.invited
invited
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
dcterms.isPartOf.title
Theory and Practice of Logic Programming
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publication.orgunit
E192-50 - Services des Instituts
-
tuw.publication.orgunit
E056-13 - Fachbereich LogiCS
-
tuw.publication.orgunit
E056-17 - Fachbereich Trustworthy Autonomous Cyber-Physical Systems
-
tuw.publisher.doi
10.1017/S1471068423000017
-
dc.date.onlinefirst
2023
-
dc.identifier.eissn
1475-3081
-
dc.description.numberOfPages
26
-
tuw.author.orcid
0000-0001-6003-6345
-
tuw.author.orcid
0000-0002-0856-7162
-
tuw.author.orcid
0000-0002-3992-8637
-
tuw.author.orcid
0000-0002-9902-7662
-
wb.sci
true
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
item.grantfulltext
none
-
item.openairecristype
http://purl.org/coar/resource_type/c_6501
-
item.openairetype
journal article
-
crisitem.author.dept
E192 - Institut für Logic and Computation
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence