退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

哈明距离下费用受限制约束最小支撑树反问题

讨论了瓶颈型哈明距离下费用受限制的约束最小支撑树反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型哈明距离来衡量修改的费用,且修改的总费用不超过给定的上界.利用转化的思想,给出瓶颈型哈明距离下费用受限制的约束最小支撑树反问题的多项式算法及证明.     

线性相补问题的递推算法

本文讨论增加变量对的线性相补问题,给出了一个充分利用原线性相补问题解的信息的有效的递推算法。     

一类加工时间依赖资源的排序问题

讨论一类工件的加工时间受资源约束的单机排序问题1|pj=bj-ajuj,∑uj≤U|∑ωjCj，给出它的最优解的两个性质，证明该类问题是NP-难的。     

一类具有维护和共同工期的单机排序问题

主要讨论了带有维护和共同工期的单机排序问题.工件的实际加工时间是与该工件在排序中的加工位置相关的.目标函数是共同工期相关的费用、提前完工的工件存储费用和不能在工期内完成的工件的惩罚费用之和.最后给出了多项式动态规划算法.     

处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断，处理机是恒速机且处理机具有准备时间的排序问题，对一般情况的LPT排的界做了改进，同时对m＝2的情况给出了一个与处理机加工速度有关的LPT排序的界。     

一个改进的Separate算法及其应用

关联规则的挖掘是一个重要的数据挖掘问题,在关联规则的挖掘过程中加入约束条件,是实现用户参与挖掘的一种方式,这样得到的规则是用户所真正关心的,而Separate算法便是这类算法的代表.先对Separate算法进行了改进,从而进一步提高其性能,然后用改进后的算法挖掘实际应用中的一个实例,最后对挖掘结果给出相关决策解释.     

具有工期限制的退化工件单机排序问题

工件具有退化效应的排序问题最近几年受到人们越来越多的关注。所谓具有退化效应的工件是指在排序中,工件的开工时间越晚其实际的加工时间就越长。讨论了一类具有工期限制的线性退化工件单机排序问题。其中线性退化工件指的是工件的实际加工时间是线性增长的函数。文中工件的实际加工时间不是固定不变的,是该工件的开始加工时间的单增函数。目标函数是使完工时间,提前完工时间和误工时间的加权和最小。给出了多项式时间的最优算法。     

突发事件应急管理中的中断-继续随机排序模型

给出一个突发事件应急管理中的中断-继续随机排序模型,其中突发事件的开始时间和持续时间都是随机的.极小化的目标函数是期望加权完工时间和、期望加权误工时间和及期望加权误工工件数.对目标函数是期望加权完工时间和的问题,证明了在相融条件下,问题是多项式可解的;如果突发事件的开始时间是均匀分布,WSPT规则是问题的最优策略;对突发事件的开始时间是确定的特殊情况,给出一个动态规划算法.对目标函数是期望加权误工时间和及期望加权误工任务数的问题,证明了在相融条件下,它们都是多项式可解的.     

整凸二次规划

本文给出了一种求解整凸二次规划的分枝定界法，该算法把松弛问题转化为线性互补问题，由于求解线性互补问题时，充分地利用了前一分枝点所对应的线性互补问题解的信息，从而地减少了计算量。