VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > 批处理教程 >
  • 回溯法——批处理作业调度

问题描述:

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

简单描述:

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

举例说明:

tji 机器1 机器2
作业1 2 1
作业2 3 1
作业3 2 3

 

 

 

  

  这3个作业的调度方案共有6种(即3个作业的全排列),分别是123,132,213,231,312,321,它们所相应的完成时间和分别是19,18,20,21,19,19。显而易见,最佳调度方案是132,其完成时间和为18。

算法设计:

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

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

  在递归函数Backtrack中,

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

    当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。

复制代码
 1 class Flowshop
 2 {
 3     friend Flow(int * *,int,int[]);
 4 private:
 5     void Backtrack(int i);
 6     int * * M,      //各作业所需的处理时间,根据上面的例子就是4*3的矩阵————M[j][i]代表第j个作业在第i台机器上的处理时间
 7         * x,       //当前作业调度————其中一种排列顺序
 8         * bestx,     //当前最优作业调度
 9         * f2,       //机器2完成处理时间————记录每个作业在机器2上的完成时间
10         f1,        //机器1完成处理时间————定义int型,减少空间消耗(因为只有当前的f1有用,所以可以覆盖赋值)
11         f,        //完成时间和
12         bestf,      //当前最优值
13         n;        //作业树
14 };
15 void Flowshop::Backtrack(int i)
16 {
17     if(i>n)
18     {
19         for(int j=1;j<=n;j++)
20             bestx[j] = x[j];
21         bestf = f;
22     }
23     else
24     {
25         for(int j=i;j<=n;j++)  //排列树中j从i开始————控制分支数
26         {
27             f1+=M[x[j]][i];  //在第1台机器上的完成处理时间————着重关注M矩阵的行标(代表当前执行的作业,是动态变化的)
28             f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];  //在机器2上的完成处理时间,f2[0]初值赋为0
29             f+=f2[i];    //总的完成时间和
30             if(f<bestf)  //剪枝函数
31             {
32                 Swap(x[i],x[j]);
33                 Backtrack(i+1);
34                 Swap(x[i],x[j]);
35             }
36             f1 -= M[x[j]][1];  //改变机器完成时间计数————递归返回37             f -= f2[i];
38         }
39     }
40 }
41 int Flow(int * * M,int n,int bestx[])
42 {
43     int ub = INT_AMX;
44     Flowshop X;
45     X.x = new int [n+1];
46     X.f2 = new int [n+1];
47     X.M = M;
48     X.n = n;
49     X.bestf = ub;
50     X.bestx = bestx;
51     X.f1 = 0;
52     X.f = 0;
53     for(int i=0;i<=n;i++)
54     {
55         X.f2[i] = 0;
56         X.x[i] i;
57     }
58     X.Backtrack(1);
59     delete [] X x;
60     delete [] X f2;
61     return X.bestf;
62 }
复制代码

具体实现 示例代码:

复制代码
 1 #include <iostream>
 2 using namespace std;
 3 #define MAX 200
 4 int* x1;//作业Ji在机器1上的工作时间;
 5 int* x2;//作业Ji在机器2上的工作时间;
 6 
 7 int number=0;//作业的数目;
 8 
 9 int* xOrder;//作业顺序;
10 int* bestOrder;//最优的作业顺序;
11 
12 int bestValue=MAX;//最优的时间;
13 int xValue=0;//当前完成用的时间;
14 int f1=0;//机器1完成的处理时间;
15 int* f2;//第i阶段机器2完成的时间;
16 
17 
18 void BackTrace(int k)
19 {
20      if (k>number)
21      {
22           for (int i=1;i<=number;i++)
23           {
24              bestOrder[i]=xOrder[i];
25           }
26           bestValue=xValue;
27      }
28  else
29  {
30       for (int i=k;i<=number;i++)
31       {
32            f1+=x1[xOrder[i]];
33            f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]];
34            xValue+=f2[k];
35            swap(xOrder[i],xOrder[k]);
36            if (xValue<bestValue)
37            {
38                 BackTrace(k+1);
39            }
40            swap(xOrder[i],xOrder[k]);
41            xValue-=f2[k];
42            f1-=x1[xOrder[i]];
43       }
44   
45  }
46 }
47 int main()
48 {
49      cout<<"请输入作业数目:";
50      cin>>number;
51      x1=new int[number+1];
52      x2=new int[number+1];
53      xOrder=new int[number+1];
54      bestOrder=new int[number+1];
55      f2=new int[number+1];
56 
57      x1[0]=0;
58      x2[0]=0;
59      xOrder[0]=0;
60      bestOrder[0]=0;
61      f2[0]=0;
62 
63      cout<<"请输入每个作业在机器1上所用的时间:"<<endl;
64      for (int i=1;i<=number;i++)
65      {
66       cout<<""<<i<<"个作业=";
67       cin>>x1[i];
68      }
69 
70      cout<<"请输入每个作业在机器2上所用的时间:"<<endl;
71      for (i=1;i<=number;i++)
72      {
73       cout<<""<<i<<"个作业=";
74       cin>>x2[i];
75      }
76 
77      for (i=1;i<=number;i++)
78      {
79         xOrder[i]=i;
80      }
81      BackTrace(1);
82      cout<<"最节省的时间为:"<<bestValue;
83      cout<<endl;
84      cout<<"对应的方案为:";
85      for (i=1;i<=number;i++)
86      {
87          cout<<bestOrder[i]<<"  ";
88      }
89      return 0;
90 }
复制代码



原文:https://www.cnblogs.com/xymqx/p/3724366.html


相关教程