论文标题
电缆树接线 - 在现实世界调度问题上的基准测试求解器以及各种优先限制
Cable Tree Wiring -- Benchmarking Solvers on a Real-World Scheduling Problem with a Variety of Precedence Constraints
论文作者
论文摘要
电缆树用于工业产品中，以在不同产品零件之间传输能源和信息。到目前为止，它们主要由人类组装，只有少数使用复杂的机器人机器的自动化解决方案。对于这些机器，必须将接线计划转换为电缆插头操作的接线序列，然后将其换成机器。在本文中，我们研究并正式化了针对电缆树的给定布局得出最佳接线序列的问题。我们总结了我们的调查，以将该电缆树接线问题（CTW）建模为旅行推销员问题，这些问题是原子，软性原子和脱节的优先限制，以及依赖旅游的优势成本，因此可以通过最新的约束程序（CP），优化的Modulo Theeories（Ompulo Theeorizy Theeories（OMT）和Comply-Conter-Integer（Mip）（MIP）（MIPS）求解。进一步显示，如何将CTW问题视为耦合任务调度问题的软版本。我们讨论了有关该问题的各种建模变体，证明其NP硬度，并在278个实例的基准集上与经验比较CP，OMT和MIP求解器。具有所有模型和实例数据的完整基准设置可在GitHub上获得，并被接受以包含在Minizinc Challenge 2020中。
Cable trees are used in industrial products to transmit energy and information between different product parts. To this date, they are mostly assembled by humans and only few automated manufacturing solutions exist using complex robotic machines. For these machines, the wiring plan has to be translated into a wiring sequence of cable plugging operations to be followed by the machine. In this paper, we study and formalize the problem of deriving the optimal wiring sequence for a given layout of a cable tree. We summarize our investigations to model this cable tree wiring Problem (CTW) as a traveling salesman problem with atomic, soft atomic, and disjunctive precedence constraints as well as tour-dependent edge costs such that it can be solved by state-of-the-art constraint programming (CP), Optimization Modulo Theories (OMT), and mixed-integer programming (MIP) solvers. It is further shown, how the CTW problem can be viewed as a soft version of the coupled tasks scheduling problem. We discuss various modeling variants for the problem, prove its NP-hardness, and empirically compare CP, OMT, and MIP solvers on a benchmark set of 278 instances. The complete benchmark set with all models and instance data is available on github and is accepted for inclusion in the MiniZinc challenge 2020.
