A Polynomial Algorithm for 2-Cyclic Robotic Scheduling
A Polynomial Algorithm for 2-Cyclic Robotic Scheduling
复制标题
DOI：
10.1007/11925231_41
复制
发表时间：
2006-11
期刊：
影响因子：
--
通讯作者：
V. Kats;E. Levner
中科院分区：
文献类型：
--
作者：
V. Kats;E. Levner
我们解决了由计算机控制的机器人服务的柔性制造系统中出现的单机器人-机器循环调度问题。问题是找到所谓的2-循环（或“2度”）计划的最小周期时间，在每个周期中，正好有两个零件进入生产线，两个零件离开生产线。一个较早的已知的多项式时间算法，这个问题是只适用于欧几里德的情况下，运输时间必须满足“三角不等式”。在本文中，我们研究了一般的非欧几里德情况。应用几何方法，我们构造了一个复杂度为O（m5 logm）的多项式时间算法.
We solve a single-robotm-machine cyclic scheduling problem arising in flexible manufacturing systems served by computer-controlled robots. The problem is to find the minimum cycle time for the so-called 2-cyclic (or “2-degree”) schedules, in which exactly two parts enter and two parts leave the production line during each cycle. An earlier known polynomial time algorithm for this problem was applicable only to the Euclidean case, where the transportation times must satisfy the “triangle inequality”. In this paper we study a general non-Euclidean case. Applying a geometrical approach, we construct a polynomial time algorithm of complexity O(m5logm).