一类随机绝对超前-延误惩罚单机排序

研究在一台随机发生故障的机器上加工n个具有同一工期的工件,使得所谓绝对超前-延误惩罚的数学期望最小的调度问题.详细地讲,问题中的目标测度是最小化完工时间与公共工期之绝对偏差和的数学期望.我们在机器的工作时间服从指数分布的条件下分中断-恢复型问题和中断-重复型问题进行研究(对于中断-重复型要求故障时间服从指数分布或是一个常数).主要工作如下:(1)问题规划和预备知识.建立支持后续工作的定义,关系和事实.特别地,证明了一个加工时间为t的工件的完工时间与任一工期之绝对偏差的数学期望是关于变量t的半V型函数;(2)最优解的性质.给出了最优解的几个特征.最重要的是,证明了最优解具有半V型性质;(3)算法.讨论了几个关于求所研究问题最优解的计算问题.