求解AFS问题的两种启发式算法在最坏情况下性能比上界的可达性研究

对文献[2]中提出的求AFS问题的次优解的两个简单易行的启发式算法及其品性进行了进一步的研究。由于已证明了其在最坏情况下性能比Cmax（H）／Cmax的上界不去超过2,本文用两个典型的例子证明：对这两种算法,这一上界是可达的。     

求解MAFS问题的归并算法的性能比研究

对M＋1台机器的MAFS排序问题，在该问题的启发式算法的基础上作了进一步的研究。用一实例证明，MAFS排序问题的归并算法的性能比是上界可达的。     

自由作业问题的一种启发式算法及最坏性能比分析

研究具有准备时间的自由作业问题，给出一种简单的启发式算法，证明 在此启发式算法上，最坏性能比是2－1／m（其中m是机器的参数），且上界是紧的。从而证明了对该问题的猜想：即在贪婪算法的情况下其最坏性能比是2－1／m（其中m是机器的台数），且上界是紧的。特别当m＝2时，具有准备时间的自由作业问题，利用该启发式算法得到最坏性能比是3／2，其上界也是紧的。     

一类装配式流水作业排序问题的启发式算法及其性能比研究

根据Ｆ′２｜ｍ１≥２，ｍ２＝１｜Ｃｍａｘ排序问题是ＮＰ完全问题的论断，提出了ＡＦＳ问题的两个启发式算法，分别给出了应用启发式算法的实例，并证明了该启发式算法在最坏情况下的品性是２的结论     

具有准备时间的流水作业时间表问题启发式算法与最坏性能比分析

本文研究具有准备时间的流水作业时间表问题，给了一个简单的启发式算法，证明了一个简单的启发式算法的最坏性能比是m 1/2(其中m是机器的台数)，且关于上界是紧的，特别当m=2时，该启发式算法的最坏性能比是3／2，此结果要好于Potts在1985年所给出的算法。     

单机工件运输排序问题上界的改进

在单机排序和工件运输问题的模型中,在2T1≥T3限制下,我们证明了最劣性能比可改进为27/14.     

关于旅行商问题的若干启发式算法的性能比分析

旅行商问题的增量最小插入法、最近插入法、最近加入法的性能比已经被证明有一个上界2,本文在欧几里德平面上给出了这些方法性能比接近于2的例子。另外,我们证明了凸包选边插入法的性能比有一个关于点数的对数函数上界。     

具有延迟时间的自由作业排序问题——最坏性能比分析

研究一类具有延迟时间的自由作业问题，证明在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2。特别当m＝2时，证明了该算法的最坏性能比为3／2，其中m为机器的台数。     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

Flow shop排序问题F2｜prmu｜∑ωjCj的一个启发式算法

给出Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法，其最坏情况的界为2，且是紧界。此外，还讨论了它的三种多项式可解的条件。     

TSP邻近算法在Euclid平面上的性能比分析

旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。     

赋有提前或延误惩罚的单机排序问题的动态规划算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题，没有多项式时间算法。笔者曾证明［２］：如果附加条件ｐｉ≥ｐＪｐｉ／ｗｉ＞ｐｊ／ｗｊ对于所有的ｉ≠ｊ（ｉ，ｊ＝１，２，…，ｎ）成立，则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。     

定位-运输路线安排问题的一种启发式算法研究

定位-运输路线安排问题(LRP)是分销网络设计和物流管理决策中的难题,属于NP难问题,求解有一定难度.文章通过构造辅助函数对优化问题约束条件的处理,基于分层次实现多个目标的思路将LRP看作一个整体,利用具群体智能的粒子群算法进行求解,避免了基于两阶段算法的不足,减小了在进化过程中停滞于局部最优解的概率.为粒子群算法在大规模组合优化问题中实际应用做了有益的尝试.     

具有多台通用机的Cmax问题的启发式算法及其性能指标分析

本文讨论了一类特殊的排序问题，具有二台专用机与ｍ台通用机的两组工件的Ｃｍａｘ问题，给出了ＬＳＭＴ启发式算法，并在ｍ＝２的情况下给出了算法性能指标的严格界。     

一类复合并行机排序问题计算复杂性研究

研究确定性排序理论的一个新模型：考虑４台机器的集合Ｍ＝（Ｍ１，Ｍ２，Ｍ３，Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ１，ｊ２，…，ｊｎ），每个零件同时被２ｉ＝（ｉ＝０，１，２）台机器同时加工。证明了在不允许间断，优化指标为作业排序长度的条件下，该问题是强ＮＰ－完全问题，没有多项式时间算法。     

单件车间排序问题的一个启发式算法

本文提出了一个启发式算法,经计算表明,这个方法对于以加工周期为目标函数的单件车间排序问题,效果是比较好的。     

有重叠的两抓钩周期性排序问题的启发式算法

抓钩排序问题不同于古典的排序问题,只有一个抓钩和一种产品,它仍然被证明为ＮＰ难题,对于有重叠区域的两抓钩周期性排序问题,迄今尚无法用数学模型直接求解。为了寻找出好的排序,提出了一种启发式算法以及求解有重叠两抓钩周期性排序问题。该方法把问题分解成相应序列的子问题,并对每个序列化建立和求解一个整体问题的线性规划模型,在序列空间中,通过寻找好的序列以得到最佳的排序。量化的示例表明所使用的方法是高效的。     

单机排序问题1｜P_k≥P_qP_k／W_k＞P_q／W_q｜sum from q＝1 to n of （…）W_q｜c_q－d_q｜近似最优解的伪多项式时间算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：单机排序问题１‖ｎｑ＝１Ｗｑｍａｘ｛（ｃｑ－ｄｑ），０｝是“强”ＮＰ完全的。而该问题是１‖ｎｑ＝１Ｗｑ｜ｃｑ－ｄｑ｜的子问题，因而也是强ＮＰ完全问题，没有好算法。本文在假设Ｐｋ≥ＰｑＰｋ／Ｗｋ＞Ｐｑ／Ｗｑ成立的条件下，设计出求该问题的近似最优解的伪多项式时间算法。     

一类调整时间可分离的Flow Shop 排序问题F3│S│Cmax的最优算法

讨论调整时间可分离的Flow Shop排序问题F3│S│Cmax，对其一类特殊情况给出了最优算法。     

一种遗传算法在集合覆盖问题中的应用研究

利用遗传算法的思想把集合覆盖问题进行适当的转化并提出了一种适用于求解该问题的改进遗传算法,通过对种群中的染色体进行启发式改进和遗传参数的选取,来达到求解的目的.