带中断的机器随机进一步调度研究
导读：当某个工作在处理器上处理，但机器突然中断，停止工作了，机器修好后继续接着处理之前未完成的工作，本文通过推导出每个工作占据机器时间过程的特征，求出整个任务完工时间的期望和方差，调度工作任务使得整个任务完工时间的期望和方差最小。由本站硕士论文中心整理。
第一章绪论
1.1调度方面的背景介绍
1.1.1与本文有关的调度问题介绍
本文调度问题研究:有一批无先后处理顺序的工作任务(jobs)需要在一个单处理器(sin娜。一。achine)中处理，不妨有n个工作任务，每个任务需要的初始处理时间为茂，i=1,2,3,(其中工作任务的初始处理时间茂是指每个工作任务第一个在单处理器中处理所需的时间)，这n个任务没有先后顺序，随时可以接受处理器的处理，但在每个时点该处理器只能处理一个工作任务。将二个工作任务用1,2,3,4,-},n标记，那么调度问题主要关心的是怎样安排工作任务的处理顺序，使的整个任务的完成时间最短或最优其他的目标函数，可以数学描述为怎样安排策略，其中二为{1,2,3,4,}-}，二}的一个排列.
1.1.2热点调度问题介绍
在主流调度理论研究中，通常假定每个工作任务需要处理时间是time-invariant即这个工作任务需要的处理时间与时间t无关，具体可以参考文献!ls}。但是在许多实际情况中，工作任务的所需处理时间是time-varying，即与时间t有关，可以假设在t时刻，它的处理时间是时间t的函数，记为x(t)。虽然与时间无关的工作在某些情况中可能反映或近似反映现实生活(其实很多时候这样假设只是为了计算的方便)，但它的结果精度远远不够，所以在对精度要求更高的今天，很难广泛的运用。但与时间有关的随机调度在现实中有广泛应用，主要体现在消防、金融管理、食品处理和储存、资源分配、军队目标搜索、国家防卫、计算机科学、人工智能和冶金等等领域，所以本文将研究工作任务需要处理时间与时间t有关的随机调度，显得很有意义和必要。在现实例子中任何推迟工作任务的处理都将影响整个任务的完工状况(从时间、成本或生命财产等等方面)。在最近的二十多年来，往随机调度模型中引入工作任务与时间t有关，越来越受到关注并且在这个领域也有了很多研究成果。在本文的研究模型中，工作任务在时刻t需要的处理时间假设与时间t是线性的(关于时间t是递增的或者递减的，因为等待将增加或者减少工作需要处理的时间或成本)，更多的细节讨论和有关随机调度的研究请参考Cheng, Ding and Lin(2004)和Womer(1999)这两篇文章。
另外为了处理的方便，经典的调度模型常常假设处理器是不间断的处理完n个工作任务，然而在现实中我们经常发现在某个时刻处理器可能会出现故障(machine-breakdown )，这样会导致处理器处理工作的间断;例如在计算机、制造业、工程提炼中，处理器发生中断是很正常的。最近二十年研究中考虑机器中断的随机调度模型主要分两个方向:
(1)第一个是preemptive-resume model，即当机器中断恢复以后，整个先前处理好的任务己经被保存，机器继续从中断工作时开始处理。有关研究请参考文献[6」和[23]，Glazebrool}e(1984,1987)，Li, Brauna and Zhao(1998)，MittenthaL and Raghavachari(1993)，Pinedo and Rammouz(1988)，以及Qi, Yin and Birge(2000a,2000b)等等文章;
(2)第二个是preemptive-repeat model，即当机器中断恢复以后，机器对刚刚处理过的工作没有保存，需要重新开始处理工作;我们用计算机下载网络资源为例，当网络资源下载一半时，突然计算机死机了(即计算机处理器中断)，您需要重新启动计算机进行资源下载，如果继续前面的一半进行下载，那么它就符合第一个方向(preemptive-resume model);如果我们需要重新从零开始下载，那么它就是第二个方向(preemptive-repeat model);有关方向二的随机调度文章请参考Cai, Zhou and S二二(2003,2004)，Cai, Wu and Zhou(2005, 2009)，Frostig (1991)，Glazebroolre(1991)以及Cheng, T.C.E., Ding, Q. and Lin, B.M.T.等等。
上面两个方向都是处理器中断(machine-breakdown )影响工作任务的处理时间，但当同时考虑处理器中断和工作任务的需要处理时间与时间t有关的双重影响时，可能会导致很难找到最优的调度策略。下面举几个在现实生活中受处理器中断和工作任务与时间有关的双重影响的例子;在钢铁厂，炼钢机器可能随时出现故障，在排除故障期间(处理器中断)，铸铁块的温度会下降(工作任务需要处理时间与时间有关)，它需要机器修理好以后重新进行加热，这样它就受到机器中断和工作任务恶化的双重影响，这时必然增加铸造时间;在军事行动中，军事雷达或者反导弹系统需要搜索敌军目标，但由于天气环境越来越恶劣、敌军反雷达系统的干扰和雷达可能遭遇突然故障的双重影响，这样增加了搜索目标时间;在消防中，任何延迟救火时间和消防设备的故障都会加重人民财产的损失，甚至严重威胁人民的生命。在人工智能中，推迟处理工作可能使得工作任务需要处理时间与原来相比减少了，因为该智能机器有学习能力;在食品发酵中，随着时间的推移发酵需要的时间越来越少了;农场的粮食干燥，也与前者一样。在这些例子中，工作任务的处理时间与时间相关和机器的中断都改变了工作任务需要的完工时间，可以看出与经典模型相比，在双重影响下寻找使整个工作任务完工时间最短或其他目标函数最优策略就变得很难。
1.2本文的研究内容
本文主要探讨在时刻t}。个工作任务需要处理时间与时间t有关，并且把处理器中断也考虑进来，在双重影响下统筹安排这n个工作任务的处理顺序，使得整个工作任务的期望完工时间最短或者整个工作任务完工时间的方差最小，可以数学描述为怎样安排策略二=lZl 22} 23 } 2.aI，其中二为{1,2,3,4,---,n}的一个排列，使得整个任务的期望完工时间最短或者整个工作任务完工时间的方差最小。另外特殊的是，本文主要关注处理器的中断是preemptive-resume以及工作任务需要处理时间与时间t是线性递减的。这篇文章的主要内容安排为:
(1)第二章讲述模型建立的过程，从经典的简单模型一步一步到本文建立的新型模型，可以看出新型模型与经典的简单模型的联系与区别;以及推导出占据过程的数学表达式，为下一章求占据过程的数字特征服务;
(2)第三章重点证明当机器中断时间和机器正常运行时间都服从指数分布时，对占据时间过程拉普拉斯变换推导出占据过程的期望和方差的数学表达式;
(3)第四章运用占据过程与整个工作任务完工时间的特殊关系推导出推导出整个工作任务的期望完工时间}' }Cmax}的数学表达式;怎样调度才能使整个工作任务的期望完工时间最小化以及怎样解决使整个工作任务完工时间的方差最小化问题，最后我们惊奇的发现，与经典模型的结论进行比较，可以看出经典模型是本文新型模型的特殊情况。
参考文献
[1] Alidaee,B.,Womer,N.K.,1999."Scheduling with time dependent processing times:Review and extensions." Journal of the Operational Research Society50, 711一720.
[2]Bachman,A.,Cheng,T.C.E.,Janiak,A.,Ng,C.T.,2002a. "Scheduling start time depen- dent jobs to minimize the total weighted completion time." Journal of the O}era- tional Research Society 53(6), 688-693.
[3]Bachman,A.,Janiak,A.,Kovalyov,M.Y.,2002b."Minimizinghttp://sblunwen.com/dxgcsslw/ the total weighted comple- tion time of deteriorating jobs." Information Processing Letters 810),81一8!}
[4]Cai X.,Wu X,and Zhou X.2005"scheduling deteriorating jobs on a single machine subject to breakdowns.''
[5] Browne,S.,Yechiali,U.,1990." Scheduling deteriorating jobs on a single processor." Op-erations Research 3.
[6] Cai X.and Zhou X.2000." Asymmetric earliness-tardiness scheduling with exponential processing times on an unreliable machine." Annals of Operations Research, 98, 313-331.
[7]Cai,X.and Zhou,X.2003."Stochastic scheduling with preemptive-repeat machine breakdowns to minimize the expected weighted flowtime，，Probability in the engi- veering and Informational Sciences,l7,}67-185
[9] Alidaee,B.,and Womer,N.K.1999." Scheduling with time dependent processing times:Review and extensions".Journal of the Operational Research Society,50,711- 720.
[10] Cai,X.,Sun,X.and Zhou,X.2004."Stochastic scheduling subject to machine break-downsahe preemptive-repeat model with discounted reward and other criteria”Naval Research Logistics,51,800-817.
[11] Browne,S.1988." Optimal Dynamic Operating Policies for Cyclic-Type(queues".Unpublished Ph.D.Dissertation,New York University,New York.
[12」 Browne,S.,and U.Yechiali.1989."Dynamic Priority Rules for Cyclic Type (queues". Adv.Appl.Prob.10,432-450.
[13J Browne,S.,and U.Yechiali."Scheduling deteriorating jobs on a single processor".御- eration Reearch.Vo1.38,No.3,May-June 1990.
[14] F}ostig,E.1991."A note on stochastic scheduling on a single machine subject to break- down the preemptive-repeat model." Probability in the engineering and Informational Sciences,
[15J Glazebrook,K.D.1991." On nonpreemptive policies for stochastic single machine scheduling with breakdowns." Probability in the engineering and Informational Sciences, 5, 77-87.
摘要 6-7
ABSTRACT 7
第一章 绪论 9-12
1.1 调度方面的背景介绍 9-11
1.2 本文的研究内容 11-12
第二章 模型建立 12-18
2.1 简单模型 12-14
2.2 新型模型 14-18
第三章 占据过程的................... 18-22
3.1 基本引理和定理 18-20
3.2 占据过程的期望和方差 20-22
第四章 最优策略 22-26
4.1 整个完工时间期......................22-24
4.2 整个完工时间方差最小的策略 24-26
结束语 26-27
附录Ⅰ 27-32
附录Ⅱ 32-34
参考文献 34-38
致谢 38-39
您可能有工程硕士学位论文方面的购买需求，请到硕士论文频道选取：