装配线调度算法

---

    本文介绍装配线调度算法及C++实现。

    作者：tyc611.cublog.cn，2008-06-09

---

[问题描述]

    有两条装配线，它们有相同功能的装配站，但在其上的装配效率（时间）有所不同。从任一起始装配站进入装配线后，可在任一装配站选择进入任一条装配线的下一装配站。并且，移入本条装配线和另外一条装配线的装配站的所用时间也不相同（这里考虑本条装配线的时间开销不计）。要求寻找一条装配时间最短的装配流程。
    问题描述详见《算法导论》（第二版）P192, 15.1 装配线调度

 

[算法思想]

    利用DP方法，把整个问题的最优问题转化为子问题的最优问题。

 

[算法时间复杂度]

    算法时间复杂度为O(N)。

 

[算法扩展及相关问题]

    这里并没有考虑在本条装配线移动的时间，如果给予考虑，只需稍微修改实现即可。另外，往往有很多问题比这更简单，相应的实现修改也较为容易。

 

[C++实现]

 

/**
* AssemblyLineDispatch.cpp
* @Author Tu Yongce
* @Created 2008-6-9
* @Modified 2008-6-9
* @Version 0.1
*/

#include <iostream>
#include <cassert>

using namespace std;

/*
* 利用DP方法解决装配线调度的最优问题，时间复试度为O(n)
* @param e1, e2: 分别为装配线1和2的移入时间
* @param a1, a2: 分别为装配线1和2上装配站处理时间
* @param t1, t2: 分别为装配线1和2上移动到另外一条装配线的移动时间
* @param x1, x2: 分别为装配线1和2的移出时间
* @param num: 装配线上的装配站个数
* @param minTime: [out]返回整个装配流程的最短时间
* @param bestPath: [out]返回实现最短时间的最优路径
*/
template <typename T>
static void AssemblyLineDispatch(T e1, T a1[], T t1[], T x1, T e2, T a2[], T t2[], T x2,
                          size_t num, T &minTime, size_t bestPath[])
{
    assert(num >= 2);

    // 保存子问题的最短时间
    T f1[2];
    T f2[2];
    f1[0] = e1 + a1[0];
    f2[0] = e2 + a2[0];

    // 保存子问题的最优路径
    vector<size_t> path1(num, 0);
    vector<size_t> path2(num, 0);

    for (size_t i = 1; i < num; ++i) {
        // 计算装配线1上当前装配站的最优解
        if (f1[0] + a1[i] <= f2[0] + t2[i - 1] + a1[i]) {
            f1[1] = f1[0] + a1[i];
            path1[i] = 1;
        } else {
            f1[1] = f2[0] + t2[i - 1] + a1[i];
            path1[i] = 2;
        }

        // 计算装配线2上当前装配站的最优解
        if (f2[0] + a2[i] <= f1[0] + t1[i - 1] + a2[i]) {
            f2[1] = f2[0] + a2[i];
            path2[i] = 2;
        } else {
            f2[1] = f1[0] + t1[i - 1] + a2[i];
            path2[i] = 1;
        }

        f1[0] = f1[1];
        f2[0] = f2[1];
    }

    // 计算整个装配流程的最短时间
    size_t last;
    if (f1[0] + x1 <= f2[0] + x2) {
        minTime = f1[0] + x1;
        last = 1;
    } else {
        minTime = f2[0] + x2;
        last = 2;
    }

    // 构造最优解（选择哪条装配线上的装配站）
    bestPath[num - 1] = last;
    for (int i = num - 1; i > 0; --i) {
        if (last == 1)
            last = path1[i];
        else
            last = path2[i];
        bestPath[i - 1] = last;
    }
}

void AssemblyLineDispatch_Test()
{
    typedef size_t T;
    const size_t NUM = 6;

    T e1 = 2;
    T a1[NUM] = {7, 9, 3, 4, 8, 4};
    T t1[NUM - 1] = {2, 3, 1, 3, 4};
    T x1 = 3;
    
    T e2 = 4;
    T a2[NUM] = {8, 5, 6, 4, 5, 7};
    T t2[NUM - 1] = {2, 1, 2, 2, 1};
    T x2 = 2;

    T minTime;
    size_t bestPath[NUM];

    AssemblyLineDispatch(e1, a1, t1, x1, e2, a2, t2, x2, NUM, minTime, bestPath);
    cout << "Minimum Time: " << minTime << endl;
    cout << "Best Path: ";
    for (size_t i = 0; i < NUM; ++i) {
        cout << bestPath[i] << " ";
    }
    cout << endl;
}

程序运行结果：

Minimum Time: 38
Best Path: 1 2 1 2 2 1

---