4.6 独立作业最优调度问题

4.6 独立作业最优调度问题

算法设计思想：

(1) 动态规划法

用数组*A和*B分别存放作业由处理机A和B处理需要的时间，预处理得到所有作业均由机器A处理所需的时间A_total和均由B处理的时间B_total。

构造布尔型三维数组***p，p[i][j][k]=true表示前k个作业能够在机器A用时不超过i时间、机器B不超过j时间内完成。这样，对于任意一个状态p[i][j][k]=true，第k个任务可能由机器A或机器B完成，对应的前一状态分别为p[i-A[k-1]][j][k-1]和p[i][j-B[k-1]][k-1]。显然，对任意的i、j，有p[i][j][0]。

初始令p[i][j][k]=false，可以得到动态规划的状态转移方程：

计算出所有的状态后，得到最优解（最短处理时间）为：

另外，构造整型三维数组***c，表示p[i][j][k]=true时第k个作业的调度情况。初始c[i][j][k]均为0，c[i][j][k]=1表示由机器A处理，c[i][j][k]=2表示由机器B处理，c[i][j][k]=3表示机器A、B都能处理。在计算状态时，如果p[i-A[k-1]][j][k-1]=true，则c[i][j][k]=1；如果p[i][j-B[k-1]][k-1]=true，则c[i][j][k]=2；如果都都满足，则c[i][j][k]=3。从每一个p[i][j][n]=true且max(i,j)=minimun的c[i][j][n]反推，即可构造所有可能的最优调度方案。

(2) 二叉树思想输出

二叉树思想输出所有最优解：如果不存在c[i][j][k]=3的情况，则反推c[i][j][n]即可得到所有可能的最优调度方案。但是，解空间中c[i][j][k]=3实际上是二叉树中含有两个儿子的情况，因此必须采用二叉树的遍历算法，才能不漏掉所有的最优方案。想到上学期的数据结构这门课中学到的二叉树结构，通过二叉树的后序遍历算法，即可输出所需叶子节点的路径。

采用动态数组，注意了三维动态数组的申请和释放，这样做节省了内存，使程序变得灵活，可以处理大规模数据。

除此之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。

程序设计代码：

/*头文件 作业调度问题.h*/

#ifndef KNAP_H

#define KNAP_H

#include

#include

using namespace std;

struct state //记录状态地址

{

int i, j; //AB处理时间

int k; //处理的任务

int c; //1代表A处理，2代表B处理

};

class Schedule //作业调度

{

public:

Schedule(char *in, char *out); //构造函数

~Schedule(); //析构函数

void Solve(); //输出结果到文件

protected:

void Plan(); //动态规划最优方案

int Max(int x, int y); //返回二者最大值

void Print(); //打印最优解

void PrintBinaryTree(int i, int j); //用二叉树思想后序遍历打印所有最优方案

private:

int task_num; //作业数

int *A, *B; //处理时间数组

int A_total, B_total; //作业均有A/B处理需要时间

bool ***p; //p[i][j][k]=true表示前k个作业在A用时不超过i，B不超过j内完成

int ***c; //c[i][j][k]表示p[i][j][k]=true时第k个作业的调度情况

int minimum; //最短处理时间

ofstream fout; //输出结果文件

};

#endif

/*函数实现文件 作业调度问题.cpp*/

#include "作业调度问题.h"

Schedule::Schedule(char *in, char *out) : fout(out)

{

ifstream fin(in);

if( !fin )

{

fout << "文件" << in << "无法打开！" << endl;

exit(1);

}

fin >> task_num; //初始化作业数

A = new int[task_num];

B = new int[task_num];

for(int i = 0; i < task_num; i++)

fin >> A[i]; //初始化A处理器时间表

for(int i = 0; i < task_num; i++)

fin >> B[i]; //初始化B处理器时间表

minimum = INT_MAX; //初始化最短处理时间

A_total = B_total = 0;

for(int i = 0; i < task_num; i++) //全部由A/B处理的时间

{

A_total += A[i];

B_total += B[i];

}

p = new bool**[A_total+1];

c = new int**[A_total+1];

for(int i = 0; i <= A_total; i++)

{

p[i] = new bool*[B_total+1];

c[i] = new int*[B_total+1];

}

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

{

p[i][j] = new bool[task_num+1];

c[i][j] = new int[task_num+1];

for(int k = 0; k <= task_num; k++)

{

p[i][j][k] = false;

c[i][j][k] = 0;

}

}

fin.close();

if( !fout )

{

fout << "文件" << out << "无法打开!" << endl;

exit(1);

}

}

Schedule::~Schedule()

{

if(fout)

fout.close();

if(A)

delete []A;

if(B)

delete []B;

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

if(p[i][j] && c[i][j])

{

delete []p[i][j];

delete []c[i][j];

}

for(int i = 0; i <= A_total; i++)

if(p[i] && c[i])

{

delete []p[i];

delete []c[i];

}

if(p && c)

{

delete []p;

delete []c;

}

}

void Schedule::Solve()

{

Plan(); //动态规划最优调度方案

Print(); //打印最优解及所有方案

}

void Schedule::Plan()

{

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

p[i][j][0] = true; //初始化处理0个作业可完成

for(int k = 1; k <= task_num; k++) //遍历前task_num个作业

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

{

if(i - A[k-1] >= 0 && p[i - A[k-1]][j][k-1] == true && j - B[k-1] >= 0 &&

p[i][j - B[k-1]][k-1] == true) //如果两个处理器都能处理

{

p[i][j][k] = true;

c[i][j][k] = 3;

}

else if(i - A[k-1] >= 0 && p[i - A[k-1]][j][k-1] == true) //只有A能处理

{

p[i][j][k] = true;

c[i][j][k] = 1;

}

else if(j - B[k-1] >= 0 && p[i][j - B[k-1]][k-1] == true) //只有B能处理

{

p[i][j][k] = true;

c[i][j][k] = 2;

}

}

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

if(p[i][j][task_num] == true && Max(i, j) < minimum)

minimum = Max(i, j); //得到完成所有作业的最少时间

}

int Schedule::Max(int x, int y)

{

if(x > y)

return x;

else

return y;

}

void Schedule::Print()

{

fout << minimum << endl;

for(int i = 0; i <= A_total; i++)

for(int j = 0; j <= B_total; j++)

//如果i、j时间内能完成而且是最优方案

if(p[i][j][task_num] == true && Max(i, j) == minimum)

PrintBinaryTree(i, j); //用二叉树思想后序遍历打印所有最优方案

}

void Schedule::PrintBinaryTree(int i, int j)

{

state *Stack;

Stack = new state[task_num+1]; //构造状态地址栈，下标从1开始

int top = 0; //置栈空

state root; //二叉树根

state temp; //状态指针

int flag; //标志未处理的右子树的根

root.i = i;

root.j = j;

root.k = task_num;

do

{

while(root.k > 0) //当根非空时，向最左下遍历

{

if(c[root.i][root.j][root.k] == 1 || c[root.i][root.j][root.k] == 3)

root.c = 1; //工作由A处理

else

root.c = 2; //工作由B处理

Stack[++top] = root; //不断将左孩子(A处理)入栈

if(c[root.i][root.j][root.k] == 1 || c[root.i][root.j][root.k] == 3)//左孩子由A做

{

root.k--;

root.i -= A[root.k]; //根指向左孩子

}

else //没有左孩子

{

root.k = -1; //根指空

}

}

temp.i = temp.j = temp.k = -1; //空指针

flag = 0; //不是新的右子树的根

while(top > 0 && flag == 0) //栈非空且不是新的右子树的根

{

root = Stack[top];

if(root.i == temp.i && root.j - B[root.k-1] == temp.j && root.k-1 == temp.k ||

c[root.i][root.j][root.k] == 1 && temp.k == -1 || root.k == 1)//是右孩子就访问

{

temp = root;

if(top==task_num && root.c==1 && root.i - A[root.k-1]==0 && root.j==0 ||

root.c == 2 && root.i == 0 && root.j - B[root.k-1] == 0) //找到一最优方案

{

for(int i = task_num; i > 0; i--)

fout << Stack[i].c << ' '; //根据是左右孩子确定A/B处理

fout << endl;

}

top--;

}

else

{

if(c[root.i][root.j][root.k] == 2 || c[root.i][root.j][root.k] == 3)//右孩子B做

{

Stack[task_num - root.k + 1].c = 2; //工作改由B处理

root.k--;

root.j -= B[root.k]; //根指向右孩子

}

else //没有右孩子

{

root.k = -1; //根指空

}

flag = 1; //为处理过的右子树的根

}

}

if(root.k == 0 && (root.i != 0 || root.j != 0)) //不是最优方案

break;

}while(top > 0); //栈非空继续遍历

}

/*主函数文件 test.cpp*/

#include "作业调度问题.h"

int main()

{

char *in = "input.txt"; //输入文件

char *out = "output.txt"; //输出文件

Schedule task(in, out); //文件初始化作业

task.Solve(); //动态规划求最优调度方案

return 0;

}

本文来源：https://www.2haoxitong.net/k/doc/99ba280952d380eb62946dee.html