/*

批处理作业调度

输入: 3

2 1

3 1

2 3

输出：18

1 3 2

*/

#include

#include

#include

#define MAXSIZE 100

int n; //作业的个数

int m1[MAXSIZE]; //每个作业在机器一上完成的时间

int m2[MAXSIZE]; //每个作业在机器二上完成的时间

int f1; //机器一完成的时间

int f2[MAXSIZE]; //机器二完成的时间

int cf; //当前所用时间

int bestf; //当前最优时间

int x[MAXSIZE]; //当前解

int bestx[MAXSIZE]; //最优解

//输入

void input();

//初始化

void init();

//回溯法

void backtrack(int);

//交换

void Swap(int*, int*);

int main(void)

{

int i = 1;

while (1)

{

input();

init();

backtrack(1);

printf("%d\n", bestf);

for (i = 1; i <= n; ++i)

{

printf("%d ", bestx[i]);

}

printf("\n");

}

return 0;

}

void input()

{

int i = 1;

printf("please enter n:");

scanf("%d", &n);

for (i = 1; i <= n; ++i)

{

scanf("%d %d", &m1[i], &m2[i]);

}

}

void init()

{

int i = 1;

cf = 0;

bestf = INT_MAX;

f1 = 0;

for (i = 1; i <= n; ++i)

{

x[i] = i;

f2[i] = 0;

}

}

void backtrack(int t)

{

int i = 1;

int j = 1;

if (t > n)

{

if (cf < bestf)

{

bestf = cf;

for (i = 1; i <= n; ++i)

{

bestx[i] = x[i];

}

}

}

else

{

for (j = t; j <= n; ++j)

{

f1 += m1[x[j]];

f2[t] = (f1 > f2[t - 1] ? f1 : f2[t - 1]) + m2[x[j]];

cf += f2[t];

if (cf < bestf)

{

Swap(&x[t], &x[j]);

backtrack(t + 1);

Swap(&x[t], &x[j]);

}

f1 -= m1[x[j]];

cf -= f2[t];

}

}

}

void Swap(int *a, int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

1、问题描述

每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f是指把F2i将i从1-n求和，称为该作业调度的完成时间和。

２、简单描述

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

区别于流水线调度问题：批处理作业调度旨在求出使其完成时间和达到最小的最佳调度序列；

流水线调度问题旨在求出使其最后一个作业的完成时间最小的最佳调度序列；

例：设n=3，考虑以下实例：

这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。那么具体的完成时间和是怎么计算的呢？将在第3部分举例说明中详细描述。

3、举例说明

４、算法设计

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

按照回溯法搜索排列树的算法框架，设开始时x=[1,2, ... , n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列(所有的调度序列)构成。

二维数组M是输入作业的处理时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。

在递归函数Backtrack中，

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

当i

5、算法分析

【前期准备】

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]

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

4、f2[0]的初值

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

6.代码实现

#include

using namespacestd;int x[100]; //当前作业调度————其中一种排列顺序

int bestx[100]; //当前最优作业调度

int m[100][100];//各作业所需的处理时间//M[j][i]代表第j个作业在第i台机器上的处理时间

int f1=0;//机器1完成处理时间

int f2=0;//机器2完成处理时间

int cf=0;//完成时间和

int bestf=10000;//当前最优值，即最优的处理时间和

int n;//作业数

void swap(int &a,int &b)

{int temp=a;

a=b;

b=temp;

}void Backtrack(intt)

{//t用来指示到达的层数(第几步，从0开始)，同时也指示当前执行完第几个任务/作业

inttempf,j;if(t>n) //到达叶子结点，搜索到最底部

{if(cf

{for(int i=1; i<=n; i++)

bestx[i]=x[i];//更新最优调度序列

bestf=cf;//更新最优目标值

}

}else //非叶子结点

{for(j=t; j<=n; j++) //j用来指示选择了哪个任务/作业(也就是执行顺序)

{

f1+=m[x[j]][1];//选择第x[j]个任务在机器１上执行，作为当前的任务

tempf=f2;//保存上一个作业在机器2的完成时间

f2=(f1>f2?f1:f2)+m[x[j]][2];//保存当前作业在机器2的完成时间

cf+=f2; //在机器2上的完成时间和//如果该作业处理完之后，总时间已经超过最优时间，就直接回溯。//剪枝函数

if(cf

{

swap(x[t],x[j]);//交换两个作业的位置，把选择出的原来在x[j]位置上的任务调到当前执行的位置x[t]

Backtrack(t+1); //深度搜索解空间树，进入下一层

swap(x[t],x[j]); //进行回溯，还原，执行该层的下一个任务//如果是叶子节点返回上一层

}//回溯需要还原各个值

f1-=m[x[j]][1];

cf-=f2;

f2=tempf;

}

}

}intmain()

{inti,j;

cout<

cin>>n;

cout<

for(j=1; j<=n; j++)

cin>>m[j][i];//第j个作业,第i台机器的时间值

for(i=1; i<=n; i++)

x[i]=i;//初始化当前作业调度的一种排列顺序

Backtrack(1);

cout<

cout<

cout<

cout<

cout<

}/*测试数据：

3

2 3 2

1 1 3

3

2 5 4

3 2 1*/

View Code

7.实现结果

参考文献：王晓东《算法设计与分析》

回溯法之批处理作业调度

1. 问题描述

​n个作业集合{1, 2, ..., n}。每个作业先由机器1处理，再由机器2处理。作业i需要机器j处理的时间为Mij 。

Mij

机器1

机器2

作业1

2

1

作业2

3

1

作业3

2

3

​对于一个确定的作业调度，设Fij 是作业i在机器j上完成的具体时间。所有作业在机器2上完成的具体时间(时刻)之和f称为该作业调度的完成时间和。

​要求：对于给定的n个作业，制定最佳作业调度方案(一个排列)，使其完成时间和达到最小

2. 问题分析

​3个作业的6种可能的调度方案是1-2-3；1-3-2；2-1-3；2-3-1；3-1-2；3-2-1；它们所相应的完成时间和分别是19,18，20,21,19,19。易见，最佳调度方案是1-3-2，其完成时间和为18。

​Fi1、Fi2表示事件i分别在机器1和机器2上完成的时间。

作业顺序

Fi1

Fi2

f

begin

0

0

0

①

2

3

3

③

4

7

10

②

7

8

18

​假设此时1-2-3的作业调度已经完成计算，遍历到了1-3-2的序列。

​首先是①，将调用f1 += M[x[j]][1];表示作业1在机器1需要2时间才能完成，接下来使用f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];比较F02 和 F11 的大小，即需要等待前一个作业在机器2完成计算才能在机器2开始本次作业，再使用F02 和 F11的较大值F11+作业2在机器2的工作时间1得到F12为3，在使用f += f2[i]，将3赋值给f。

​到③，调用f1 += M[x[j]][1];，F21变为2+2=4，再比较F12和F21，将较大的F21+3=7赋值给F22。f变为10。

​到②，F31变为7，比较F22和F31，将7+1=8复制给F32，最终将f变为18，得到最终结果。

3. 代码求解

​该问题的解空间：排列树：

​

​使用到的全局变量：

M 各作业所需的处理时间

x 当前作业调度

bestx 当前最优作业调度

f2 机器2完成的处理时间

f1 机器1完成的处理时间

f 完成时间和

bestf 当前最优值

n 作业数

​核心求解代码：

void BackTrack(int i) {

// i > n表示已经访问到叶子结点，即一个作业调度遍历完成

// 将此时的最优解暂时保存到bestx中

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]][1];

f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];

f += f2[i];

// 如果f小于当前的最小值，代表这个分支可以继续运算，否则直接裁去该分支，达到优化算法的目的

if (f < bestf) {

swap(i, j);

// 递归求解

BackTrack(i + 1);

// 递归运算后，需要回退到上一层排列树

swap(i, j);

}

// 本条路径求解结束后回退到原本的状态

f1 -= M[x[j]][1];

f -= f2[i];

}

}

}

4. 完整代码

/**

* 回溯法求解批处理作业调度问题

*

* 主要由BackTrack函数递归调用求解问题

* 使用bsetf保存最优解，bestx保存最优的作业调度序列

**/

#include

#include

#define MAXROW 4

#define MAXCOL 3

/**

* M 各作业所需的处理时间

* x 当前作业调度

* bestx 当前最优作业调度

* f2 机器2完成的处理时间

* f1 机器1完成的处理时间

* f 完成时间和

* bestf 当前最优值

* n 作业数

**/

int M[MAXROW][MAXCOL], x[MAXROW], bestx[MAXROW], f2[MAXROW], f1, f, bestf, n;

// 值交换函数

void swap(int i, int j) {

int tmp = x[i];

x[i] = x[j];

x[j] = tmp;

}

void BackTrack(int i) {

// i > n表示已经访问到叶子结点，即一个作业调度遍历完成

// 将此时的最优解暂时保存到bestx中

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]][1];

f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];

f += f2[i];

if (f < bestf) {

swap(i, j);

BackTrack(i + 1);

swap(i, j);

}

f1 -= M[x[j]][1];

f -= f2[i];

}

}

}

void main() {

n = 3;

bestf = INT_MAX;

M[1][1] = 2;M[1][2] = 1;

M[2][1] = 3;M[2][2] = 1;

M[3][1] = 2;M[3][2] = 3;

for (int i = 0; i <= n; i++) {

f2[i] = 0;

x[i] = i;

}

BackTrack(1);

printf("%d\n", bestf);

for (int i = 1; i <= n; i++) {

printf("%d ", bestx[i]);

if (i != n)

printf("-> ");

}

printf("\n");

system("pause");

}