流水车间问题描述

       在参考文献[1]可以查阅到十六种车间调度问题模型，本文的讨论对象为多资源调度模型(Multi-Resource Constrained Job Shop Scheduling Problem)。

       该车间调度模型一般被描述为，在车间内包含M种不同的作业，N台不同的机器，每个作业有P种不同的零件需要安装。

       在该模型下，同样又有多种模型分支。在参考文献[2]中，作者提供了6种流水车间调度模型，本文仅讨论模型一，经典流水车间排序调度模型。模型和描述如下（1，2，3表示机器，A，B，C表示作业，每个作业有三个零件需分别在1，2，3机器上加工）：

                                      

       车间内的每个作业如果不是正在处理就是在下一台机器上的缓冲区等待，在第一台机器上运行的第一个作业运行完毕后将没有任何等待的进入下一台机器上运行。在第一台机器上的所有作业都是连续的无延迟的执行。当一个作业在最后一台机器上运行完毕后，就会被系统立即释放。

流水车间问题的数学模型

以下内容主要参考于文献[3].

问题描述

     该问题是个经典NP难问题(此处对NP难问题是啥不过多描述，虽然这涉及研究该问题的意义)。

     流水车间问题（Flow Shop Schedual Problem，以下简称FSSP）的描述如下：

     在一条生产线上，n个作业按一定的顺序在m台机器上进行处理，作业i在机器j上的处理时间记为

                                                                          t(i, j)     i = 1, 2...n; j = 1, 2...m;

      这个处理时间是固定的，但非负，可以为零，零即表示这个作业无需在该机器上运行。以上图为例，在2机器上的C蓝色方框不存在即表示处理时间为零。

      FSSP需要解决的是 --- 从第一台机器上第一个作业的开始时间到最后一台机器的最后一个作业的结束时间相差最小的作业排列顺序。

     该问题还有以下条件：

1. 每个作业在每台机器上只能运行一次；
2. 每台机器在同一时刻只能处理一个作业；
3. 每个作业在某一时刻只能在一台机器上处理；
4. 作业不可被抢占；
5. 作业在机器上的处理时间不随调度序列的改变而改变；
6. 机器的使用顺序是固定的，以上图为例，机器使用顺序为1->2->3；

计算方案

    经典流水车间的各作业完工时间由两部分组成，

    一是自身处理时间，记作 t(i,j)  -- 上文已经提及。

    二是作业处理前，已经被消耗的时间，记作 c(i, j) -- 表示作业i在机器j上的完工时间。

    以下是数学公式描述：

    c(1, 1) = t(1, 1)  --  作业1在机器1上的完工时间等于自身的处理时间；

    c(1,  j) = c(1, j-1) + t(1, j) -- 作业1在机器j上的完工时间等于作业1在上一台机器上的完工时间加上本次处理时间；

    c(k, 1) = c(k-1, 1) + t(k, 1) -- 作业k在机器1上的完工时间等于k-1道作业在机器1上的完工时间加上本次处理时间；

    c(k, j) = max(c(k-1, j), c(k, j-1)) + t(k, j) --  作业k在机器j上的完工时间等于本次处理时间加上，

                                                     第k-1道作业在机器j上的完工时间和第k个作业在j-1台机器上的完工时间的较大值；

    通过以上公式，有如下描述：

    MakeSpan = min(c(n, m)) ;

    MakeSpan及整个流水线的完工时间，等于最后一个机器上最后一个作业的完工时间；

c/c++代码计算完工时间

    代码写法很多，笔者初次使用了递归的写法，但由于存在很多的重复计算，导致了计算时间过长，在此引以为戒！！！

    于是改成了以下写法：

const int mecNum = m; // 机器总数
const int proNum = n; // 总作业数

// 作业
struct Process{
    int index = -1; // 作业序号
    int cost[mecNum] = {0}; // 该作业每道工序耗时
}p[proNum];

// 总耗时函数
int Makespan(Process pro[])
{
    int curMaxPath[mecNum] = {0};
    int preMaxPath[mecNum] = {0};

    // 第i道作业
    for(int i = 0; i < proNum; i++)
    {
        if(i == 0)
        {
            // 第j个机器/第i道作业的第j道工序
            for(int j = 0; j < mecNum; j++)
            {
                if(j == 0)
                    curMaxPath[j] = pro[i].cost[j];
                else
                    curMaxPath[j] += (curMaxPath[j-1] + pro[i].cost[j]);

            }
            memcpy(preMaxPath, curMaxPath, sizeof curMaxPath);
        }
        else
        {
            for(int j = 0; j < mecNum; j++)
            {
                if(j == 0)
                    curMaxPath[j] = (preMaxPath[j] + pro[i].cost[j]);
                else
                    // 比较前一步工序完成时间和前一个作业当前工序完成时间
                    curMaxPath[j] = (max(curMaxPath[j-1], preMaxPath[j]) + pro[i].cost[j]);

            }
            memcpy(preMaxPath, curMaxPath, sizeof curMaxPath);
        }
    }
    return curMaxPath[mecNum-1];
}

获取最佳调度序列的方法

    同样，在文献[1]中介绍了许多种方法以解决车间调度问题，本文暂且对各种方法仅作提及，不作详细描述。

    笔者比较感兴趣的获取方式为超启发式算法，超启发式算法以高层决策调度底层启发式算法的方式来解决问题，底层启发式算法常见的有，遗传算法，蚁群算法，模拟退火算法，粒子群算法，神经网络等。各底层算法在网上已有很多介绍，若读者对超启发算法感兴趣可以查找并阅读文献[4]，推荐此文仅因为中文好懂...

    机器学习小白的笔记，如有错误，还请大佬指出~！

参考文献

[1]潘全科.车间调度问题研究[J].聊城大学学报(自然科学版),2004.03,17(1):10.

[2]S.S.Panwalkar,Christos Koulama.Analysis of flow shop scheduling anomalies[J].ELSEVIER,1 January 2020,280(1):25-33.

[3]E.Taillard.Some efficient heuristic methods for the flow shop sequencing problem[J].Elsevier,5 July 1990,47(1):65-74.

[4]谢毅,侯彦娥,陈小潘,等.超启发算法研究进展综述[J].计算机工程与应用,2017,53(14):1-8.