大數據文摘出品

作者：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年的大調整”。不僅如此，他也沒有電子郵箱，就連郵件都是三個月才看一次，而傳真更是六個月才看一次。

其實我想知道其他時間他都幹什麼去了。

怎麼管理自己的時間

最後回到主題，怎麼利用調度算法最優地管理自己的時間？

很遺憾，答案是沒有。因為現實中要處理的調度問題往往都是不可解決的，也就是沒有最好的調度方案。

但是呢，至少我們也能從中借鑒到一些小技巧運用于時間管理中，比漫無目的地東一棒西一錘瞎幹的好。

• 明确度量任務完成的标準，根據這個标準制定計劃。
• 明确手頭任務的重要性，再根據任務完成所需時間進行估算，先完成最緊急最重要的任務。
• 當一個緊急任務必須在一個不緊急任務之後才能進行時，将這個不緊急任務升級為同樣緊急的任務。
• 不要嘗試短時間内進行多任務，而是将相同任務歸類，然後一段時間隻做一類任務。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部