算法设计策略-回溯法

0/1背包

问题描述

回溯法求解

限界函数

0/1背包算法

批处理作业调度

问题描述

设有n个作业的集合{0,1,⋯,n−1}，每个作业有两项任务，要求分别在两台设备P1和P2上完成。每个作业必须现在P1上加工，然后再在P2上加工。P1和P2加工作业i所需的时间分别为ai和bi。作业i的完成时间fi(S)是指在调度方案S下，该作业的所有任务得以完成的时间，则MTF(S)=1n∑n−1i=0fi(S)是采用调度方案S的平均完成时间。批处理作业调度（batch job schedule）问题要求确定这n个作业的最优作业调度方案使其MTF最小。这等价于求使得所有作业的完成时间之和FT(S)=∑n−1i=0fi(S)最小的调度方案。

回溯法求解

对于双机批处理作业调度问题，其可行解是n个作业的所有可能的排列，每一种排列代表一种作业调度方案S，其目标函数是FT(S)=∑n−1i=0fi(S)。使FT(S)具有最小值的调度方案或作业排列是问题的最优解。

从之前在动态规划法中讨论的已经知道，对于双机作业调度问题，存在一个最优非抢先调度方案，使得在P1和P2上的作业完全以相同的次序处理。因此，批处理作业调度问题的解空间大小为n!。

求解这一问题没有有效的约束函数，但可以使用最优解的上界值U进行剪枝。如果对于已经调度的作业子集的某种排列，所需的完成时间之和已经大于迄今为止所记录下的关于最优调度方案的完成时间之和的上界值U，则该分枝可以剪去。

批处理作业调度算法

class BatchJob{
public:
    BatchJob(int sz, int *aa,int *bb,int up)
    {
        n=sz;
        U=up;
        f=f1=0;
        a=new int[n];
        b=new int[n];
        f2=new int[n];
        y=new int[n];
        for(int i=0;i<n;i++){
            a[i]=aa[i];
            b[i]=bb[i];
            y[i]=i;
        }
    }
    int JobSch(int *x);//求最优调度方案和最小FT值

private:
    void JobSch(int i, int *x);//递归函数
    int *a,*b,n,U;//保存输入数据
    int f,f1,*f2,*y;//局部数据
};

void BatchJob::JobSch(int i,int *x)
{
    if(i==n){
        for(int j=0;j<n;j++){
            //记录迄今为止的最优解
            x[j]=y[j];
        }
        U=f;
    } else {
        for(int j=i;j<n;j++){
            //考察剩余作业的各种可能排列
            f1 += a[y[j]];//第i个处理作业j
            f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+b[y[i]];//P2执行必须在f1+a[i]时间之后开始
            f += f2[i];//累计作业i的完成时间
            if(f<U){
                Swap(y,i,j);
                JobSch(i+1,x);
                Swap(y,i,j);//准备选择新的排列
            }
            //恢复原来的f和f1值
            f1 -= a[y[j]];
            f -= f2[i];
        }
    }
}

int BatchJob::JobSch(int *x)
{
    //一维数组x保存最优作业调度方案，函数返回最小FT
    JobSch(0,x);
    return U;
}

数组y保存当前的部分向量，迄今为止已经得到的完成时间之和最小的解向量保存长度为n的一维数组x中，其值为U。在状态空间树的每一状态结点处，对剩余作业生成各种可能的排列，并考察之。

//产生各种可能排列的算法
//排列产生算法
template<class T>
void Perm(T a[],int k,int n)
{
    if(k==n-1){
        //输出一种排列
        for(int i = 0;i<n;i++)
            cout << a[i] <<" ";
        cout << endl;
    } else {
        //产生{a[k],...,a[n-1]}各种排列
        for(int i = k;i<n;i++){
            T t=a[k];
            a[k]=a[i];
            a[i]=t;
            Perm(a,k+1,n);//产生{a[k+1],...,a[n-1]}各种排列
            t=a[k];
            a[k]=a[i];
            a[i]=t;
        }
    }
}