A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case
A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case
复制标题
DOI：
10.1016/j.dam.2008.03.025
复制
发表时间：
2009-01
期刊：
影响因子：
--
通讯作者：
V. Kats;E. Levner
中科院分区：
文献类型：
--
作者：
V. Kats;E. Levner
在本文中，我们考虑了多台机器生产线中相同零件的无等待循环调度问题，其中机器人负责将每个零件从一台机器移动到另一台机器。目的是找到所谓的 2 循环计划的最小循环时间，其中每个循环期间恰好有两个零件进入生产线和两个零件离开生产线。早期已知的针对该问题的多项式时间算法仅在机器人行进时间满足三角形不等式的附加假设下才适用。我们对机器人行程时间提出了这一假设，并提出了一种与公制情况具有相同时间复杂度的多项式时间算法，O(m5logm)。
In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m5logm).