具有优先约束的单机随机排序问题

摘要：

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件问的约束为申并有向图.证明了模块M的p因子最大初始集合,中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序.从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.

关键词：单机排序、随机故障、串并有向图、树优先约束、最大家庭树

所属期刊栏目：39

分类号：O22;TP3

资助基金：国家自然科学基金重点项目7043100;国家自然科学基金创新群体项目60521003;国家科技支撑计划项目Z006BAH02A09

在线出版日期：2009-06-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：126-137