论文部分内容阅读
本文研究了带有随机准备时间的两台同型平行机离线排序问题。假设系统中有一台机器带有一个在0时刻随机发生的机器准备时间，其持续时间α或者为0或者为a，并且α=a的概率为q。目标是极小化总完工时间的期望以及极小化最大完工时间的期望。
文章分别考虑了动态和静态两种不同类型的算法。对于极小化总完工时间问题P2｜α｜E[∑Cj]，分别设计了动态和静态的最优算法。对于极小化最大完工时间问题P2｜α｜E[Cmax]，首先证明了动态LPT算法的最坏情况界为7/6，接着给出了静态M-LPT算法，并证明其最坏情况界为