基于二分图匹配的一类多机调度问题研究

二分图是图论当中一种特殊的模型,求带权二分图的最佳匹配算法对许多具有最优解的实际应用问题的解决是准确和高效的。针对多机系统的操作系统的一类多机调度问题进行了分析,建立了该问题的二分图模型并给出了二分图匹配的算法,对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。     

二分图为k-消去图的2个条件

图G的一个k 正则支撑子图称为G的k 因子 .若对G的任一边e ,图G总存在一个k 因子不含e ,则称G是k 消去图 .若图G存在一个划分 (X ,Y)使得G的每条边的端点分别在X和Y中 ,则称G =(X ,Y)为二分图 .证明了二分图G =(X ,Y)且X =Y是k 消去图的充分必要条件是kS≤r1+2r2 +… +k(rk+… +rΔ) -ε(S)对所有S X成立 .并由此给出二分图是k 消去图的一个邻集充分条件 .     

基于二分图的动态排课系统的设计与实现

高校排课涉及诸多因素,是一个典型的受约束条件下的多目标优化问题。按学科大类招生、学生入校后的一至两年内重点进行基础培养、根据兴趣和双向选择原则进行专业分流等多方面的教学改革措施进一步增加了排课的难度,导致排课算法的时间复杂性显著增加。本文设计了一种基于二分图的动态排课算法,实现了一个动态排课系统,试运行结果表明,算法及系统时间复杂性得到有效控制,并能够有效解决排课问题。     

多巷道堆垛机联合作业调度问题研究

自动化立体仓库作为现代物流技术领域内出现的一种新型仓储方式,在工业生产中发挥着日益重要的作用。自动化立体仓库作业调度往往需要多巷道堆垛机联合作业,根据作业调度相关原则,提出基于时间要求的堆垛机调度算法模型和优化调度的三个目标,运用遗传算法实现多目标的优化,采用矩阵编码和不同目标互相交叉的方法,解决多巷道堆垛机联合作业优化调度问题,突破了传统的仅对单目标进行优化的特点。     

用模拟退火算法解决生产调度问题

介绍了Metropolis准则，给出了模拟退火算法解决生产调度问题的基本方法和步骤，并对算法的有效性进行了验证．     

一类LP问题无穷多最优解的求法

本文利用对偶定理和互补松驰定理,给出了一类LP问题——多个变量,两个约束的线性规划问题的无穷多最优解的求法.     

完备二分图的冠的k-优美性

图的优美性是图的一个重要性质,有广泛的应用.马克杰猜想:完备二分图Km,n的冠I(Km,n)是k-优美图,这里m,n,k是任意正整数且m n.对于m=2,3,4,5或k>(m-1)n的情形,利用构造的方法,证明了猜想的正确性.这一结果丰富了优美图理论.     

多六隅图完备匹配计数的一种新方法

多六隅图有着十分明显的理论化学背景，其完备匹配的计数是一个广泛研究的课题。本文通过定义一种特殊矩阵，从而给出了一类多六隅图完备匹配计数的显工表达式。     

基于遗传算法的公交调度模糊最优解

降低公交运行成本、方便乘客乘坐是公交调度首要考虑的因素,因此,对公交调度进行优化设计要充分协调乘客和公交公司的利益冲突。首先建立能够模拟公交车运行的确定性模型,然后引入隶属度函数,在确定性模型的基础上建立模糊多目标规划模型,使用遗传算法对其进行求解。通过实例对基于遗传算法与确定性模型的公交调度结果进行比对,结果表明,基于遗传算法获得的公交调度模糊最优解比确定性模型更为合理。     

一类推广的Bottleneck问题的多项式算法

本文讨论了一类Bottleneck问题,给出了判定最优解的三个定理,并在此基础上给出了一个求最优解的算法和算例,算法的复杂度为O(n2).     

基于最大匹配算法的列车调度模型

在铁路大提速的背景下,对重要的铁路干线京沪线给出了基于最大匹配算法的列车调度方案.从列车运行时的空闲时间表出发,建立一组不等式模型,求解出现行列车时刻表对于货车的空闲时间,进而计算出货车通行量的理论最大值.为了求得在此时的货车运行时刻表的一个可行解,设计了空闲时间表的最大匹配算法.此算法实现了一个造表过程,采用迭代搜索的方法从货车通行量的瓶颈区间出发,依次求出各个货车可行的时刻序列,直到表被填满,即可得到一个可行的货车时刻表.     

一类三角函数多解问题的处理手段

三角函数求值是三角函数中常见问题.这类问题的基本题型有:求某角的三角函数值,求某角的大小等.在这类问题中,如果不注重分析元素(如角)之间的相互制约关系,不注重分析隐藏条件,就容易导致得出多解的错误结论.本文就这类问题常见处理手段作一介绍.     

基于约束的部分枚举策略的空间关系图匹配算法研究

本提出了一种基于约束的部分枚举空间关系图匹配策略．该策略通过使用在匹配过程中动态生成的2类匹配约束条件智能预测当前匹配状态的后继有效的枚举状态以跳过无效的中间匹配状态，达到状态空间剪枝的目的，可以有效降低空间关系图匹配过程中状态搜索空间．根据理论分析，该策略在最好情况下的时间复杂度为O(n^2)，在几乎很少发生的最坏情况下时间复杂度为O(n!)；其空间复杂度都是O(n)．所提出的方法已在笔研发的手绘草图识别系统Smart Sketchpad中取得了很好的识别效果．     

一类函数最小值问题的多解与推广探讨

我们经常会遇到这样的习题: 1.直线l过定点P(1,2 2),且与x、y轴正半轴分别交于A、B两点,试求|PA| | PB |的最小值. 2.P(1,2 2)为椭圆x2/a2 y2/b2=1(a,b＞0)上一点,试求a b的最小值.     

一类串行生产线的最优调度问题的注记

讨论了串行生产线的最优调度问题,给出了生产线生产周期的显示公式,给出两个变量时最优调度的解的特性．     

导出匹配可扩图的韧度

如果图G的每一个导出匹配都包含在图G的一个完美匹配中,则称图G是导出匹配可扩的.用T(G)表示图G的韧度,文章的主要结论是:设G是有2n(n≥3)个顶点的非完全图,如果G是导出匹配可扩的,则2/(n-1) ≤T (G) ≤n-1;对于任意满足2/(n-1) ≤p/q≤n-1,p+q≤2n,1≤q≤n-1的数p/q,都有韧度为p/q的导出匹配可扩图.     

一个自对偶图的匹配等价图类

与自身对偶的平面图称为自对偶图,其匹配唯一性的研究具有重要的意义。文章利用比较其匹配多项式的系数方法对一个自对偶图的匹配等价图类进行研究,得到该自对偶图的匹配等价图类的刻画,并证明其是匹配唯一的。     

Harary图的k-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.     

多车队实时指挥调度系统设计

多车队实时指挥调度突破了一般指挥调度系统的单纯监控车辆和仅作简单指挥的局限性,把指挥调度的对象从单辆车扩展到同时对多个车队的实时监控和指挥调度,并在GIS地图上实时直观地图形化展示车队情况,使得车队、沿路警力、指挥中心能够密切配合,保障大型活动中交通及人员入场、散场的通畅有序。     

基于活动图的建筑工程施工规划与调度方法研究

为了降低建筑工程的总成本和缩短施工工期,兼顾建筑工程施工过程的安全,设计了基于活动图的施工规划和调度方法。该方法首先从初始活动图中提取候选施工计划,然后将计划从活动图转换为离散事件模拟模型。接下来使用现有的移动规划计划算法生成无障碍的安全移动轨迹,并根据移动设备的轨迹计算安全评分。通过结合影响施工计划的不同指标(即成本、资源和期限),选择合适的施工计划。最后,采用案例研究来展示本方法的实用性。结果证明,此施工规划与调度方法不仅实际适用,而且能为项目经理提供方便有效的工作方式。