3.7 安排生产作业任务

德国企业BÖWE CARDTEC（博威卡技术公司）为管理智能卡（信用卡、身份证等）生产过程提供软硬件产品。该公司的客户通常都用同一硬件设备生产多种不同类型的智能卡，因此在两轮任务不同的生产过程之间需要有重新配置的步骤，例如更换色带颜色并插入正确的空白卡。两轮生产作业之间的准备时间相当长，从而导致整体日产量下降。为解决这一问题，BÖWE CARDTEC软件使用TSP模型，把所有作业任务按一定顺序排列起来，使准备时间总和最小。城市就是这些作业任务，作业i和j之间的旅行成本则是硬件设备在完成作业i和开始作业j之间重新配置所需的时间。该公司报道称，应用Concorde解得的路线，通常情况下总准备时间的降幅最多能达到65%，从而总生产率也大大提高。

1954年，Merrill Flood在一次讲座中最早提出了TSP在安排计划方面的此类应用。在一般的例子中，从作业i到作业j的准备时间不同于从作业j到作业i的准备时间。因此这种TSP题目是不对称的，路线的总花费与旅行方向有很大关系。