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

Stochastic Single Machine Scheduling Problem with Precedence Constraints

作　　者：闫杨[1] 汪定伟[1] 王大志[1] 王洪峰[1] 

机构地区：[1]东北大学系统工程研究所,辽宁沈阳110004

出　　处：《数学的实践与认识》2009年第5期126-137,共12页Mathematics in Practice and Theory

基　　金：国家自然科学基金重点项目(7043100);国家自然科学基金创新群体项目(60521003);国家科技支撑计划项目(2006BAH02A09)

摘　　要：讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.The stochastic single machine scheduling problem that the processing times of the jobs are constants and the machine is subject to a sequence of stochastic breakdowns was considered, the objective function is to minimize the mean weighted sum of completion times. Two kinds of precedence constrains are addressed. In the first one, it is assumed that jobs are subject to series-parallel diagraph precedence constraints. We apply Lawler＇s algorithm which is used to solve total weighted completion time single machine with constrains of series-parallel digraph to the condition that ;stochastic breakdowns are taken into account by proving the following theorem. Jobs in the ρ-maximal initial set I of module M should be processed prior to other jobs in module M, and the schedule is the optimal if the jobs in I arenrt be preempted by the jobs in N／I. In the second one, it is assumed that jobs are subject to outtree precedence constraints. Under the condition that stochastic breakdowns are taken into account, jobs in the maximal family tree should be processed prior to other jobs in family tree and the optimal schedule is obtained if jobs aren＇t be preempted by the other jobs, and the optimal algorithm is given.

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

分 类 号：O223[理学—运筹学与控制论] O224[理学—数学]