6.3 最佳调度问题.doc

6.3 最佳调度问题算法设计思想：(1) 分支限界法求解假设有n个任务和k个机器，首先将问题转化为一颗解空间树：树高为n，每一层对应一个任务；每个节点代表一个调度状态，记录了每个机器完成任务的时间；每个节点有k个孩子，代表下一个任务可以由k个机器来完成。这样，问题所求的最佳调度方案就是找所有机器完成时间最大值的最小值叶子节点。分支限界法的本质是对解空间树的BFS（广度优先）搜索，即将下一个任务由每个机器完成的调度状态入队，而后再依次将出队的每一个状态的子状态入队。为了实现剪枝，我们需要定义一个处理时间上界up，其含义为：当前剩下的任务全部由完成时间最早的机器处理之后，所有机器完成任务的最晚时间。这样，在搜索过程中不断缩小up，并判断当前状态的最晚完成时间，一旦大于up，说明该支路没有发展前景，进行剪枝。另外，为了使up正确地指示上界，需要首先对任务按照完成时间降序排序，并且预处理得到剩下的后m项任务的完成时间，避免在搜索过程中重复计算。(2) 采用优先队列容器在进行BFS搜索时，需要用队列来存储解空间树的各个节点，即当前的调度状态。该算法采用函数库提供的特殊容器：优先队列容器priority_queue（包含在库queue中），并且自己定义了优先队列容器所需的对象比较优先权bool operator()const为调度状态中最大机器完成时间，使队列每次出队的元素为最大完成时间最小的调度方案，实现了优先队列式的分支限界法。(3) 搜索过程中动态申请释放数组在BFS搜索过程中，解空间树的每个状态节点所记录的各机器完成时间都采用动态数组记录。这就要求我们不能仅靠构造函数中那一次动态数组申请，而是需要对每个新的状态申请一个动态数组。同样，我们也不能只靠类对象的析构函数来释放一个动态数组，而需要在算法每次剪枝时释放悬空的动态数组。我们用全局变量NUMBER（初始为0）对动态数组的申请（+）和释放（-）进行了监视，结果显示（NUMBER=0）所有申请的动态数组都得到了释放。（相应代码已删去）算法的重点是处理时间上界up的定义，优先队列容器的使用，以及对动态数组的动态申请和释放。除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。程序设计代码： /*头文件 最佳调度问题.h*/#ifndef KNAP_H#define KNAP_H#include #include #include /包含优先队列容器using namespace std;class state/记录调度状态public:state(int k);/构造函数，k是机器数state();/析构函数int x;/任务序号int *time;/记录各机器当前时间bool operator(const state &y)const; /定义优先队列所需的关系state& operator=(const state &y); /定义状态赋值运算符=private:int n;/任务数;class Task/任务类public:Task(char *in, char *out);/构造函数Task();/析构函数void Solve();/输出结果到文件protected:void Sort();/将工作时间从大到小排序void Schedule();/分枝限界法采用优先队列求解void PreProcess(int *last);/预处理，后几个工作的时间和int MinMachine(int* time);/当前状态下处理最小时间机器int *Fresh(int* old);/更新状态中的时间int Max(int* time);/返回最大时间void Print();/输出结果private:int n, k;/任务数和机器数int *t;/完成任务的时间int *time;/记录各机器工作时间int min;/最小工作时间ofstream fout;/输出结果文件;#endif/*函数实现文件 最佳调度问题.cpp*/#include 最佳调度问题.hstate:state(int k)/构造函数，k是机器数n = k;x = 0;/表示从选0个任务开始time = new intn+1;/需要记录n个机器的当前时间for(int i = 1; i (const state &y)const/定义优先队列所需的关系int this_max = 0;int y_max = 0;for(int i = 1; i = n; i+)/找到该状态机器最大处理时间if(this_max timei)this_max = timei;if(y_max y_max)/机器最大处理时间大于yreturn true;elsereturn false;state& state:operator=(const state &y) /定义状态赋值运算符=x = y.x;n = y.n;time = y.time;return *this;Task:Task(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 无法打开! n k;/初始化任务数n和机器数kt = new intn+1;for(int i = 1; i ti;/初始化各任务所需处理时间fin.close();time = new intk+1;for(int i = 1; i = k; i+)timei = 0;/初始化各机器处理时间min = INT_MAX;/最小时间开始初始化为最大值if( !fout )cerr 文件 out 无法打开! endl;exit(1);Task:Task()if(fout)fout.close();if(t)delete t;if(time)delete time;void Task:Solve()Sort();/将工作时间从大到小排序Schedule();/分枝限界法采用优先队列求解Print();/输出函数void Task:Sort()int temp;for(int i = 1; i n; i+)for(int j = i+1; j = n; j+)if(ti tj)temp = ti;ti = tj;tj = temp;void Task:Schedule()int *last;/存储剩下工作时间的数组last = new intk;/元素为之后剩余工作时间和PreProcess(last);/预处理int up = last0;/处理时间上界，初始为总时间state temp(k);/辅助状态，构造k个机器/存储状态的优先队列容器，按照当前状态机器最大完成时间升序排列priority_queuestate, vector, greater Queue;Queue.push(temp);int num;/任务序号int min_machine;/当前状态处理时间最少的机器while(1)temp = Queue.top();/取队头元素if(temp.x = n)/处理结束break;Queue.pop();num = temp.x;for(int i = 1;i 1 & temp.timei = temp.timei-1)if(i = k)/需要释放数组time内存delete temp.time;continue;/同等剪枝if(Max(temp.time) up)if(i = k)/需要释放数组time内存delete temp.time;continue;/限界剪枝temp.timei += tnum+1;/加上下一个任务的时间min_machine = MinMachine(temp.time);temp.timemin_machine += lastnum+1;if(Max(temp.time) max)min = max;/找到最优方案delete temp.time;void Task:PreProcess(int *last)for(int i = 0; i n; i+)/预处理last数组lasti = 0;for(int j = i+1; j = n; j+)lasti += tj;int Task:MinMachine(int* time)int min = INT_MAX;int min_machine;for(int i = 1; i = k; i+)if(timei min)min = timei;min_machine = i;return min_machine;int* Task:Fresh(int* old)int *temp;temp = new intk+1;for(int i = 1; i = k; i+)tempi = oldi;return temp;int Task:Max(int* time)int max = 0;for(int i = 1; i = k; i+)if(max timei)max = timei;return ma