logo资料库

分支限界法---批处理作业调度.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.06M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    #include #include #include // 用time() 得到种子 #include // 用到里面的优先队列（priority_queue） using namespace std; const int N = 8; // 作业数 const int TIME = 99; // 每个作业的时间控制在两位数内 const int NUM = 50; // 测试次数 class Flowshop1 { private: int **M, n; // 各作业所需的处理时间 // 作业数 int *bestx, // 当前最优作业调度 // 当前作业调度 // 机器完成处理时间 // 机器完成处理时间 // 完成时间和 *x, *f2, f1, f, bestf; // 当前最优值 void Backtrack(int i); void Swap(int &x, int &y); public: Flowshop1(int **M, int n); ~Flowshop1(); int getBestf(); int *getBestx(); }; struct MinHeapNode { int s, // 已经安装的作业数 // 机器上最后完成时间 // 机器上最后完成时间 f1, f2, sf2, // 当前机器上的完成时间和 bb, *x; // 当前完成时间和下界 // 当前作业调度 MinHeapNode(int n) { x = new int[n]; for (int i=0; i
    x = new int[n]; for (int i=0; i b.bb); } }; class Flowshop2 { private: int n, // 作业数 **M; // 各作业所需的处理时间 int **b, // 各作业所需的处理时间排序数组 // 数组M和b的对应关系数组 **a, *bestx, // 最优解 bestc; // 最小完成时间和 void BBFlow(void); int Bound(MinHeapNode &E, int &f1, int &f2); void Sort(void); void Swap(int &x, int &y); public: Flowshop2(int **M, int n); ~Flowshop2(); int getBestf(); int *getBestx(); }; int main() { int *M[N], i; srand(time(0)); for (int num=1; num<=NUM; num++) {
    for (i=0; igetBestf(), my2->getBestf()); for (i=0, putchar('\t'); igetBestf() != my2->getBestf()) { printf("\tNot Equal "); getchar(); // 最优值不等（表示程序有错），等待... } for (i=0; igetBestx()[i]); putchar('\n'); for (i=0; igetBestx()[i]); putchar('\n'); for (i=0; igetBestx()[i] != my2->getBestx()[i]) { putchar(7); // 最优作业调度方案不一样，响铃（允 许不一样） break; } } delete my1; delete my2; } for (i=0; i
    this->M = M; this->n = n; this->bestx = new int[n]; this->x = new int[n]; this->f2 = new int[n]; this->f1 = 0; this->f = 0; this->bestf = (~(unsigned int)0) >> 1; for (int i=0; ix[i] = i; this->Backtrack(0); } Flowshop1::~Flowshop1() { delete []bestx; delete []x; delete []f2; } int Flowshop1::getBestf() { return bestf; } int *Flowshop1::getBestx() { return bestx; } void Flowshop1::Backtrack(int i) { if (i == n) { for (int j=0; j
    M[x[j]][1]; f1 += M[x[j]][0]; f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + f += f2[i]; } if (f < bestf) { Swap(x[i], x[j]); Backtrack(i + 1); Swap(x[i], x[j]); } f1 -= M[x[j]][0]; f -= f2[i]; } } } void Flowshop1::Swap(int &x, int &y) { int temp = x; x = y; y = temp; } Flowshop2::Flowshop2(int **M, int n) { this->M = M; this->n = n; b = new int *[n]; a = new int *[n]; bestc = (~(unsigned int)0) >> 1; // 最小完成时间和 for (int i=0; iSort(); this->BBFlow(); } Flowshop2::~Flowshop2() { for (int i=0; i
    } delete []a; delete []b; delete []bestx; } int Flowshop2::getBestf() { return bestc; } int *Flowshop2::getBestx() { return bestx; } void Flowshop2::BBFlow(void) { priority_queue, cmp> H; MinHeapNode E(n); while (true) { if (E.s == n) { // 叶结点 if (E.sf2 < bestc) { bestc = E.sf2; for (int i=0; i
    delete []E.x; if (H.empty()) { printf("\tMin Heap Empty \n"); // 报错 break; } else { E = H.top(); H.pop(); } } while (!H.empty()) { delete []H.top().x; H.pop(); } } int Flowshop2::Bound(MinHeapNode &E, int &f1, int &f2) { // 计算完成时间和下界 int j, k; bool **y = new bool *[n]; // 工作数组 for (k=0; k E.f2) ? f1 : E.f2) + M[E.x[E.s]][1]; int sf2 = E.sf2 + f2; // 机器和机器的作业顺序不一样 // 分别都先运行时间短的, 而假设其可以运行 // s1: 假设机器很快很快 // s2: 假设机器很快很快 // 原则是使估计得到的下界尽可能的大 int s1 = 0, k1 = n - E.s, f3; for (j=0; j
    if (!y[j][0]) { k1--; if (k1 == n - E.s - 1) // 找到的第一个 f3 = (f2 > f1 + b[j][0]) ? f2 : f1 + b[j][0]; s1 += f1 + k1 * b[j][0]; // 假设作业在机器上顺序执行 并无时间间隔 } } int s2 = 0, k2 = n - E.s; for (j=0; j s2) ? s1 : s2); } void Flowshop2::Sort(void) { // 对各作业在机器和上所需时间排序 int *c = new int[n]; int i, j, k; for (j=0; j<2; j++) { for (i=0; ii; k--) { if (b[k - 1][j] > b[k][j]) { // 结果为从小到大 Swap(b[k - 1][j], b[k][j]); Swap(c[k - 1], c[k]); } } } for (i=0; i
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料