Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling
Institute of Logic and Computation, Vienna University of Technology, Wien, Austria.ORCID iD: 0000-0001-6003-6345
Institute of Logic and Computation, Vienna University of Technology, Wien, Austria.ORCID iD: 0000-0002-0856-7162
Institute of Logic and Computation, Vienna University of Technology, Wien, Austria.
Institute of Logic and Computation, Vienna University of Technology, Wien, Austria.ORCID iD: 0000-0002-9902-7662
Show others and affiliations
2023 (English)In: Theory and Practice of Logic Programming, ISSN 1471-0684, E-ISSN 1475-3081, Vol. 23, no 6, p. 1281-1306Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Cambridge University Press, 2023. Vol. 23, no 6, p. 1281-1306
Keywords [en]
answer-set programming, parallel machine scheduling, lexicographical optimisation
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hj:diva-63645DOI: 10.1017/s1471068423000017ISI: 000920784500001OAI: oai:DiVA.org:hj-63645DiVA, id: diva2:1839467
Available from: 2024-02-21 Created: 2024-02-21 Last updated: 2024-02-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Oetsch, Johannes

Search in DiVA

By author/editor
Eiter, ThomasGeibinger, TobiasOetsch, Johannes
In the same journal
Theory and Practice of Logic Programming
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf