带有随机准备时间的平行机排序问题

摘要

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

目录

文摘

英文文摘

致谢

第一章 绪论

1.1 排序问题

1.2 近似算法及计算复杂性

1.3 近似算法的最坏情况界

1.4 带维护时间的排序问题

1.5 本文概述

第二章 目标为极小化完工时间总和的期望

2.1 动态P2｜α｜E[Cj]

2.2 静态P2｜α｜E[Cj]

第三章 目标为极小化最大完工时间的期望

3.1 序言

3.2 动态P2｜α｜E[Cmax]

3.3 静态P2｜α｜E[Cmax]

参考文献