0028算法笔记——【回溯法】批作业调度问题和符号三角形问题

《0028算法笔记——【回溯法】批作业调度问题和符号三角形问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案  1、批作业调度问题    (1)问题描述   给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。   批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。    例：设n=3，考虑以下实例：   这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分

2、别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。    (2)算法设计文档大全实用标准文案    批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2,……n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。   算法具体代码如下：[cpp] viewplain copy1.#include "stdafx.h"  2.#include   3.using namespace

3、 std;   4.  5.class Flowshop  6.{  7.    friend int Flow(int **M,int n,int bestx[]);  8.    private:  9.        void Backtrack(int i);  10.  11.        int **M,    // 各作业所需的处理时间  文档大全实用标准文案1.            *x,     // 当前作业调度  2.            *bestx,    // 当前最优作业调度  3.  4.            *f2,    // 机器

4、2完成处理时间  5.            f1,    // 机器1完成处理时间  6.            f,     // 完成时间和  7.  8.            bestf,    // 当前最优值  9.            n;  // 作业数  10. };   11.  12.int Flow(int **M,int n,int bestx[]);  13.  14.template   15.inline void Swap(Type &a, Type &b);  16.  17.int main()  18.{  

5、19.    int n=3,bf;  20.    int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};  21.  22.    int **M=new int*[n+1];  23.  24.    for(int i=0;i<=n;i++)  25.    {  26.        M[i]=new int[3];  27.    }  28.    cout<<"M(i,j)值如下："<

6、nt j=0;j<3;j++)  33.        {  34.            M[i][j]=M1[i][j];  35.        }  36.    }  37.  38.    int bestx[4];  39.    for(int i=1;i<=n;i++)  40.    {  41.        cout<<"(";  42.        for(int j=1;j<3;j++)  43.        cout<

7、.    bf=Flow(M,n,bestx);  4.  5.    for(int i=0;i<=n;i++)  6.    {  7.        delete []M[i];  8.    }  9.    delete []M;  10.  11.    M=0;  12.  13.    cout<