批处理作业调度-回溯法-白红宇

问题描述：

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

简单描述：

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

算法设计：

　　从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。

　　类Flowshop的数据成员记录解空间的结点信息，M输入作业时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。

　　在递归函数Backtrack中，

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

　　　　当i<n时，当前扩展结点在i-1层，以深度优先方式，递归的对相应子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

算法描述：

class Flowshop{    friend Flow(int * *,int,int[]);private:    void Backtrack(int i);    int * * M,        * x,        * bestx,        * f2,        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++)        {            f1+=M[x[j]][i];            f2=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];            f+=f2[i];            if(f

实例代码：

#include 
      
       using namespace std;#define MAX 200int* x1;//作业Ji在机器1上的工作时间；int* x2;//作业Ji在机器2上的工作时间；int number=0;//作业的数目；int* xOrder;//作业顺序；int* bestOrder;//最优的作业顺序；int bestValue=MAX;//最优的时间；int xValue=0;//当前完成用的时间；int f1=0;//机器1完成的处理时间；int* f2;//第i阶段机器2完成的时间；void BackTrace(int k){     if (k>number)     {          for (int i=1;i<=number;i++)          {             bestOrder[i]=xOrder[i];          }          bestValue=xValue;     } else {      for (int i=k;i<=number;i++)      {           f1+=x1[xOrder[i]];           f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]];           xValue+=f2[k];           swap(xOrder[i],xOrder[k]);           if (xValue
       
        >number;     x1=new int[number+1];     x2=new int[number+1];     xOrder=new int[number+1];     bestOrder=new int[number+1];     f2=new int[number+1];     x1[0]=0;     x2[0]=0;     xOrder[0]=0;     bestOrder[0]=0;     f2[0]=0;     cout<<"请输入每个作业在机器1上所用的时间："<

本文转自博客园xingoo的博客，原文链接：，如需转载请自行联系原博主。