Combinatorial Optimization: Theory and Algorithms
Combinatorial Optimization: Theory and Algorithms
复制标题
DOI：
10.1007/978-3-662-56039-6
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
B. Korte;J. Vygen
中科院分区：
文献类型：
--
作者：
B. Korte;J. Vygen
让我们从两个例子开始。一家公司有一台在印刷电路板上钻孔的机器。由于它生产许多这样的电路板，它希望机器尽可能快地完成一个电路板。我们无法优化钻孔时间，但我们可以尽量减少机器从一个点移动到另一个点所需的时间。通常钻床可以在两个方向上移动：工作台水平移动，而钻臂垂直移动。由于两个运动可以同时进行，因此将机器从一个位置调整到另一个位置所需的时间与水平和垂直距离的最大值成比例。这通常被称为l∞距离。（旧机器一次只能水平或垂直移动;在这种情况下，调整时间与l1距离成比例，即水平和垂直距离之和。
Let us start with two examples. A company has a machine which drills holes into printed circuit boards. Since it produces many of these boards it wants the machine to complete one board as fast as possible. We cannot optimize the drilling time but we can try to minimize the time the machine needs to move from one point to another. Usually drilling machines can move in two directions: the table moves horizontally while the drilling arm moves vertically. Since both movements can be done simultaneously, the time needed to adjust the machine from one position to another is proportional to the maximum of the horizontal and the vertical distance. This is often called the l∞-distance.(Older machines can only move either horizontally or vertically at a time; in this case the adjusting time is proportional to the l1-distance, the sum of the horizontal and the vertical distance.)