📄 texta-12.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" link="#0000FF" vlink="#3399FF" alink="#FF0066">
<div id="Layer1" style="position:absolute; width:711px; height:21px; z-index:1; top: 10px; background-color: #CCCCCC; layer-background-color: #CCCCCC; border: 1px none #000000; left: 26px"><b>|</b><font face="宋体" size="2"><a href="../text1/text1-0.htm">第一章</a></font><b>|</b><font face="宋体" size="2"><a href="../text2/text2-0.htm">第二章</a></font><b>|</b><font face="宋体" size="2"><a href="../text3/text3-0.htm">第三章</a></font><b>|</b><font face="宋体" size="2"><a href="../text4/text4-0.htm">第四章</a></font><b>|</b><font face="宋体" size="2"><a href="../text5/text5-0.htm">第五章</a></font><b>|</b><font face="宋体" size="2"><a href="../text6/text6-0.htm">第六章</a></font><b>|</b><font face="宋体" size="2"><a href="../text7/text7-0.htm">第七章</a></font><b>|</b><font face="宋体" size="2"><a href="../text8/text8-0.htm">第八章</a></font><b>|</b><font face="宋体" size="2"><a href="../text9/text9-0.htm">第九章</a></font><b>|</b><font face="宋体" size="2"><a href="../text10/text10-0.htm">第十章</a></font><b>|</b><font size="2" face="宋体">算法分析<b><font color="#000000">|</font></b>
</font></div>
<pre align="left">
<b><font face="宋体" size="4" color="#FF0033">作业调度满足最优性原理：</font><font face="宋体" size="4" color="#000000">
排列中确定第一个作业后，随着第一个作业的完成，余下的作业排
列仍是一个最优排列。
按某一确定顺序执行情况的好坏，用t=f<font size="2">2</font>-f<font size="2">1</font>来表示。设g(s,t)为
最优作业调度长度。
<i><font face="Arial, Helvetica, sans-serif" color="#FF0033">f1, f2</font></i>为<font color="#FF0033">S</font>调度下，二个处理机<i><font face="Arial, Helvetica, sans-serif">P<font size="2">1</font>, P<font size="2">2</font></font></i> (假如只有2个处理机) 各自完成
<i><font face="Arial, Helvetica, sans-serif">T1, T2,…,</font></i> <i><font face="Arial, Helvetica, sans-serif">Tk</font></i>的时间。
<font color="#FF0033"><i><font face="Arial, Helvetica, sans-serif">f1 </font></i></font>为处理机<font color="#FF0033"><i><font face="Arial, Helvetica, sans-serif">P<font size="2">1</font> </font></i></font>完成<i><font face="Arial, Helvetica, sans-serif" color="#0033CC">T<font size="2">11</font>, …..</font></i><font color="#0033CC"> <font color="#000000">时</font></font><font color="#000000">间</font>
<font color="#FF0033"><i><font face="Arial, Helvetica, sans-serif">f2 </font></i></font>为处理机<font color="#FF0033"><i><font face="Arial, Helvetica, sans-serif">P<font size="2">2</font></font></i></font>完成<i><font face="Arial, Helvetica, sans-serif" color="#0033CC">T<font size="2">12</font>, ….. </font></i><font face="Arial, Helvetica, sans-serif" color="#0033CC"><font color="#000000">时</font></font><font color="#000000">间</font>
<font color="#FF0033">最优调度长度：<i><font face="Arial, Helvetica, sans-serif">g(s, t)</font></i></font>
假定处理机在t时刻之前不能工作，则最优调度长度为
<i><font face="Arial, Helvetica, sans-serif"> g ( {1, 2, … ，n}, 0)</font></i>
<i><font face="Arial, Helvetica, sans-serif" color="#FF0033">g ({1, 2, …, n}, o )</font></i><font color="#FF0033"> </font>= <i><font face="Arial, Helvetica, sans-serif" color="#0033CC">min{ai + g ( {1, 2, …, n} - { i }, bi)} </font></i><font color="#0033CC"> (<i><font face="Arial, Helvetica, sans-serif">1</font></i></font><i><font face="Arial, Helvetica, sans-serif">≤i≤n)</font></i>
如果<font color="#FF0033"><i><font face="Arial, Helvetica, sans-serif">g (Ф, t)</font></i></font> =<i><font face="Arial, Helvetica, sans-serif"> max{ t, o} 和 ai≠0 1≤i≤n</font></i>
<i><font face="Arial, Helvetica, sans-serif" color="#FF0033">g (S, t) </font><font face="Arial, Helvetica, sans-serif">=<font color="#0033CC"> min{ ai + g(S-{i}, bi + max {t - ai, o})}</font></font></i>
因为<i><font face="Arial, Helvetica, sans-serif">f2 - f1 = bi + max{ai,t} - ai = bi + max{t - ai, o}.</font></i>
<font color="#FF0033">可证：</font>对任一对相邻作业i和j, 若有<i><font face="Arial, Helvetica, sans-serif" color="#0033CC">min{bi, aj}≥ min{bj, ai}。</font></i>
则总存在一个最优调度，而且具有这种性质的所有调度有相同的长度。
</font></b></pre>
<table width="732" cellspacing="0" cellpadding="0">
<tr>
<td width="327"> </td>
<td width="271"><a href="../index.htm"><img width="60" height="25" usemap="#MapMap4" border="0" src="../../images/home.gif"></a><a href="../index.htm"><map name="MapMap4"><area shape="rect" coords="42,-34,88,-15" href="text0.htm"><area shape="rect" coords="4,4,55,23" href="textA-index.htm"></map></a></td>
<td width="132"><font face="楷体_GB2312" size="2"><b> <a href="texta-11.htm">上一页</a>
<a href="textA-13.htm">下一页</a> </b></font></td>
</tr>
</table>
<pre align="left"><b><font face="宋体" size="4" color="#000000">
</font></b></pre>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -