1700495534
算法之美：指导工作与生活的算法 05 时间调度理论 要事先行
1700495535
1700495536
安妮·迪拉德
1700495537
1700495538
我们度过每一天的方式，自然就是度过一生的方式。
1700495539
1700495540
尤金·劳勒
1700495541
1700495542
“我们为什么不写一本关于时间调度理论的书呢？”我问，“不应该花太多时间！”写作，就像发动战争，其中常常包含严重的计算错误。15年后，其中的日程安排仍然未执行完。
1700495543
1700495544
现在是周一早晨，你的日程表上还有一大堆任务等着去完成。有些任务只有在其他人完成之后你才能开始（只有在洗碗机内的碗碟被拿出后才能再次放碗碟进去），有些只能在规定的时间开始（如果你在周二晚上之前将垃圾倒在路边，邻居们就会投诉）。有些任务迫在眉睫，有些没有时间要求，有些处于两者之间，比较灵活。有些任务时间紧迫，但没那么重要。有些很重要，但并没那么紧迫。你也许会想起亚里士多德的这句话——“重复的行为造就了我们”，这种行为可能是拖地、与家人共度更多时光、准时发传真，或者学法语。
1700495545
1700495546
所以，我们该怎么做，什么时候做，以什么样的先后顺序做？人生就是在等待中度过。
1700495547
1700495548
虽然我们总能找到一些方式安排我们每天要做的事情，然而我们似乎并不认为我们善于安排这些事情。因此，时间管理指南之类的书常年位居畅销书榜的前列。不幸的是，我们往往能发现这些指南之间的矛盾和不一致之处。《尽管去做》一书中提倡的是，一想到任何可以在两分钟内完成的任务就立即去做。另一本同类畅销书《吃掉那只青蛙！》建议从最困难的任务开始，再逐步转向更容易的事情。《战胜拖延》一书则建议首先执行调度者的社交活动和休闲活动，然后再将工作填充到空白时间之中，而不是我们经常做的相反的顺序。“美国心理学之父”威廉·詹姆斯曾断言，“没有什么比永远有一个未完成的任务悬在那里更让人感到疲惫不堪的”，但弗兰克·帕特诺伊在《等待》中提到一些故意不立即完成任务的例子。
1700495549
1700495550
每位大师都有其独特的思想体系，我们很难知道该听谁的。
1700495551
1700495552
1700495553
1700495554
1700495556
算法之美：指导工作与生活的算法 安排时间是一门科学
1700495557
1700495558
虽然时间管理跟时间本身一样古老，但时间调度这门科学是在工业革命时期的机器工厂中产生的。弗雷德里奇·泰勒是一名有钱律师的儿子，1874年，他放弃了哈佛大学的学业机会，去费城的恩特普赖斯水压工厂做了机工学徒。4年后，他完成了他的学徒生涯，开始在米德维尔钢铁厂工作，在那里，他一路从车工车间领班做到了总工程师。在这个过程中，他发现，他监管的机器（和人）的时间并没有被很好地利用，这促使他开创了他所谓的“科学管理”这一门学科。
1700495559
1700495560
泰勒创建了一个规划办公室，它的中心是一个公告板，展示了商店的日程安排，以便所有人都能看到。公告板记录商店里的每一台机器，显示该机器目前正在执行的任务，以及后续将执行的所有任务。这一创意是由泰勒的同事亨利·甘特提出的，他在1910年开发的甘特图帮助了从胡佛大坝到州际公路系统等20世纪美国很多雄心勃勃的建设项目规划组织。一个世纪后，甘特图仍然出现在亚马逊、宜家和美国太空探索技术公司项目经理办公室的墙壁和屏幕上。
1700495561
1700495562
泰勒和甘特将调度变成一种研究对象，他们赋予它视觉和概念的形式。但他们并没有解决一个基本问题，那就是，到底怎样安排日程是最好的。直到几十年之后的1954年，兰德公司的数学家塞尔默·约翰逊在他发表的一篇论文里才第一个暗示这一问题可以被解决。
1700495563
1700495564
约翰逊研究的是书籍装订这个例子，在装订过程中，每本书都需要在一台机器上印刷，然后在另一台机器上进行装订。但这种最常见的双机器安装例子更类似于家庭中的洗衣服。当你洗衣服时，必须先用洗衣机再用烘干机，每次洗不同的衣服花费的时间也不同。大的污渍可能需要更长的清洗时间，但烘干时间均不变；衣服数量多可能需要更长的烘干时间，但洗衣时间不变。所以，约翰逊问，如果在同一天你有很多衣服要洗和烘干，最好的处理方法是什么？
1700495565
1700495566
他的答案是，你首先应该找到一个需要最少时间的洗衣或者烘干的方法，如果这种最短时方法需要用洗衣机，那么先洗这批衣服。如果这种方法需要用烘干机，将这一步放到最后。剩下的衣服重复此最优分类过程，也就是在安排上从两端向中间进行。
1700495567
1700495568
直观地说，约翰逊的算法之所以合理是因为无论你如何安排洗衣的顺序，在开始时总有一段时间是洗衣机单独运行的，而在结束时总有一段时间是烘干机单独运行的。将开始时的洗衣时间和结束时的烘干时间最小化后，你就能将洗衣机和烘干机共同工作的时间最大化。因此，用于洗衣的总时间就会是绝对最小值。约翰逊的分析产生了时序安排的第一个最佳算法：从最好洗的衣服洗起，以最少的烘干衣量结束。
1700495569
1700495570
在直接应用之外，约翰逊的研究还揭示了更深层次的两点内容：第一，时序安排可以通过算法表达；第二，存在最优时序安排方案。这引发了一项庞大的研究，为大量假定工厂中不同数量和种类的机器运行提供策略。
1700495571
1700495572
与装订或洗衣过程不同，我们将重点研究这其中的一小部分：单一机器调度。因为最重要的时间调度问题只涉及一台机器：我们自己。
1700495573
1700495574
1700495575
1700495576
1700495578
算法之美：指导工作与生活的算法 处理时限
1700495579
1700495580
一提到单机调度，我们立马会遇到一些问题。约翰逊的装订调度是基于最小化两机共同工作时间来降低总时间的。然而，在单机调度的情况下，如果我们要完成所有被赋予的任务，那么所有的安排都应该用同样长的时间去完成，这与先后顺序无关。
1700495581
1700495582
这一点最基本且违反直觉，值得重复应用。如果你只有一台机器，同时你必须完成所有的任务，那么对于任务的任何排序都将花费相同的时间。
[
上一页 ]
[ :1.700495533e+09 ]
[
下一页 ]