批处理作业调度问题

问题描述

给定n个作业的集合J=（J1，J2，… ，Jn）。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为t_ji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=ΣF_2i，称为该作业调度的完成时间和。

简单来说：对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。

举例：

算法设计

从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2, … , n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。

类Flowshop的数据成员记录解空间的结点信息，以便减少传给Backtrack的参数。二维数组M是输入作业的处理时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。

在递归函数Backtrack中：

1.当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。

2.当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的作业，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

算法描述

注：1、区分作业i和当前第i个正在执行的作业

给x赋初值，即其中一种排列，如x=[1,3,2]；M[x[j]][i]代表当前作业调度x排列中的第j个作业在第i台机器上的处理时间；如M[x[2]][1]就意味着作业3在机器1上的处理时间。

　　2、bestf的初值

此问题是得到最佳作业调度方案以便使其完成时间和达到最小，所以当前最优值bestf应该赋值为较大的一个值。

　　3、f1、f2的定义与计算

假定当前作业调度排列为：x=[1,2,3]；f1[i]即第i个作业在机器1上的处理时间，f2[j]即第j个作业在机器2上的处理时间；则：

f1[1]=M[1][1] , f2[1]=f1[1]+M[1][2]

f1[2]=f1[1]+M[2][1] , f2[2]=MAX(f2[1],f1[2])+M[2][2]　//f2[2]不光要等作业2自己在机器1上的处理时间，还要等作业1在机器2上的处理时间，选其大者。

f1[3]=f1[2]+M[3][1] , f2[3]=MAX(f2[2],f1[3])+M[3][2]

f1只有当前值有用，可以覆盖赋值，所以定义为int型变量即可，减少空间消耗；f2需要记录每个作业的处理时间，所以定义为int *型，以便计算得完成时间和。

　　4、f2[0]的初值

f2[i]的计算都是基于上一个作业f2[i-1]进行的，所以要记得给f2平[0]赋值为0。

代码实现

class Flowshop
{
    friend Flow(int * *,int,int[]);
private:
    void Backtrack(int i);
    int * * M,　　　　　　//各作业所需的处理时间，根据上面的例子就是4*3的矩阵————M[j][i]代表第j个作业在第i台机器上的处理时间
        * x,　　　　　　　//当前作业调度————其中一种排列顺序
        * bestx,　　　　 //当前最优作业调度
        * f2,　　　　　　 //机器2完成处理时间————记录每个作业在机器2上的完成时间
        f1,　　　　　　　　//机器1完成处理时间————定义int型，减少空间消耗（因为只有当前的f1有用，所以可以覆盖赋值）
        f,　　　　　　　　//完成时间和
        bestf,　　　　　　//当前最优值
        n;　　　　　　　　//作业树
};
void Flowshop::Backtrack(int i)
{
    if(i>n)
    {
        for(int j=1;j<=n;j++)
            bestx[j] = x[j];
        bestf = f;
    }
    else
    {
        for(int j=i;j<=n;j++)　　//排列树中j从i开始————控制分支数
        {
            f1+=M[x[j]][i];　　//在第1台机器上的完成处理时间————着重关注M矩阵的行标（代表当前执行的作业，是动态变化的）
            f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];　　//在机器2上的完成处理时间，f2[0]初值赋为0
            f+=f2[i];　　　　//总的完成时间和
            if(f<bestf)　　//剪枝函数
            {
                Swap(x[i],x[j]);
                Backtrack(i+1);
                Swap(x[i],x[j]);
            }
            f1 -= M[x[j]][1];　　//改变机器完成时间计数————递归返回时
            f -= f2[i];
        }
    }
}
int Flow(int * * M,int n,int bestx[])
{
    int ub = INT_AMX;
    Flowshop X;
    X.x = new int [n+1];
    X.f2 = new int [n+1];
    X.M = M;
    X.n = n;
    X.bestf = ub;
    X.bestx = bestx;
    X.f1 = 0;
    X.f = 0;
    for(int i=0;i<=n;i++)
    {
        X.f2[i] = 0;
        X.x[i] i;
    }
    X.Backtrack(1);
    delete [] X x;
    delete [] X f2;
    return X.bestf;
}