m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．     

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

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

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题，在工件具有准备时间的条件下，给出一种新的启发式算法，其最坏性能比不超过2，猜想该算法的紧界是2—2／(m 1)，其中m是机器的台数，证明在3台机器的情况下，该算法的最坏性能比为3／2，且上界是紧的。     

关于工件组的两机自由作业时间表问题

讨论关于工件组的两机自由作业时间表的加工全长问题，无论是对于成组加工情形还是分组情形，该问题都可以被证明是ＮＰ困难的。对于成组加工情形，设计了一个性能比为５／４的近拟算法，该算法生成的时间表作为分组情形的解，性能比仍能保持为５／４。此外，还讨论了如何最优地求解只有一个工件组的情形。     

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

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

一类装配式作业排序问题计算复杂性研究

探讨装配式作业排序问题的计算复杂性，证明了在优化指标为作业排序长度的条件下该问题是ＮＰ－完全问题。     

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

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

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

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

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

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

退化工件误工数的双机自由作业排序问题

探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题,其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是 NP 困难的;然后对最小化加权误工工件数问题给出了一个拟多项式时间算法;最后对几种特殊情形给出了多项式时间算法。     

加工时间服从几何分布的流水车间随机排序问题

为了解决使最长加工时间的数学期望最小、工件的加工时间服从几何分布的两阶段流水车间随机调度问题,采用理论分析的方法,分别研究了两阶段静态随机流水车间和动态随机流水车间工件的最优加工顺序.结果表明:在工件的到达时间均为0的两阶段静态随机流水车间、工件的到达时间不一致的两阶段动态随机流水车间两种情况下,由给出的优先规则的不可中断静态优先策略和不可中断动态优先策略是确定使最长加工时间最小的优先策略,并对算法的最优性进行了证明.该成果对正规目标函数的流水车间随机排序问题的解决具有一定的参考价值和指导意义.     

转盘上的Flow-shop排序问题的复杂性

讨论转盘上的Flow-shop排序问题,当运送不相等且只有一台机器的情况下,转盘上的Flow-shop排序问题是强NP-困难的.     

Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem

As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.     

车间作业调度问题中调度规则算法的设计方法研究进展

 调度规则是解决实际生产中的动态车间作业调度问题的有效方法,但它的效率取决于系统特征、加工条件参数和调度目标,因此没有一个规则在所有的调度环境下都比其他规则要好。综述了调度规则的发展、分类及特点,并对调度规则的设计方法进行总结。介绍了调度规则的设计方法,包括早期使用的手工方法和表现较好的智能方法,给出进化算法、遗传规划和数据挖掘方法,并分析比较了其优缺点。针对调度规则设计方法存在的不足,指出了未来的研究方向。     

工人技能部分柔性的流水车间调度问题

本文针对工人技能部分柔性的流水车间调度问题(FSPPSF),建立了目标为最小化完工时间的FSPPSF模型,利用分支定界法求解给定技能矩阵的FSPPSF(S).针对不同工人技能的柔性度进行计算实验,得出柔性度和相对运行效益率的关系,为决策者如何制定培训新工人方案提供重要依据.     

局部n次积分C-半群与非齐次抽象Cauchy问题

作为强连续半群的推广,积分半群和C-半群进一步丰富了半群理论及应用,解决了强连续算子半群不能处理的某些不适定Cauchy问题。为了寻求积分半群对于解决非齐次抽象Cauchy问题的功效,选取了三类非齐次抽象Cauchy问题,给出了它们的解的定义,并在局部n次积分C-半群的概念和性质的基础上,证明了局部n次积分C-半群对于此类非齐次抽象Cauchy问题解的存在和唯一性条件。     

带运输时间的Flow-shop时间表问题

研究带运输时间的流水作业时间表问题，同一工件在一台机器上完工之后，在另一台机器上开始加工，且运输过程只能由机器R完成，证明在只有两台机器的情况下，该问题是强NP-困难的，并构造一个启发式算法，证明该算法的紧界为2。