Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling
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 KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers. Under consideration in Theory and Practice of Logic Programming (TPLP).
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Scheduling Parallel Optical Circuit Switches for AI Training
The rapid growth of AI training has dramatically increased datacenter traffic demand and energy consumption, which has motivated renewed interest in optical circuit switches (OCSes) as a high-bandwidth, energy-efficient …
Argumentation for Explainable Workforce Optimisation (with Appendix)
Workforce management is a complex problem involving the optimisation of the makespan and travel distance required for a team of operators to complete a set of jobs, using a set of instruments. A crucial challenge in work…
Workflow Optimization for Parallel Split Learning
Split learning (SL) has been recently proposed as a way to enable resource-constrained devices to train multi-parameter neural networks (NNs) and participate in federated learning (FL). In a nutshell, SL splits the NN mo…
Federated LearningSchedulingAnswer Set Programming Energised! End-to-End Neurosymbolic Reasoning and Learning with ASP and Energy Based Models
We present a general neurosymbolic reasoning and learning methodology based on a modular integration of answer set programming with an energy based model substrate. Key contributions are: (1) supporting joint optimisatio…
Multi-Object TrackingExact and heuristic methods for the discrete parallel machine scheduling location problem
The discrete parallel machine makespan scheduling location (ScheLoc) problem is an integrated combinatorial optimization problem that combines facility location and job scheduling. The problem consists in choosing the lo…
ARCCombinatorial OptimizationScheduling