平衡分式指派问题

在经典指派问题和瓶颈指派问题研究的基础上,给出了平衡指派问题的一种新的演变形式,即带有分式目标函数的平衡指派问题,并提出了求解该平衡分式指派问题的多项式时间算法,阐述了算法的有效性,并且给出了时间复杂度,还通过一个算例演示了此算法。     

指派问题的树算法

给出了求解指派问题的树算法.该法将指派方案与树枝建立联系,每种指派方案对应一个树枝,通过画指派树讨论所有可能的指派方案,最后经过比较得到最优指派方案.该算法简单易懂,易于掌握,能够找到全部最优指派方案,并且容易编程实现.     

基于区间数排序的区间型指派问题研究

对区间型指派问题进行了研究与讨论.给出区间数的运算法则以及区间数的排序方法,并结合遗传算法对区间型指派问题进行求解计算,与传统的求解算法相比,该算法在处理区间型指派问题时具有求解速度快,运算效率较高的特点,可以很好的解决一些实际的区间型指派问题.该文最后给出具体算例对该方法的可行性与准确性加以验证.     

最优指派问题的动态规划模型及算法

考虑了指派问题:有m项工作和n个人.若m与n是相同的,并且每一项工作只能由一个人来做;同时,每一个人只能做一项工作;符合这一条件的指派问题称为标准指派问题;若m与n不相同, 则称为非标准指派问题.本文在充分考虑了指派问题性质的基础上,建立了求解标准指派问题的动态规划模型,并给出了其求解算法;同时在标准指派问题的动态规划模型的基础上给出了求解非标准指派问题的动态规划模型.最后,通过实例说明了本文提出的方法的基本步骤和计算方法的可靠性.     

一种基于伏格尔法的指派问题新算法

指派问题是一个应用广泛的运筹学问题.用伏格尔(Vogel)法以及闭合回路验优和调优的方法给出了指派问题的新算法,该算法避免了匈牙利法可能导致死循环的缺陷.并编制了通用高效的计算机程序,该程序能求解任意n人员n任务的指派问题.     

两类多目标广义指派问题的有效算法及其应用

讨论了两类目标广义指派问题,给出了它们的多目标整数线性规划数学模型,并结合模糊理论与解决传统指派问题的匈牙处算法提出了一种新的求解算法——模糊匈牙利法。给出了该方法在物资供应中的应用。     

基于混合算法求解指派问题

本研究建立了指派问题的数学模型，提出了以遗传算法和蚁群算法相结合的思想及其解决方案．算法主要是将每一个任务作为一个基因位形成染色体，以遗传算法控制寻优方向，更适宜解决组合优化问题．实验结果表明，使用此算法解决指派问题，提高了搜索效率，能够在短时间内找到最优分配方案，证明该算法是可行的．     

2种限制性指派问题

提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.     

基于特殊需要的指派问题

基于可持续发展和保护资源、环境的特殊需要，给出了3种新的指派问题的数学模型及其求解方法．它们分别是B指派问题、C指派问题和D指派问题。     

二维瓶颈指派问题的动态规划算法

基于前人对一维瓶颈指派问题的算法的研究，讨论了二维瓶颈指派问题，并给出了一种带阀值的动态规划算法。     

区域极点配置

对区域极点配置的已有成果进行综述．区域极点配置的基本方法总结为：代数Riccati方程(ARE)方法和线性矩阵不等式(LMI)方法．列出了可以结合区域极点配置方法来研究的控制问题(如最优控制、鲁棒性、H2性能、H-性能等)的主要研究成果．最后,给出了几点研究展望．     

匈牙利方法在资源分配问题中的应用

通过对一维资源平行分配问题的讨论,给出了将该问题分解成若干个指派问题的方法,通过用匈牙利方法求解应对的指派问题,得出该资源分配问题的最优解。     

广义模糊指派问题的解法

对于指派问题,工作未完成之前,其效率矩阵中的元素应该是不确定的。但是决策者为了得到具有指导性的决策,有必要对效率矩阵中的元素进行统计或粗略估计。由此产生了更加贴近于现实生活中的不确定环境中的指派问题。针对现实生活中的模糊指派问题,讨论了模糊指派问题出现的三种可能情况,分别建立了它们的数学模型。将求解传统指派问题的匈牙利算法和伏格尔法进行了推广,讨论了模糊指派问题的求解方法,并结合算例进行了说明。     

带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。     

一类非平衡指派问题的求解

讨论了一类非平衡指派问题的求解方法,即要求指派给各人的任务数目两两之间相差不能超过1,并且要求所需总费用或总时间最少的非平衡指派问题,采取虚拟假想任务或者虚拟假想人的方法将之转化为平衡指派问题进行求解.     

“人少任务多”型指派问题的一种新算法

对于“人少任务多”型指派问题的解法,人们已经提出了很多解法,如“加边补零”法[1],“加边补最小值”法[2],只是前面提到的这些方法总体思路都是将其转化为标准指派问题来求解;对此,提出了一种不同于传统解法的差额法,方法不必一开始就去用新的矩阵去代替原系数矩阵,而是可直接在原系数矩阵上进行求解;方法简洁,直观,而且优于传统算法.     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。     

分派问题的迭代理论与方法

对文献^[1]提出的分派问题的对角线解法，进行了改进，使其理论更完备，过程更简单，提高了它的理论价值和实用价值。