Sökning: WFRF:(Musliu Nysret) >
Answer-Set Programm...
Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling
-
- Eiter, Thomas (författare)
- Institute for Logic and Computation, TU Wien, Vienna, Austria
-
- Geibinger, Tobias (författare)
- Institute for Logic and Computation, TU Wien, Vienna, Austria
-
- Musliu, Nysret (författare)
- Institute for Logic and Computation, TU Wien, Vienna, Austria; CD-Lab Artis, TU Wien, Renningen, Germany
-
visa fler...
-
- Oetsch, Johannes (författare)
- Institute for Logic and Computation, TU Wien, Vienna, Austria
-
- Skočovský, Peter (författare)
- Institute for Logic and Computation, TU Wien, Vienna, Austria; Bosch Center for AI, Renningen, Germany
-
- Stepanova, Daria (författare)
- Bosch Center for AI, Renningen, Germany
-
visa färre...
-
(creator_code:org_t)
- IJCAI Organization, 2021
- 2021
- Engelska.
-
Ingår i: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021. - : IJCAI Organization. - 9781956792997 ; , s. 280-290
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- 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 workshop 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 KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Constraint programming
- Answer set programming
- Makespan
- Objective functions
- Optimisations
- Parallel machine
- Parallel machines scheduling
- Real-world
- Scheduling problem
- Sequence dependent setup times and release dates
- Timing constraints
- Job shop scheduling
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas