Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach
Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach
复制标题
多桥加工系统的无碰撞调度：基于彩色旅行商问题的方法
DOI：
10.1109/jas.2017.7510415
复制
发表时间：
2018-01-01
影响因子：
11.8
通讯作者：
Dai, Xing
中科院分区：
文献类型：
--
作者：
Li, Jun;Meng, Xianghu;Dai, Xing
多桥加工系统（MBMS）因其高生产能力和高效率而在工业中获得了广泛的应用。它们包含多个在部分重叠的工作空间内并行工作的桥接机器。他们的调度问题可以抽象为一个系列颜色的旅行推销员问题，其中每个推销员都有一些专有的城市和一些与其邻居共享的城市。为了解决这个问题，我们开发了一种贪心算法来选择满足邻近度的邻近城市。该算法允许推销员随机选择其共享城市并相应地运行多次。因此它可以用来解决 MBMS 的作业调度问题。随后，提出了一种无冲突调度方法来解决MBMS的作业调度和冲突解决问题。它是贪婪算法的扩展，引入了时间窗口约束和冲突解决机制。因此，增强贪婪算法可以尽力为单个机器逐步选择作业，使其与相应重叠工作空间中处理的相邻机器的作业序列之间不存在时间重叠；仅当不可避免时才删除此类时间重叠。最后，我们应用所提出的方法对大型三桥水射流切割系统进行了案例研究。
Multi-bridge machining systems (MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces. Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triple-bridge waterjet cutting system by applying the proposed method.