工件具有学习效应的分批排序问题

讨论了分批排序中工件具有学习效应、目标函数为极小化加权总完工时间的几个问题,分别就所有工件的基本加工时间都相等的情况给出了几种算法,并证明了算法的最优性.     

多类工件单机排序中具有多项式时间可解的子问题

本文讨论了NP—完全问题1|MCS|∑W_iC_i的子问题找到了两个多项式可解的情形.本文还给出了其它两种情形的最优性条件,由此得到的算法可使复杂性大大降低.     

工件加工排序问题的研究

通过对在给定设备、按规定工序下多种工件加工排序问题的研究,得出了基于最短加工时间规则和优化加工顺序规则基础上的工件加工排序模型。该模型按工件加工时间长短,从短到长顺序排列,同时要求最紧张设备等待时间最小化。在设备等待时间最小化的前提下,优先加工在该设备上加工时间最短的工件,兼顾启发性的搜索方法,使平均流程时间最短。最后通过实例分析证实了该算法的有效性与实用性。     

一类无界的不相容工件族分批排序加权总完工时间问题

考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明．对工件有k个到达时间的情形,给出了一个复杂性为D（2^k-1nlogn）的启发式算法．     

工件带拒绝费用的单机排序问题

在经典排序模型中,我们往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,我们就会考虑是否要加工该工件,我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,我们把这种排序称为可拒绝排序[1][2]。本文研究了工件带拒绝费用的单机分族分批排序问题。主要证明了问题1,sfg|family-jobs,rej|Cmax+∑j∈sej和1,sfg|family-jobs,rej,b|Cmax+jisej是NP-难的,给出了它们的近似算法。     

一类排序问题的最优化算法

本文讨论了具有调整时间的多类工件单机排序问题I|MCS|∑Ci|尽.管该问题是强NP—完全的,但本文证明了一个最优解的必要条件,由此给出了一个复杂性为O(M~2(n/M 1)~M)的动态规划算法.这是一个相当满意的结果.本文还对表现测度为加权完工时间和的情况做了一些讨论,在权为类权时得到了与上述同样的结果.     

带有固定工件的一个单机排序问题

本文考虑带有固定工件的一个单机排序问题,证明了该问题是NP-困难的并给出了它的一个动态规划算法,证明该问题是拟多项式时间可解的。     

带有霸王工件的单机在线分批排序

研究了一个带有霸王工件且允许重启的单机在线分批排序,其目标函数值为求时间表长．对于批容量无限的情况,给出了一个最坏竞争比为2的在线算法．     

关于循环比赛名次排列的问题

循环比赛的名次排列中,若依据每队的得失分情况排列,出现多组并列的可能很大,这将为名次的高低问题带来争议,若利用循环比赛的得失分情况转换为邻接矩阵,通过计算,求得n级得分向量及n级失分向量,保证且有两向量分向量各异并趋于其特征向量,并可得到比赛排名,再将此运算方法推广至允许平局情况的比赛。     

机器有两种不同速度的平行工件半在线排序研究

本文提出了新模型Q2m︱rj=0,on-line-ncv︱C max,并通过分析模型的特点,设计出了半在线算法,引进等效化(Virtualization)概念证明了当P≥m(s+1)max/(i∈τ)mjPj时(其中P为工件集的总负荷),算法的竞争比为2-s/(m(s+1)).     

有理数的排序问题

有理数的排序问题融知识性和趣味性于一体，处理方法灵活多变．本文通过一些不同形式的例题，介绍解答此类问题的思考方法．     

两类单机成组排序的问题

讨论了单机成组排序问题的加权总完工时间和最大延迟时间的极小化问题.并分别给出了算法.对于单杌成组排序误工总数问题,通过构造函数,利用动态规划方法给出其算法.     

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.     

一个排序问题的解决

问题 一天内的不同时刻,经理把文件交给秘书打印,每次都将一份文件放在秘书文件堆的上面,秘书有时间就将文件堆最上面的那份取来打印,每次取一份．若有n份文件,且经理是按1,2,…,n的顺序依次交来,问：秘书打印完这n份文件的可能顺序有多少种？     

排序问题的稳定性分析

This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a parameter, what is the new optimal cost？ Given a specific change of a parameter, what is a new optimal solution？ Here, the concern is mainly with the sensitivity analysis for some single-machine and flowshop scheduling problems with polynomial time algorithms. It is shown that, for these problems, the sensitivity analysis results depend on the positions of jobs with changed parameters.     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

机床的最优负荷问题

机床加工中的最优负荷问题是提高经济效益的最重要途径之一 .本文就此问题进行了探索 ,所得出的解法具有一定推广价值 .     

保序回归问题的贝叶斯一致最优解

本文利用鞅方法,探讨了保序回归问题在贝叶斯均方误差意义下最优解的具体形式,而且指出了在特定条件下,其作为估计量具有非常重要的无偏性和有效性.     

一类半正定双对称矩阵反问题的最小二乘解

本讨论了一类半正定双对称矩阵反问题的最小二乘解及其最佳逼近。     

比赛项目排序问题的贪婪算子遗传算法

将比赛项目的排序问题转化为图论问题中的货郎担问题(TSP),利用TSP较为成熟的遗传算法进行求解。这样防止了搜索过程陷入局部最优。针对遗传算法收敛速度慢的特点,对遗传算法进行了改进,引入贪婪交叉算子来加快算法的收敛速度,得到冲突总人次数为8的优良结果。在对算法进行合理性分析时,从理论上论证了算法的优劣。