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

《在带中断的单机上的随机调度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、王秀军硕士学位论文答辩委员会成员名单姓名职称单位备注韩天雄教授华东师范大学主席汪荣明教授华东师范大学吴述金副教授华东师范大学第一章绪论弗一旱三百比§1．1调度方面的背景介绍1．1．1与本文有关的调度问题介绍本文调度问题研究：有一批无先后处理顺序的工作任务(jobs)需要在一个单处理器(single—machine)中处理，不妨有礼个工作任务，每个任务需要的初始处理时间为五，i=1，2，3，⋯，n(其中工作任务的初始处理时间X是指每个工作任务第一个在单处理器中处理所需的时间)，这扎个任务没有先后顺序，随时可以接受处理器的处理，但在每个时点该处理器只能处理一个工作任务。将n个工作任

2、务用1，2，3，4，⋯，n标记，那么调度问题主要关心的是怎样安排工作任务的处理顺序，使的整个任务的完成时间最短或最优其他的目标函数，可以数学描述为怎样安排策略7r={il，i2，ia，⋯，如)，其中7r为{1，2，3，4，⋯，礼)的一个排列，7r(后)=ik。1．1．2热点调度问题介绍在主流调度理论研究中，通常假定每个工作任务需要处理时间是time-invariant，即这个工作任务需要的处理时间与时间t无关，具体可以参考文献f19】。但是在许多实际情况中，工作任务的所需处理时间是time-varying，即与时间t有关，可以假设在t时刻，它的处理时间是时间t的函数，记为x(t

3、)。虽然与时间无关的工作在某些情况中可能反映或近似反映现实生活(其实很多时候这样假设只是为了计算的方便)，但它的结果精度远远不够，所以在对精度要求更高的今天，很难广泛的运用。但与时间有关的随机调度在现实中有广泛应用，主要体现在消防、金融管理、食品处理和储存、资源分配、军队目标搜索、国家防卫、计算机科学、人工智能和冶金等等领域，所以本文将研究工作任务需要处理时间与时间亡有关的随机调度，显得很有意义和必要。在现实例子中任何推迟工作任务的处理都将影响整个任务的完工状况(从时间、成本或生命财产等等方面)。在最近的二十多年来，往随机调度模型中引入工作任务与时间t有关，越来越受到关注并且在

4、这个领域也有了很多研究成果。在本文的研究模型中，工作任务在时刻t需要的处理时间假设与时间t是线性的(关于时间t是递增的或者递减的，因为等待将增加或者减少工作需要处第一章绪论华东师范大学硕士论文2理的时间或成本)，更多的细节讨论和有关随机调度的研究请参考Cheng，DingandLin(2004)$1Womer(1999)这两篇文章。另外为了处理的方便，经典的调度模型常常假设处理器是不间断的处理完n个工作任务，然而在现实中我们经常发现在某个时刻处理器可能会出现故障(machine-breakdown)，这样会导致处理器处理工作的间断；例如在计算机、制造业、工程提炼中，处理器发生中

5、断是很正常的。最近二十年研究中考虑机器中断的随机调度模型主要分两个方向：(1)第一个是preemptive-resumemodel，即当机器中断恢复以后，整个先前处理好的任务已经被保存，机器继续从中断工作时开始处理。有关研究请参考文献[6]年fl[23】，Glazebrooke(1984，1987)，Li，BraunaandZhao(1998)，Mittenthaland兄n夕^o秒nc^07．z(1993)，PinedoandRammouz(1988)，以及Qt，YinandBirge(2000a，2000b)等等文章：(2)第二个是preemptive-repeatmode

6、l，即当机器中断恢复以后，机器对刚刚处理过的工作没有保存，需要重新开始处理工作；我们用计算机下载网络资源为例，当网络资源下载一半时，突然计算机死机了(即计算机处理器中断)，您需要重新启动计算机进行资源下载，如果继续前面的一半进行下载，那么它就符合第一个方向(preemptive-resumemodel)；如果我们需要重新从零开始下载，那么它就是第二个方向(preemptive-repeatmodel)：有关方向二的随机调度文章请参考Cai，ZhouandSun(2003，2004)，Cai，WuandZhou(2005，2009)，Frostig(1991)，Glazebroo

7、ke(1991)以及Cheng，T．C．E．，Ding，Q．andLin，B．M．T．等等。上面两个方向都是处理器中断(machine-breakdown)影响工作任务的处理时间，但当同时考虑处理器中断和工作任务的需要处理时间与时间t有关的双重影响时，可能会导致很难找到最优的调度策略。下面举几个在现实生活中受处理器中断和工作任务与时间有关的双重影响的例子；在钢铁厂，炼钢机器可能随时出现故障，在排除故障期间(处理器中断)，铸铁块的温度会下降(-v作任务需要处理时间与时间有关)，它需要机器修理好