分支限界法-批处理调度问题

分支限界法-批处理调度问题

ID:45114306

大小:136.86 KB

页数:15页

时间:2019-11-10

分支限界法-批处理调度问题_第1页
分支限界法-批处理调度问题_第2页
分支限界法-批处理调度问题_第3页
分支限界法-批处理调度问题_第4页
分支限界法-批处理调度问题_第5页
资源描述:

《分支限界法-批处理调度问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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;它们所相应的完成时间和分别是19,1

2、8,20,21,19,19。易见,最佳调度方案是1,3,2,其完成时间和为18。    限界函数15    批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度,所以如图,批处理作业调度问题的解空间是一颗排列树。      在作业调度问相应的排列空间树中,每一个节点E都对应于一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为:   设

3、M

4、=r,且L是以节点E为根的子树中的叶节点,相应的作业调度为{pk,k=1,2,……n},其中pk是第k个安排的作业。如果从节点E15到叶节点L的路上,每一个作业pk在机器1上完成处理后都能立即在机器2

5、上开始处理,即从pr+1开始,机器1没有空闲时间,则对于该叶节点L有:注:(n-k+1)t1pk,因为是完成时间和,所以,后续的(n-k+1)个作业完成时间和都得算上t1pk。   如果不能做到上面这一点,则s1只会增加,从而有:。   类似地,如果从节点E开始到节点L的路上,从作业pr+1开始,机器2没有空闲时间,则:   同理可知,s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是:   注意到如果选择Pk,使t1pk在k>=r+1时依非减序排列,S1则取得极小值。同理如果选择Pk使t2pk依非减序排列,则S2取得极小值。 15   这可以作为优先队列式分支

6、限界法中的限界函数。    算法描述    算法中用最小堆表示活节点优先队列。最小堆中元素类型是MinHeapNode。每一个MinHeapNode类型的节点包含域x,用来表示节点所相应的作业调度。s表示该作业已安排的作业时x[1:s]。f1表示当前已安排的作业在机器1上的最后完成时间;f2表示当前已安排作业在机器2上的完成时间;sf2表示当前已安排的作业在机器2上的完成时间和;bb表示当前完成时间和下界。二维数组M表示所给的n个作业在机器1和机器2所需的处理时间。在类Flowshop中用二维数组b存储排好序的作业处理时间。数组a表示数组M和b的对应关系。算法Sort实现对各作

7、业在机器1和2上所需时间排序。函数Bound用于计算完成时间和下界。   函数BBFlow中while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值(完成时间和下界)的结点作为当前扩展结点,并加以扩展。算法将当前扩展节点E分两种情形处理:15 1)首先考虑E.s=n的情形,当前扩展结点E是排列树中的叶结点。E.sf2是相应于该叶结点的完成时间和。当E.sf2

8、ode,计算出其相应的完成时间和的下界bb。当bb  2.  3.template  4.class Graph;  5.  6.template   7.class MinHeap   8.{   9.    template  10.    friend class Graph;  11.    public:   12.        MinHe

9、ap(int maxheapsize = 10);   13.        ~MinHeap(){delete []heap;}   14.  15.        int Size() const{return currentsize;}   16.        T Max(){if(currentsize) return heap[1];}   17.  18.        MinHeap& Insert(const T& x);   19.        MinHeap

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。