在带中断的单机上的随机调度

论文摘要

本文主要研究随机调度n个无先后处理顺序的工作任务（没有哪个工作任务必须要在其他工作任务被处理之前处理完）,使得整个任务完工时间的期望或者方差最小。每个工作任务随着时间的流逝,工作任务需要处理时间与时间是相关的,我们这里主要假设工作任务的需要处理时间与时间是线性的（线性递减或者渐近线性递减的）；并且考虑单处理器是preemptive-resume breakdown,即考虑处理器在工作过程中可能中断,当某个工作在处理器上处理,但机器突然中断,停止工作了,机器修好后继续接着处理之前未完成的工作,与实际相符我们假设系统正常运行时间up-time和停工时间down-time都服从指数分布。我们知道在经典理论中,都假设机器是连续不间断的工作的,整个工作任务的完工时间的期望和方差可以通过指数化策略进行最小化；但是当涉及到机器是可能中断的和每个任务需要的处理时间是随着时间线性变化时,那么结论会怎么样呢?还可以运用指数策略最优调度一批工作任务吗?本文通过推导出每个工作占据机器时间过程的特征,求出整个任务完工时间的期望和方差,调度工作任务使得整个任务完工时间的期望和方差最小。最后我们惊奇地发现经典调度的指数策略同样适用于我们的调度问题,即指数策略调度使整个任务完工时间的期望最小与处理器是否带中断没有任何关系,但这样的指数策略不能使整个任务完工时间的方差最小。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 调度方面的背景介绍
• 1.2 本文的研究内容
• 第二章 模型建立
• 2.1 简单模型
• 2.2 新型模型
• 第三章 占据过程的数字特征
• 3.1 基本引理和定理
• 3.2 占据过程的期望和方差
• 第四章 最优策略
• 4.1 整个完工时间期望最小的策略
• 4.2 整个完工时间方差最小的策略
• 结束语
• 附录Ⅰ
• 附录Ⅱ
• 参考文献
• 致谢