打字猴:1.700495692e+09
1700495692 这使劳勒和伦斯特拉这样的研究者面临一个不可抗拒的问题:究竟什么比例的调度问题是难解的?在塞尔默·约翰逊初创调度理论的20年后,对个人解决方案的探索已变成一项更浩大、更雄心勃勃的研究:通过这一探索可以纵观整个调度理论。
1700495693
1700495694 研究人员发现,即使是对调度问题进行最微妙的改变,也经常会跨越易处理和不易处理之间细致而又不规则的分界线。例如,当所有任务都具有相同权值时,穆尔算法就最大限度地减少了过期任务(或腐烂水果)的数量。但如果一些任务比其他更重要,这个问题就变得难解,没有算法可以很轻松地提供最佳安排。同样,如果某些任务必须等到某个时间点才能开始,那几乎所有的安排都会陷入难解的境地。在收垃圾车到来的前一天晚上才能把垃圾倒出去,这可能是一个合理的市政规章,但它会让你的日程安排变得棘手。
1700495695
1700495696 对调度理论边界的绘制一直持续到今天。最近的一项调查表明,在所有问题中大约有7%是仍然未知的,就是调度的未知领域。然而,在我们所理解的93%的问题中,现实也并不是很理想:只有9%的问题可以被有效解决,其他的84%已经被证明是难解的。[2]换句话说,大多数的调度问题都没有现成的解决方案。如果你觉得很难完美地管理你的日程,那也许因为实际上这就是难以管理的。尽管如此,我们讨论过的算法往往是解决那些困难问题的起点——也许不是那么完美的,但至少是可以预期的。
1700495697
1700495698 [1]我们将在第8章详细研究“难解性”这一问题。
1700495699
1700495700 [2]事实也并非数据显示的那么糟糕,因为这包括多机调度问题,更像是管理一组员工而不是管理你的日历。
1700495701
1700495702
1700495703
1700495704
1700495705 算法之美:指导工作与生活的算法 [:1700494150]
1700495706 算法之美:指导工作与生活的算法 放弃所有:抢占和不确定性
1700495707
1700495708 谚语
1700495709
1700495710 种树最好的时间要么是20年前,要么就趁现在。
1700495711
1700495712 到目前为止,我们只考虑了使调度变得更加困难的因素。但有一个转折可以使它更容易:能够中途停止一个任务的执行切换到另一个任务。“抢占”这个属性最后会戏剧性地改变整个游戏。
1700495713
1700495714 如果有些任务不能在一个特定的时间开始,那么将最大延迟(为咖啡店的顾客服务)或完工时间(为了快速缩短你的待办事项列表)最小化都越过了难解性那条线。但一旦允许抢占,那就还有其他高效的解决方案。在这两种情况下,经典的策略——最早到期日和最短加工时间,只要进行一个相当简单的修改,就是表现最好的。当任务开始时,将该任务与正在进行的任务进行比较。如果你运用最早到期日原则,新的任务甚至比现在的任务截止日期更早,那么就转换档位,否则它将停滞不前。同样,如果你运用最短加工时间原则,新的任务可以完成的比目前的任务更快,那么先暂停处理这一个,否则就继续你正在做的事情。
1700495715
1700495716 现在,如果一周的生意好,一家机械工厂可能会知道在接下来的几天里他们所期望的一切,但是我们大多数人通常都是盲目的,至少部分人是这样。例如,我们可能不确定我们何时才能启动一个特定的项目。(某人会就某个问题给我一个确定的答案吗?)在任何时候,我们的电话或电子邮件都可能弹出一个新任务的消息,添加到我们的原议程之中。
1700495717
1700495718 事实证明,即使你不知道什么时候会开始工作,最早到期日和最短加工时间仍然是最佳的策略,这能够保证你在面对不确定性时表现出最佳状态(平均来说)。如果在不可预知的时刻,你的桌子上突然出现一堆任务,最小化最大延迟仍然是最早到期日的抢先版最佳策略——如果新来的任务比手头上的截止日期更早的话,那就转而执行这一新任务,如果不是就忽略它。同样,最短加工时间的抢先版策略(比较当前任务的剩余完成时间和完成新任务所需要的时间)仍然是最小化完成总时间的最佳方法。
1700495719
1700495720 事实上,在面对不确定性时,最短加工时间的加权版本是一种最通用的调度策略。它提供了一个简单的时间管理方法:每接到一件新工作时,通过其将耗费的时间来对其进行重要性的划分。如果该重要性高于当前正在执行的任务,就切换到新任务,不然就坚持当前任务。该算法是调度理论最接近“万能钥匙”的地方,最佳策略并不只是为了解决一个问题,而是许多问题。在一定条件下它所要最小化的并不只是加权完工时间的总和,如我们所期待的,也是超期任务的权值以及这些任务的加权超时数的总和。
1700495721
1700495722 有趣的是,如果我们提前知道任务的开始时间和持续时间,想要优化所有其他的指标也都是难解的。所以,调度不确定性的影响揭示了一些违反直觉的东西:在有些情况下,透视是一种负担。即使拥有完全的预知,寻找完美的调度计划实际上也许也是不可能的。相比之下,驻足思考,工作来时反应灵敏,也许不能给你想象中完美的调度执行,但这是你可以做的最好的一件事,也最容易计算。这会带来一些安慰。作为商业作家和编码员的杰森·弗瑞德曾说:“直到做出一个万能计划,你才会继续吗?用‘猜测’代替‘计划’,并放轻松。”当未来充满迷雾的时候,原来你不需要日程表,只需要一个待办事项清单。
1700495723
1700495724
1700495725
1700495726
1700495727 算法之美:指导工作与生活的算法 [:1700494151]
1700495728 算法之美:指导工作与生活的算法 抢占并不是随意的:关联转换
1700495729
1700495730 谚语
1700495731
1700495732 走的越急,就落得越远。
1700495733
1700495734 埃伦·厄尔曼
1700495735
1700495736 程序员不说话,因为他们不能被打断……与其他人同步(电话、蜂鸣器和门铃)只能意味着打断思路。中断就意味着会发生一些错误。你不能中途下车。
1700495737
1700495738 所以,调度理论还是告诉人们一个合理而又鼓舞人心的道理。解决许多调度问题时,有最简单和最优算法,而要解决的这些问题都已经非常接近我们在日常生活中遇到的情况。但是,在现实世界中,当涉及实际操作的单机调度问题时,事情就会变得复杂。
1700495739
1700495740 首先,人们和计算机操作系统都面临着一个奇怪的挑战:正在进行调度的机器和将要进行计划的机器是同一个。要想理顺你的待办事项清单上的项目,需要你的待办事项列表本身进行优先处理和调度。
1700495741
[ 上一页 ]  [ :1.700495692e+09 ]  [ 下一页 ]