大数据文摘出品
作者：Andy
主播：段天霖
《生活中的算法 (Algorithms to live by)》：调度算法
新的一周开始了！有效率的一周应该始于一份安排得当的计划表。
但安排日程不是件容易的事情，有些任务得在其他任务后进行（比如说洗完衣服后，才能晾衣服）；有些有准确的截止日期，而有些却没有，还有些呢，介于两者之间；有些紧急，但不重要；有些重要，但又不紧急...
面对这一堆乱七八糟的任务，到底该如何安排效率最高？这涉及到计算机科学中非常常见的调度 (Scheduling) 算法。
本周，我们来聊聊【调度】这个或大或小的话题，以及如何利用它来进行科学时间管理。
点击收听由来自杜克大学美女主播段天霖与大家分享：如何科学地管理自己的时间。
听了主播的分享，你是否对调度算法有了更深刻的影响，在留言区留你的心得吧，文摘菌会选出获赞数最高的两位同学，免费邮寄送出《算法之美》这本书哟~~~ 我们日常都会遇到时间管理问题，去做什么，什么时候做，以及什么顺序做？
我们总会想着找到一个最好的方法来进行时间管理，市面上也有无数的书告诉我们该怎么办，但他们却又互不相同，甚至互相矛盾。比如说《搞定：无压工作的艺术》里就推崇一种把任何想到的能在两分钟以内完成的工作，迅速搞定的做法；而与此相对，在《吃掉那只青蛙》里面，却又倡导先从困难的事开始，然后到简单事...
似乎每位作者都有着自己的一套理论，那到底该听谁的呢？
那不妨借鉴一下计算机科学中的调度 (Scheduling) 算法，来进行科学时间管理。
调度算法：起源
虽然，时间管理这个概念可能与时间本身一样古老，但说到调度算法科学，可能得追溯到19世纪末了。Frederick Taylor 在拒绝了哈佛大学的录取后，成了一名光荣的机械师学徒，之后一番打拼，从学徒升到了总工程师。期间，他越来越坚定一个想法，那就是，很多机器的时间没有得到最大程度的利用，于是他就提出了一个新的叫作“
科学管理”的学科。
于是 Taylor 建立了计划办公室，房间中一块大板子上列着店内所有机器，以及正在进行的工作和正在等待的工作。之后他的同事 Henry Gantt 在此基础上进一步提出了现在大家熟悉的甘特图，如今被广泛应用在各个大公司的项目管理中，比如亚马逊和 SpaceX。
然而他们只是提出概念还有视觉化，却没解决怎么调度这个根本问题。而这还得等到几十年后 RAND 公司的数学家 Selmer Johnson 来解决了。
Johnson 碰上的是书本装订问题，或者说洗衣服问题。洗衣服分两步，洗和烘干。假设你有几篮子衣物（糙汉子表示只有一个篮子），有的比较脏得长时间洗，烘干时间正常；还有的衣物多得长时间烘干，洗倒不用太久。于是 Johnson 就问，到底怎样的顺序来洗衣服最好呢。
答案很简单，先找出这些篮子里洗或烘干所需时间最短步骤，如果是洗就放最前面，如果是烘干就放最后面，不断重复这个步骤就能获得最优顺序。
因为洗衣过程中，必然有些时间只在洗或只在干，而不是同时进行。为了避免这种浪费，只要使它俩最小就好。于是这就是调度算法中第一个算法：
从最好洗的开始，以最好干的结束。
此外，Johnson 还揭示了两点：
调度是可以用算法形式表现
最优的调度方案是存在的
于是这就为调度延伸出了各种问题，比如说一个有各种各样机器的虚拟工厂，它的最优调度策略是什么。
但今天，我们不谈这些复杂问题。只谈一台机器情况，因为我们最关心的调度问题也就只有一台机器——我们自己。
截止日期是第一生产力
然而，当挽起衣袖准备开始解决单机器调度问题时，却突然发现好像有点不对。因为一台机器一次只能做一件事，那无论怎样的顺序来做花的时间都一样，还需要什么调度。
但是，慢着，在现实生活中却又是需要考虑做事顺序的不是吗？
那是哪儿出问题了呢，这里就要说到调度中最重要的概念：
度量指标 (metric)，明确你的目标。也就是你得对不同方案好坏设置一个度量标准，是越快越好，还是先干重要的好。这也是计算机科学里的一个重要原则：在计划前，先设定一个评判标准（这也是机器学习中evaluation的重要性）。
因此即使同一个问题，如果评判标准不同，那最优策略也就不同。
比如说我们希望尽量不拖延，也就是超过截止日期的时间最短。那就可以使用称为
最早完成日期 (Earliest Due Date)的最佳策略。只看截止日期，先做截止日期最近的，很简单。或许都不用这里说，你早就已经会用这个策略了。但现实中不光拖延时间，还会有很多其他因素。比如你买了很多新鲜食物，如果把品尝日期当做截止日期，应用上述策略的话，确实能最小化你食物的过期时间，但就不保证味道了。
于是改变一下测量标准，最小化会过期食物的数量。于是就得到摩尔算法 (Moore’s Algorithm)。它最初也是先按过期日期先后来吃，但是一旦看到之后的事物可能会在吃之前过期。那么立刻停下来，把最大的食物（需要最长时间吃）丢掉。这样就能尽量减少过期食物数量了。
搞定任务
有时候我们关心的可能不是截止日期，而是越快越多的搞定手头事情。而此时的最优算法又成了最短处理时间(Shortest processing Time) 算法，即先完成能最快完成的任务。
这就类似《搞定：无压工作的艺术》中的策略了。先把能快速解决的事先解决，也能减少心理负担，使得集中精力于困难的事。
但在现实中，并不是说越快越多完成任务就越好。特别是事有轻重，有些事要比另一些事重要些。那么我们可以对最短处理时间算法进行少许修改，不同的任务有各自权重，利用权重与所需时间比得到“单位时间重要度”，之后只需优先执行重要度高的任务即可。这个算法可以称为加权最短处理时间策略，非常实用。
有意思的是，当观察动物觅食时，也会观察到类似策略，它们会倾向于寻找“单位时间更多能量”的食物。
认清问题
从上面的两个例子可以清晰看出，虽然针对各个标准都能给出最优解法，但选择哪个标准却是在于我们自己。
这也提供了看待拖延症（时间管理的死敌）的另一个视角。一般认为拖延症是一种坏习惯和行为，但会不会实际上拖延症只是用了匹配错了最优策略和度量方法呢。
通常认为拖延症是懒或者逃避，但其实对于一些勤奋想快点做完事情的人也非常容易出现。比如2014年的一项研究就发现，有时候人们为了尽快完成任务，结果却花了更多时间和精力，也就是欲速则不达。
那么他们采用了错的策略吗，不，他们只是把一个好策略用在了错误的标准上。因为他们可能用的是最短处理时间方法， 但是实际上应该进行衡量的标准并不是最快最多完成任务。
这就是成也标准败也标准。比如说现在的智能手机，会在应用图标的右上角标上未读信息，不管信息的重要性都只计数一，这导致我们不能分清信息的重要性，而会浪费很多时间去检查不重要信息。只因为我们是以尽快完成尽可能多的任务为策略。
而实际上应该做的可能应该是，先把重要的事情做完。这听起来是解决拖延症的可靠方法，但是对于NASA的人来说确实在最戏剧性地情况下意识到这个问题：火星的表面，而且是众目睽睽下。
优先级倒置和优先限制
1997年夏天，当人们兴奋地将价值一亿五千万美元的探路者号送上火星，却发现它居然出现了拖延症。寻路者号对于优先度最高的任务不闻不问，却把时间都花在那些中等优先度的任务上。
大名鼎鼎的 JpL（喷气推进实验室）小组爆肝数日，最终发现了元凶，那就是调度中的大敌人：优先级倒置 (priority inversion)。具体是这样的，系统先运行一个低优先级任务占用一些系统资源，然后根据计时器中途中断任务，调用调度程序。
这时调度程序想运行高优先级的任务，但因为要用的部分资源被低优先级任务占着，所以只能退而运行中优先级不使用相同资源的任务，或是这个占用着资源的低优先级任务。因为这个原因，往往有些最高优先级的任务被丢在一旁长一段时间不执行。
JpL 一旦发现问题就知道怎么解决了，写了个代码发送到火星。这个解决方法便是优先级继承，方法很简单：一旦发现低优先级任务占用了高优先级任务的资源，便立刻将其优先级升为与被占用任务相同优先级，尽快执行完。
生活中也会遇到很多优先级倒置的问题，可以说它也是拖延症的罪魁祸首之一。比如我最近的例子，需要交学费，非常紧急（不按时交开除学籍！），然而银行在山下，下山得骑车。借车这事，在我心里优先级又不高，结果便一直没借车，去忙些其他事情了。
直到最近学校发来最后通牒：“快交学费！” 可以去会计科，于是便不用下山了，也就不用借自行车，也就没有低优先任务阻碍交学费这个紧急任务了，于是我也就没有被开除了（这才是重点）。
事实上，下次碰到这样这样的事情，正确做法是将借自行车升级为交学费一样紧急的事情。
以上讲的都涉及到优先限制，也就是有些事只能在某些事之后完成。
撞上墙了！ Eugene Lawler 可以说是20世纪研究优先限制最杰出的科学家，他几乎花了一生时间来思考怎么才能更有效地完成一系列接连任务。因为当一个普通调度问题加入优先限制后，可能会变得很不一样。
比如说最早完成日期，如果加入优先限制，就会发现原来策略行不通了，因为有些任务即使截止日期早，但却得在另一件任务之后做。而 Lawler 证明只需要反过来从后往前就能很好解决，也就是先找没有未完成任务中没有其他任务依赖的任务，找出其中截止日期最晚的，放在调度表最后，然后不断重复这个操作就行了。
此外，他还发现了很多很有意思的其他问题。比如说最短处理时间，当加入优先限制后，似乎还是一个很基础的问题，但事实上却没有一个有效解决它的方法。不光是 Lawler 没想出来，其他研究人员也都没想出来。
而且不光最短处理时间问题， 情况远远比这更糟。那就是， Lawler 发现有一系列类似问题，都不能得到有效解决，于是调度理论也就撞上墙了。
不过这也激起了像 Lawler 这样的顶尖研究人员的雄心，去探索调度问题中到底哪些是无法被解决的，哪些又能被解决的。也就是说对整个调度理论，进行一次大勘察，而这个大勘察现在都还在继续着。
最近研究显示，调度问题中有7%的问题现在尚未理解。
而即使是剩下93%理解的问题，情况也不容乐观，其中只有9%是可以被有效解决的，而剩下84%都被证明无法被解决。也就是说事实上对于大多数调度问题，确实也没有最佳方法。
所以当我们对管理时间感到压力山大时，也不用太自责，或许它本来就太难了。然而，这里提到的一些算法还是可以作为你处理这些难问题的起点，即使不是最优方法，但至少有个比较好的方法可以使用。
停停停，先来干这个：优先处理
到目前为止说的都是些让问题变得更复杂的因素，那现在来看看让问题变得更简单的吧。比如如果能够在某件任务中途停下来，而去干其他事。这个叫作抢先 (preemption)的性质，让问题又发生了大大的改变。
一些之前无法被解决的问题，又能被解决了。比如说加入优先限制的最短处理时间问题，如果加入抢先后，就又能得到有效解决了。只要不停切换为处理当前重要度最大的任务即可。
抢先，尤其适合应对不确定性。假设在进行一些任务时，同时有新的任务突然加入，那么就需要重新考虑当前该运行的任务，也就是设置哪个任务抢先。
不确定性对策略的影响不大，仍然按照加入抢先后的策略进行就可以了。
抢先处理的代价 抢先有它的好处，当然也就有其缺点，环境切换 (Context Switch)。而环境切换时，是需要付出一些代价的。
日常中我们也常会碰到，从某事切换到另一件事时，有时需要调整下心理状态，或者工作环境。比如说查看邮件时，得打开邮件软件，等上好一会；如果要写代码，得登录终端，调节好状态；如果写作，又得找来卡片，笔墨，工具书...
任务和任务之间切换时，是需要耗费额外时间的。当任务少时，或许还看不出有什么问题，但当我们把任务切换频率提到很高时，就会出现一个很奇怪的现象系统颠簸 (thrashing).
简单的解释就是，假设有很多任务，我们想进行多任务处理，于是就给每个任务分配相等但少量的时间，不停地来回切换处理任务，这类似于计算机系统的分时处理。
假设每个任务都需要准备时间，于是当任务太多，分配给每个任务的时间块很短时，就会出现不断在任务之间切换，而每次准备时间就把时间块用完了的现象。这样就会不断在各个任务上移动，而实际工作却一点没做的现象，即系统颠簸。
日常生活中类似的，一有邮件就点开瞧瞧，一有信息就拿起来看看，有过经验的人也知道这样对效率影响有多大。
对于计算机来说，这个问题可以简单用升级内存或缓存的手法解决，当然对于我们人，要升级大脑可没那么简单，或许还得等到多年以后生物技术的发展。
但也还是有些方法来避免这个问题的。第一，我们可以减少任务的数量，对不重要的事情说不，把精力只集中在少数任务上。第二，我们可以规定最短时间块得有的时间，也就是很流行的番茄钟，给每个任务规定一个充足的最短时间。
当然，如果你不想减少任务数量，也不想麻烦的使用番茄钟，调度中一些其他技巧也能帮组你避免环境切换的损耗。
比如说中断结合 (Interrupt Coalescing)，其实就是批量处理。简单说就是把类似任务放在一起完成，这样也就避免了环境切换。比如说把一天的特定半个小时全部用来回复邮件和发邮件，就能提高很多效率。
运用这个技巧的典范人物就是大神级程序员 Donald Knuth，他说：“我一次只干一件事。” 当然，他说的一件事是指需要相同环境的一类任务。比如说在“2014 TeX 大调整”中，他就一下把过去6年大家关于 TeX 反应的所有bug都修复了。完成之后还挂上“等待2021年的大调整”。不仅如此，他也没有电子邮箱，就连邮件都是三个月才看一次，而传真更是六个月才看一次。
其实我想知道其他时间他都干什么去了。
怎么管理自己的时间 最后回到主题，怎么利用调度算法最优地管理自己的时间？
很遗憾，答案是没有。因为现实中要处理的调度问题往往都是不可解决的，也就是没有最好的调度方案。
但是呢，至少我们也能从中借鉴到一些小技巧运用于时间管理中，比漫无目的地东一棒西一锤瞎干的好。
明确度量任务完成的标准，根据这个标准制定计划。
明确手头任务的重要性，再根据任务完成所需时间进行估算，先完成最紧急最重要的任务。
当一个紧急任务必须在一个不紧急任务之后才能进行时，将这个不紧急任务升级为同样紧急的任务。
不要尝试短时间内进行多任务，而是将相同任务归类，然后一段时间只做一类任务。
本文首发于微信公众号：大数据文摘。文章内容属作者个人观点，不代表和讯网立场。投资者据此操作，风险请自担。
