带有扩充链优先约束工件的分批排序问题

提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。     

关于问题1|chains,B|Cmax的多项式算法

对带有"扩充链"优先约束的分批排序问题进行了研究,其目标函数为最大完工时间.优先约束为:在一个"扩充链"上包含有n个工件,另外有m个孤立点工件(即工件之间无任何优先约束).讨论了B=2时问题的最优算法,把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为O(n4)的多项式算法.     

带有优先约束的分批排序问题

对工件带有优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：有一个树上包含有n个工件,其余的m-1条链上的工件数总和为常数,且工件的加工时间不限制．对于此种情况,给出了一个多项式时间算法．     

三台平行机上四个约束链的排序问题

考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.     

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

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

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

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

加工时间具有学习效应的链约束单机排序问题

研究了工件的加工时间具有学习效应的链约束单机排序问题,在链可中断和不可中断两种情况下,均给出了目标函数为极小化最大完工时间的多项式算法。     

具有加工顺序约束和非对称模糊加工时间的工期指派调度方法

研究了工件加工时间是非对称模糊数、工件间具有优先加工顺序约束、目标函数为极小化提前完工惩罚和拖期完工惩罚和的均值的单机工期指派调度优化问题.证明了当模糊加工时间具有相同宽度比、优先加工约束关系为树状约束时,该问题是多项式可解的.进一步,当优先加工顺序为一般约束时,基于线性规划松弛技术,设计了近似比为2的近似算法.      

一类安装时间和加工时间受资源约束的成组排序问题

讨论了安装时间和加工时间同时受资源约束的单机成组排序问题．目标函数为在满足最大完工时间限制条件下极小化安装时间消耗资源量与工件消耗资源量的总和．在讨论了问题若干性质基础上，给出了一个最优多项式算法，并用数值例子作了说明．     

基于带宽和时延约束的服务质量任播路由算法

为在满足带宽需求的前提下找到时延最短的任播路径集合,研究基于带宽和时延两个约束度量的服务质量任播路由算法.为解决带宽和时延约束问题,提出一个适用于该非确定性多项式问题的多项式时间近似优化算法.仿真结果表明,当网络规模增加或客户带宽需求较大时,该文算法时延增加相对较小,因此具有较好的可扩展性和健壮性.与包括最短路径优先任播路由算法和最大带宽优先任播路由算法的启发式算法相比,在带宽受限大型网络中该文算法具有更好的性能优势.     

两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

基于准时制的时间成本双目标作业调度优化

提出了一种基于混合遗传算法的以生产周期和生产成本为优化目标的作业调度方法，该方法采用Giffler-Thompson启发式调度算法产生活动的调度，基于工序编码的染色体决定了工序调度的优先级，在启发式调度算法产生的冲突集合中，根据工序的优先级选择下一步安排加工的工序，混合遗传运算在全全局范围内搜索具有最优调度工序优先级的染色体，同时，在GifflerThompson的启发式算法中，采用了反向调度的策略，即从工件的交货期开始，先安排最后一道生产工序，然后依次安排前一道生产工序，直到工件的第一道工序调度完毕，形成一个完整的调度方案，在算法中，不仅考虑了工件的生产周期和多个工艺计划，而且考虑了库存费用和加工费用，设计了基于生产周期和生产成本的双目标适应度函数，算例结果表明该方法是可行的。     

平行机上有优先约束的工件的排序问题

考虑有优先约束的单位工件在m台同型机上的排序问题，目标函数是使工件的完工时间之和最少，当机器的台数不确定时这个问题已经得到了解决．该文中指出当机器的台数确定为m(m≥3)时该问题是NP-完备的。     

有模机配合约束的平行机台调度方法

所描述的问题为在平行机台上具有单一模具约束的调度问题,以实现最小化拖期和为目标·描述了该问题的数学模型,并提出了如下的启发式算法,依据模具成组构成工作表,在对工作指派时根据一定条件允许改变工作的指派顺序,最后运用启发式算法ＮＢＲ(ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ)对调度方案进行局部调整以减少拖期和·通过一个应用实例,测试了该算法的有效性·     

单机分族分批排序的最小误工个数问题

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。