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).
翻译:我们处理的是一个具有挑战性的平行机器的时间安排问题,其时间和排放日期取决于序列设置的时间,来自半导体工作车间生产的实际应用。在那里,工作只能由专用机器处理,因此很少有机器能够几乎决定制造过程,而不管其余的机器如何安排工作。这在机器故障和工作需要重新安排时造成问题。我们不只优化制造过程,而是将单个机器的跨度置于非自动排列顺序和从字典上将由此产生的图例最小化。这样可以使所有机器都尽早完成并增加时间表的稳健性。我们研究应用问答程序(ASP)来解决这个问题。虽然ASP可以简化建模,同时将时间限制和考虑的客观功能结合起来,对目前的解决技术提出了挑战。前一个问题是通过差异逻辑扩展ASP来解决的。对于后者,我们设计了不同的算法,用多光谱解。为了处理工业规模的实例,我们研究了不同的近似和超光谱。我们的实验结果表明,ASP确实是一个很有前途的KRRP范式模型,而MTP在解决该问题和逻辑化过程中是竞争性的。