一类二阶段指派问题

经典的指派问题是研究资源与任务的二元匹配。作为推广,三维指派问题是研究资源、任务与作业的三元匹配。前者已有成熟的有效算法,后者是著名的NP困难问题。本文讨论介于二者之间的一类二阶段指派问题,即可分解为二阶段决策的特殊三维匹配问题,给出多项式时间算法。     

图的消去割宽问题

图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件：图中的边在一次性被搜索后立即堵塞，使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域. 在这个条件限制下，图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系，得到了一些特殊图类的消去割宽值.     

多专用机的两组工件的P／／C_（max）问题

本文对具有多台专用机与通用机的两组工件的Ｐ     

弦图扩张与最优排序

弦图是一类特殊的完美图，以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题，沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

关于拟阵与组合最优化方法

本论文讨论了拟阵与组合最优化问题之间的关系．阐述了用拟阵这一数学工具解决组合最优化问题的一些方法和思想．     

在线可中断二台机器流水作业问题

本文研究了可中断的二台机器流水作业排序问题,目标函数为最小化最大完工时间,工件实时到达,工件信息在工件到达之前不可知。我们给出了该在线问题的下界,并对问题中只有两个到达时间的特殊情况给出了3/2竞争的在线算法。     

限制情况下装卸工问题的最优解

装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过.现代物流技术迅速发展,促成和推动装卸工问题的提出和研究.装卸工问题是一个新的NP困难的组合优化问题,首先介绍装卸工问题及限制情况下装卸工问题的数学模型,然后分析限制情况下的装卸工问题的性质,最后给出该问题的所有最优解.     

矩阵与有向图的双标号带宽

定义了一般矩阵与有向图的双标号带宽,并给出了一些理论结果.此外还给出了无向图带宽的一个新结果.     

有尺寸的同型机分批排序问题的近似算法

对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比.