1700495670
当某个任务在另一个任务完成之前无法启动时，调度理论家称之为“优先约束”。操作研究专家劳拉·艾伯特·麦克莱表示，她清楚地记得这一原则在她自己家里不止一次地产生了作用。“如果你能看到这些东西，这可能是有用的。当然，安排好三个孩子的一天，有很多需要统筹的事务……孩子们必须先吃完早餐，我们才能出门，如果我不记得递给他们勺子，那他们就不能吃早餐。有时，你忘记做一件小事会导致整个任务的延迟。在调度算法方面，仅仅知道这是什么并使其保持运转就已经大有裨益了。这就是我每天如何安排事情的。”
1700495671
1700495672
在1978年，调度理论研究者简·卡雷尔·伦斯特拉使用了相同的原理帮助他的朋友吉恩搬到伯克利的新家。“吉恩正在拖延一些事，这些事是必须在我们开始其他紧急事情之前就完成的。”伦斯特拉回忆说，他们需要退还一辆面包车，但又需要用这辆车运送一台设备，而又需要用这台设备来修理公寓里的东西。这个修理的任务没那么紧急（因此它被推迟），但换车是很紧急的。伦斯特拉说：“我向他解释道，应该考虑到前任务更加紧急。”伦斯特拉是调度理论的中心人物，因此他有能力给他的朋友提供这个建议，这也带来了特别有趣的讽刺意味。这是一个由优先约束引起的优先级反转的标准案例。可以说，20世纪最优秀的优先约束专家就是他的朋友尤金“吉恩”劳勒。
1700495673
1700495674
[1]具有讽刺意味的是，探路者号的软件团队负责人格伦·里夫斯将该问题归结于“截止日期压力”的错误，并认为在开发过程中修复这个问题被认为是“较低优先级”。因此，其根本原因在某种程度上来说，就是镜像问题本身。
1700495675
1700495676
1700495677
1700495678
1700495680
算法之美：指导工作与生活的算法 减速带
1700495681
1700495682
劳勒考虑到他一生大部分时间都在思考如何最有效地完成一系列的任务，他便对自己的职业生涯采取了一种有趣的迂回路线。他在佛罗里达州立大学学习数学，后于1954年在哈佛大学攻读研究生，但在获得博士学位前便离开。后又在法学院、军队和机械加工车间工作，1958年他回到哈佛大学，得到博士学位后他开始在密歇根大学工作。1969年，在休假期间他去了伯克利，在一场声名狼藉的反越南战争的抗议中被逮捕。次年，他成为加州大学伯克利分校的一名教师，并获得了计算机科学系的“社会良知”的美誉。他于1994年去世，此后计算机协会设立了劳勒奖，表彰那些体现出计算机科学人道主义潜力的人。
1700495683
1700495684
劳勒的优先约束理论的第一次调查表明，它们应用起来十分容易。例如，采取最早到期日算法将一组任务的最大延迟量进行最小化。如果你的任务有优先约束，那只会使事情更加棘手——如果有些任务必须在其他任务之后完成，那你就不能简单地按照到期日的先后顺序来安排任务。但在1968年，劳勒证明了只要你按照从后往前的顺序建立时间表就没有问题：只看跟其他没有依赖关系的任务，并把到期日最后的任务排在日程表的最后。然后重复这一过程，每一步都只考虑那些不作为其他（还未做安排的）任务完成前提的任务。
1700495685
1700495686
但当劳勒更深入地考虑优先约束时，他发现了一些奇怪的问题。我们所看到的是，如果你想尽可能快地从你的待办事项列表中理清尽可能多的项目，最短处理时间算法就是最佳策略。但是，如果某些任务有优先约束，便没有一个简单或明显的调整原则。虽然这看起来像一个基本调度问题，但无论是劳勒还是其他任何研究人员似乎都没能找到一个有效的解决方法。
1700495687
1700495688
然而，事实比这还糟。在那之后不久，劳勒自己也很快发现这一问题属于大多数计算机科学家认为没有行之有效的解决办法的范畴——在该领域被称为“难解性”[1]。影响调度理论发展的这第一个减速带就是一个难以逾越的障碍。
1700495689
1700495690
正如我们看到的，在“三倍或无”（要么赢三倍，要么全部输光）的情况下，最优停止理论并没有圣人的指导，每一个问题也并不都能用一个正式答案表达。在调度问题上，其定义就很清楚地表明，每一组任务和约束都有一些最好的调度安排，所以本质上调度问题并不是不可回答的，但它可能没有简单直接的算法帮你在一个合理的时间量里的找到最优安排。
1700495691
1700495692
这使劳勒和伦斯特拉这样的研究者面临一个不可抗拒的问题：究竟什么比例的调度问题是难解的？在塞尔默·约翰逊初创调度理论的20年后，对个人解决方案的探索已变成一项更浩大、更雄心勃勃的研究：通过这一探索可以纵观整个调度理论。
1700495693
1700495694
研究人员发现，即使是对调度问题进行最微妙的改变，也经常会跨越易处理和不易处理之间细致而又不规则的分界线。例如，当所有任务都具有相同权值时，穆尔算法就最大限度地减少了过期任务（或腐烂水果）的数量。但如果一些任务比其他更重要，这个问题就变得难解，没有算法可以很轻松地提供最佳安排。同样，如果某些任务必须等到某个时间点才能开始，那几乎所有的安排都会陷入难解的境地。在收垃圾车到来的前一天晚上才能把垃圾倒出去，这可能是一个合理的市政规章，但它会让你的日程安排变得棘手。
1700495695
1700495696
对调度理论边界的绘制一直持续到今天。最近的一项调查表明，在所有问题中大约有7%是仍然未知的，就是调度的未知领域。然而，在我们所理解的93%的问题中，现实也并不是很理想：只有9%的问题可以被有效解决，其他的84%已经被证明是难解的。[2]换句话说，大多数的调度问题都没有现成的解决方案。如果你觉得很难完美地管理你的日程，那也许因为实际上这就是难以管理的。尽管如此，我们讨论过的算法往往是解决那些困难问题的起点——也许不是那么完美的，但至少是可以预期的。
1700495697
1700495698
[1]我们将在第8章详细研究“难解性”这一问题。
1700495699
1700495700
[2]事实也并非数据显示的那么糟糕，因为这包括多机调度问题，更像是管理一组员工而不是管理你的日历。
1700495701
1700495702
1700495703
1700495704
1700495706
算法之美：指导工作与生活的算法 放弃所有：抢占和不确定性
1700495707
1700495708
谚语
1700495709
1700495710
种树最好的时间要么是20年前，要么就趁现在。
1700495711
1700495712
到目前为止，我们只考虑了使调度变得更加困难的因素。但有一个转折可以使它更容易：能够中途停止一个任务的执行切换到另一个任务。“抢占”这个属性最后会戏剧性地改变整个游戏。
1700495713
1700495714
如果有些任务不能在一个特定的时间开始，那么将最大延迟（为咖啡店的顾客服务）或完工时间（为了快速缩短你的待办事项列表）最小化都越过了难解性那条线。但一旦允许抢占，那就还有其他高效的解决方案。在这两种情况下，经典的策略——最早到期日和最短加工时间，只要进行一个相当简单的修改，就是表现最好的。当任务开始时，将该任务与正在进行的任务进行比较。如果你运用最早到期日原则，新的任务甚至比现在的任务截止日期更早，那么就转换档位，否则它将停滞不前。同样，如果你运用最短加工时间原则，新的任务可以完成的比目前的任务更快，那么先暂停处理这一个，否则就继续你正在做的事情。
1700495715
1700495716
现在，如果一周的生意好，一家机械工厂可能会知道在接下来的几天里他们所期望的一切，但是我们大多数人通常都是盲目的，至少部分人是这样。例如，我们可能不确定我们何时才能启动一个特定的项目。（某人会就某个问题给我一个确定的答案吗？）在任何时候，我们的电话或电子邮件都可能弹出一个新任务的消息，添加到我们的原议程之中。
1700495717
1700495718
事实证明，即使你不知道什么时候会开始工作，最早到期日和最短加工时间仍然是最佳的策略，这能够保证你在面对不确定性时表现出最佳状态（平均来说）。如果在不可预知的时刻，你的桌子上突然出现一堆任务，最小化最大延迟仍然是最早到期日的抢先版最佳策略——如果新来的任务比手头上的截止日期更早的话，那就转而执行这一新任务，如果不是就忽略它。同样，最短加工时间的抢先版策略（比较当前任务的剩余完成时间和完成新任务所需要的时间）仍然是最小化完成总时间的最佳方法。
1700495719
[
上一页 ]
[ :1.70049567e+09 ]
[
下一页 ]