基于二分图匹配的一类多机调度问题研究
第8卷%第7期
软件导刊
2009年7月SoftwareGuide
Vol.8No.7Jul.2009
基于二分图匹配的一类多机调度问题研究
张
超，曾显华，齐凯隆
（中南大学信息科学与工程学院，湖南长沙410012）
摘
要：二分图是图论当中一种特殊的模型，求带权二分图的最佳匹配算法对许多具有最优解的实际应用问题的解
决是准确和高效的。针对多机系统的操作系统的一类多机调度问题进行了分析，建立了该问题的二分图模型并给出了二分图匹配的算法，对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。关键词：二分图；匹配；最优解；多机调度问题中图分类号：TP312
文献标识码：A
文章编号：1672-7800（2009）07－0073－03
要的应用，并且在很多情况下是求出最优解精确而高效的算法。
0引言
二分图也称二部图，是图论当中一种特殊的模型。根据其
1问题的提出
在多机系统中有M台处理机，某一时刻有N个作业来请
定义，它是无向图，其顶点集V可分割为两个互不相交的子集（X，Y），并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集（iinX，jinY）。求带权二分图的最佳匹配就是根据图中两边的点之间的关系以及已存在的边的信息，选择已存在的边当中的若干条边组成一个完备匹配，该匹配能够使这两个不相交的子集中的某一个子集中所有的点都饱和并且该匹配是所有的匹配当中边的权值加起来和最大的一个匹配。求二分图的匹配在一些安排、调度等问题当中有重
求处理，由于每台处理机性能的不同以及作业的内容不同，所以不同的作业在不同的处理机上所需的时间也不同，假设第i个作业在第j台处理机上处理所需的时间是t［i］［j］。（某个作业全在某个处理机上完成，处理机只有处理完当前作业后才会去处理其它的作业）
问题：现在要你设计一个调度方案，使这N个作业的平均回转时间最小。一个作业的回转时间为它结束时刻和它请求处
［5］［6］［7］
薛理银.教育信息处理［M］.北京：高等教育出版社，1995.白云.网络教学资源自适应组织研究［D］.重庆：西南师范大学，
［8］
学，2003.
刘清堂，杨宗凯.可重用的学习对象及其应用策略［J］.电化教育研究，2003（8）.
（责任编辑：王
钊）
2003.
高晓红.基于网络的自适应学习系统研究［D］.上海：上海师范大
ResearchoftheDiagnosisAlgorithmBasedonPointsofKnowledge
Abstract：Thethesisresearchpointstoknowledge-basedlearningcontenthierarchy,andtoexplorethebasisofthetestonhowtoeffec-tivelydiagnoseproblemsofknowledgepoints.ThesisstudyofthecontentsofthefirstalgorithmOrganizeresourcesexistOrganizestudytheeffectofparticlesizeandtheevaluationandsoon.Secondly,thedefinitionofalearningobjectgranularityandknowledgebetweentheprecursors,successorsandparallelrelationship,tobuildaknowledge-pointforameaningfulunitstudyresourcesorganizationalframe-work,laidthereuseandsharingofresources,aswellastheeffectiveorganizationofresourcesbasis.Thirdly,attestonthebasisofthediscussedproblemsofthediagnosisalgorithm,andonthisbasisapracticalexample,experimentsshowthatthealgorithmisfeasible.KeyWords：KnowledgePointDetectionAlgorithmOrganize
作者简介：张超（1987-），男，湖北黄冈人，中南大学信息科学与工程学院本科生，研究方向为软件开发；曾显华（1987-），男，湖南邵阳人，中南大学
信息科学与工程学院本科生，研究方向为软件开发；齐凯隆（1988-），男，陕西宝鸡人，中南大学信息科学与工程学院本科生，研究方向为软件开发。
软件导刊2009年
理时刻（对于上述所有作业来说，这个时刻都是0）的差。
2
问题的二分图匹配算法
2.1
问题的的性质
上述问题是多机调度问题当中的一种，它不同于多机调度
当中要求完成所有作业时的时刻最早的那种NP问题，它是要使所有作业的平均回转时间最小，这是一个P类问题，它能够求得精确解。下面介绍用二分图匹配求得精确解的思路及算法。
先分析一台处理机的情况。假设这台处理机按顺序处理的
k个作业的所花费的处理时间依次是t1，t2，t3，…，tk，那么第i个
作业的回转时间则为ri=t1+t2+t3+…+ti所以这k个作业总的回转时间是t1+（t1+t2）+（t1+t2+t3）+…+（t1+t2+t3+…+tk）=t1×k+t2×（k-
1）+t3×（k-2）+…tk-1×2+tk从这里可以看出如果作业i是处理机j
中倒数第p个处理的程序，那么它对总的回转时间的增加量是
t［i］［j］*p。由上述分析可以看出，由于同一个作业在处理机上
被处理的位次不同致使其对总回转时间的增加量不同，所以如果建立二分图的话，就要对代表机器的点进行拆点处理，将每个点拆成N（作业总数）个点来表示作业在该处理机上被处理的位次。
2.2二分图模型的建立
构造一个二分图G，左边的N个结点为N个作业，右边的
M个结点为M台处理机
，这样就是原始的二分图了
。
第7期张超，曾显华，齐凯隆：基于二分图匹配的一类多机调度问题研究
·75·
if（!usedy［v］&&slack［v］
dec=slack［v］；
for（u=1；u
if（usedx［u］）lx［u］-=dec；for（v=1；v
if（usedy［v］）ly［v］+=dec；elseslack［v］-=dec；}}}
for（u=1；u
执行完KM算法后，返回的结果就是二分图最大权匹配的结果，将该结果取反就是要求的结果了，即最小的总运转时间，然后再将取反后的结果除以N即为最小的平均运转时间，实现语句是min_t=（double）（-KM（））/N。同时link［］数组中记录着匹配的信息，也就是调度的信息。
度时的分配如下：机器1上依次处理作业3、作业1，机器2上处理作业4，机器3上依次处理作业2，作业5。
该调度算法的时间复杂度取决于KM算法，假设n=，则该
KM算法需要找O（n）次增广路，每次增广最多需要修改O（n）
次顶标，每次修改顶标时从slack［］数组中查找O（n）次，所以时间复杂度为O（n3）。该调度算法的空间复杂度为O（N2M）。
3结束语
综合以上分析，整个多机调度问题的二分图匹配算法的时
间复杂度为0（N3M3），所占空间复杂度为O（N2M）。该算法比搜索、动态规划等算法有更高效的时间复杂度，并且该算法能获得精确解。该调度算法提高了计算机系统资源的利用率，加快了用户的响应，从而使用户获得最合理的响应时间，满足不同用户的要求。
参考文献：［1］［2］
BONDYJA，MURTYUSR．Graphtheorywithapplication［M］．London：Macmillan，1976.
GuizhenLiu，BinhaiZhu.Someproblemsonfactorizationwithcon-straintsinbipartitegraphs［J］.DiscreteAppliedMath，2003（128）：421-423.
2.4算法的结果与复杂度分析
应用上述算法，对M为3，N为5，并且5个作业在3台处
理机上的处理时间的t数组为t［5］［3］={{7，9，8}，{6，5，4}，
［3］余样宣，崔国华，邹海明.计算机算法基础［M］.武汉：华中科技大学出版社，2000.
（责任编辑：杜能钢）
{3，4，6}，{8，5，7}，{6，5，5}}，进行该调度算法后得出min_t即最
小平均回转时间是6.2，得出记录匹配信息的数组link［1…15］
={1，3，-1，-1，-1，4，-1，-1，-1，-1，5，2，-1，-1，-1}，其表示调
ResearchofaClassofSchedulingProblemofMulticomputer
BasedonBipartiteGraphMatching
Abstract：TheBipartiteGraphisaspecialkindofmodelinthegraphtheory,thealgorithmofsolvingthebestmatchingoftheweightedbipartitegraphisaaccurateandhigh-efficientmethodtomanyproblemswhichhavethebestmethod.Inthispaper,akindofschedulingproblemofmulticomputerisbroughtupfirstly.AndthenamodalofBipartiteGraphforthisproblemisbuildandannovelalgorithmforthisproblembasedonBipartiteGraphMatchingisproposed.Finally,thecomplexityoftheproposedalgorithmisanalyzed.Simulationre-sultsstowitiseffective.
KeyWords：BipartiteGraph;Matching;BestMethod;SchedulingProblemofMulticomputer