OptaPlanner背景
在上一篇裡噴了不少水，這一篇準備放點幹貨；其實也沒辦法完全幹，因為很多預備知道在交待一下。好了，說一下關于OptaPlanner的背景、應用相容性及其原理。
這一篇先說一下OptaPlanner是何方神聖，再看看它适用于哪種平台（.NET能用嗎？老舊系統能用嗎？），再從原理上探究一下，它是如何幫我們把一個看上去幾乎不可能實作的工作，努力做到比經驗豐富的老師傅更好的。下一篇我将會講解OptaPlanner相關的基本概念,并教大家它的examples(示例)運作起來(這些examples可是好東西喔，并且非常豐富)。
顧名思義，叫什麼planner的，它肯定是用來plan東西的東東，就是把一堆東西（資料）扔進去，再教它一些規則(Drools腳本或Java寫的算分程式)，然後它就運用它的數學頭腦，把這些東東按要求把它初始化好，并努力找到一個相對最優的方案；如果資料不是太多，那它就能找到一個絕對最優方案了，因為它以把所有情況都篇曆。例如：你有一堆任務需要确定配置設定到哪些機台，需要計算每個任務什麼時候開始處理(也就是明細的生産計劃了)；用OptaPlanner跑完之後，就會給出一個方案，這個方案包含了每個任務應該放在哪個機台，應該在什麼時候開始。又例如：在醫院等機關進行醫護人員排班時，把各個醫護人員的專長，每個人員的作息資訊，每個科室需要的專業技能等資訊放進去，OptaPlanner就能給你找出一個排班方案出來，可以滿足各科室對特殊專業人員的需求，也可以滿足各人員盡量不逾時工作的方案。
那麼問題來了，OptaPlanner到底是一個什麼鬼東西？它有這麼牛？真能這樣，我們做排産的老師傅不是要失業了嗎？其實不然，它隻是按我們設計的規則來找盡量好的方案，而這些規則好不好直接影響到方案的優劣，是以如果OptaPlanner成功應用了，并不是替代了老師傅們，而是把老師傅解放出來，讓他們去重新思考并制定更佳的規則，并通過OptaPlanner來驗證并實作這些方案。
E文好的同學可以直接進它的官網（
http://www.optaplanner.org）, 學成了記得分享呀。先說一下這OptaPlanner的來頭，它本來是一個名叫Geoffrey De Smet的大牛自己寫的，後來他就把它貢獻給了JBoss基金會(這裡省去了N年的曲折離奇, N >= 10)，并成為KIE項目組中OptaPlanner項目的負責人。是以OptaPlanner是基于Apache2.0開源協定的，對商業友好，就是說你想用就盡管用，有問題還可以在他們的讨論組上求助。關于這位超級大牛的個資訊及OptaPlanner的詳情，可從以下連結看到，其實這位大牛給OptaPlanner錄制了很多講解OptaPlanner的視訊，隻不過它隻放在Youtube上，大家要看的自己想辦法上去搜OptaPlanner了，提醒一下各位，Gerffrey這牛不是英美或其它以英語為母語國家的人（好像是比利時還是荷蘭人），它的口語鄉單比較重，聽起來挺吃力的，還沒字幕。而且講的都是各個示例和一些比較進階的應用，去看視訊之前最好還是打一下基礎，要不然基本上看不懂（沒基礎就算講中文也聽不懂吧？）。
Geoffrey De Smet在GitHub上的首頁：
https://github.com/ge0ffrey（還有StackOverflow上也有他老人家不少對OptaPlanner問題的解答，大家可以搜搜）
OptaPlanner的背景介紹：
http://www.oschina.net/news/75942/a-decade-of-optaplanner（這是開源中國社群翻譯Geoffrey老人家的文章，原著E文版在這：
http://www.optaplanner.org/blog/2016/08/07/ADecadeOfOptaPlanner.html）
OptaPlanner其實是一個很好的排程引擎（更貼切地說它是一個規劃引擎，下面就稱規劃引擎吧，因為它不光用于排産上），耐何在國内使用的人十分少，是以中文資料幾乎沒有，國内有幾個比較出名的APS産品，不知道其排程核心用的是什麼，不過如果是自主開發APS系統的話，OptaPlanner是一個好的引擎，畢竟并不是所有企業都能找到一堆數學專家對組合優化問題進行研究的。而OptaPlanner資料非常豐富，它的項目組還能提供很好的技術支援（免費的僅限于讨論組答疑，付費的就沒試過了）,而且使用起來也友善、容易。但目前我觀察的情況來看，還隻有比較多國外的同行們及相關的技術網站在研究讨論。我也是奉公司之命開發生産排程方面的系統，才硬着頭皮去啃它的。又耐何我的體育老師不給力，教的E文也不怎麼樣，雖然是把基本的東西看懂了，但很多更深層的東西其實還沒有完全摸透的(到目前為止我還遇到一個Score Corruption的問題還在研究)。是以有賴大家一起學習之後的分享了。在應用OptaPlanner的過程中，我也遇到一些問題，一開始有些小白問題，後來又遇到一些跟系統實情相關的難題，我也曾經在讨論組上向Geoffrey他老人家請教，老實說，他還是一個比較有耐心，非常nice的人，一點都不嫌我這類小白煩，從原理開始給我講解出錯的原因，應該如何改，這個要猛贊一下。
接下來我就發揮程式狗的看家本領Ctrl + C -> Ctrl + V, 中間還去逛了一次百度翻譯（沒辦法，體育老師呀）.
OptaPlanner是一個限制求解器。它優化了企業資源計劃的使用情況，如車輛排程、員工排班、雲優化、任務配置設定、任務排程、Bin Packing等等。每個組織都面臨這樣的排程難題：配置設定一組有限的受限資源（員工、資産、時間和金錢）來提供産品或服務。OptaPlanner提供了更有效的計劃，提高服務品質并降低成本。OptaPlanner是一個輕量級的、可嵌入的規劃引擎。它令普通的java程式員有效地解決優化問題。它還與其他JVM語言相容（如 Kotlin 與 Scala）。限制适用普通的域對象,可以重用現有代碼。沒有必要把它們作為數學方程來輸入。在引擎蓋之下，OptaPlanner結合先進的優化的啟發式和共通啟發式演算法（如禁忌搜尋、模拟退火和延遲接受）,非常高效地進行分數計算。OptaPlanner是開放源代碼的軟體，Apache軟體許可下釋出。它是用100%的純java™，運作在任何JVM在Maven的中央存儲庫也可用。
好了按上述的官方描述我們可以大概知道，它就是一個用來解一些規劃問題的引擎，而規劃問題幾乎都可以被視作NPC問題，關于什麼是NPC問題呢？這裡還噴點水，讓大家對NPC問題有個大概的概念，如果不是研究資料的，了解一下就可以了。大家可以看一下這位牛人寫的關于NPC問題的文章（
http://www.matrix67.com/blog/archives/105），概括來說，就是一些沒有辦法使用确定性算法來得到結果的問題，而對于這類問題，又分為NP問題和NPC問題，但都隻能通過周遊的辦法才能找到。對于NP問題和NPC問題，我有以下了解，也不知道對不對，大牛看到不對的幫忙指正一下：
NP問題：一種無法通過确定性算法直接獲得解，但對獲得的解是可驗證的，例如：結合上一篇文章提到的生産排程問題，如果老闆隻要求做出一個可行的生産計劃，也就是隻需要一個可以執行的生産排程就可以了。成本、效率什麼的都不管；那麼這就是一個NP問題。因為要做出這個計劃，你也是沒有直接的、确定的方法或算法來做的；更多的是靠經驗、對實際情況的有限掌握、對來情況的預判和感覺。但是做出來的計劃是可以驗證的。也就是說工廠中的房間拿着這個計劃是真的可能執行的，而不會出現物料不到位、産品配置設定到了錯誤的機台上等違反硬限制問題的， 那麼隻要不違反這些硬性限制，就認為這是一個可行的計劃。是以做一個可行計劃，可以被視作是NP問題。
NPC問題：則是那種不旦無法通過确定性算法獲得解，對所得的解，也沒有一個确定的辦法去驗證的問題。還是上面的生産排程問題，如果老闆要求做一個所有情況下除了可行，還要成本最低、效率最高的計劃。那麼：1. 計劃員也隻是靠經驗、預判、對資料有有限掌握做出一個計劃來，計劃是否可行是可能驗證的(也就是NP問題)，但這個計劃是否成本最低、效率最高，那就沒辦法驗證了，除非你把所有可能的計劃都列出來(這個就不是确定性算法了，因為并不是所有情況你都能把所有情況都列出來)。事實上，現實世界遇到的問題，光靠人類，即便通過超級計算機，也是不太可能把所有情況都周遊完的，例如一個計劃有1000個任務，就算忽略任務的所有其它考慮因素，就是1000個任務無任務要求，随便自由地排列，也就是1000個數的排列問題了，有多少種情況？是1000的階乘！（有興趣的同學自己回顧一下高中的排列公式）再考慮每個任務的各種屬性，及每個屬性的可能取值範圍，那麼組合下來，通常是天文數字了。
是以，OptaPlanner在排程領域的作用就是幫人們對問題的可能性進行“周遊”，為什麼我把周遊引起來呢？因為如果僅僅是無序地周遊，對所有情況一個一個試，那OptaPlanner就沒啥作用了，我們可以通過自己編寫程式，就能設計出周遊所有組合情況的代碼來（能不能跑完那是另外一回事）。OptaPlanner強大之處在于，他是有方法地去周遊的，它引入了禁忌搜尋，模拟退火等算法，力求在固定的時間内，找到比傻傻地周遊更好的組合方案出來。事實上也證明它這些算法是有效的。
OptaPlanner的作用、構架和應用相容性
關于OptaPlanner開源包，大家可以上官網看看，我在這裡也隻做個大概的介紹，畢竟我也是新手呀。其實OptaPlanner現在已經加入KIE Project Group，作為KIE的一個子項目，關于KIE可以看看Redhat的一個項目群，包括了
OptaPlanner（就是本系列文章的主角），
Drools(規則引擎，國内已有很多相關的資料，我就不再熬述了，OptaPlanner是需要結合Drools來使用的，是以這個系列的文章裡也會有些内容涉及Drools，但不會太深入)，另外一個就是
jBMP了，是一個流程定制的平台。
作用
OptaPlanner用官方的描述就是可以幫你規劃出一個用更少的資源做更多更好事情的規劃引擎。如下圖列出它可以做的工作領域（這僅僅是OptaPalnner的Example裡有的示例，其實所有關于規則的問題，屬于NPC的問題，隻要你能把它抽象并模組化成OptaPlanner可識别的模型，你就可以用OptaPlanner來解決）：車輛排程、工作排程、裝置排程，Bin Packing(就是用袋子裝石頭那個問題啦)及員工排班。
構架和應用相容性
那麼應用OptaPlanner需要什麼條件呢？其實作為一個輕量的、可嵌入的規則引擎，相容性肯定是人家設計時的考慮重點之一，是以它完全是一個純Java環境的軟體，隻要你的系統有Java8以上的運作環境（7.6版本要求的是Java8），遵循
Apache Software License 2.0就可以使用了。在我的工作中，我把它運作于Windows, 雲端的Unbuntu.凡是一般Java程式能運作的環境，隻需你一個jar指令，就可以運作你内嵌了OptaPlanner的程式了。這裡有一個官方關于OptaPlanner相容性的圖：
那麼有人就問了，現在很多企業用的都是Microsoft平台或其它老舊平台技術（有什麼辦法呢.NET就是多人才），是不是OptaPlanner與我的項目就無緣了？其實不然，因為OptaPlanner本身是一個引擎，是基于Java技術的，你通過它來實作你自己的規劃引擎程式的時候，必然也是需要Java寫的。但這個規劃程式是一個服務程式，它不像普通的Web程式，需要頻繁跟使用者互動，事實上它的所有運作過程中涉及的資料都是需要基于記憶體的，在此過程是不能進行IO的（并不是說OptaPlanner引擎不允許這麼做，而是我們設計的時候就不應該這麼做），至于為什麼，是碼農都懂，一個對CPU高度依賴的程式，你還要它去做I/O，是不是有點那個？是以通常情況下，它是一次性把需要規則及資料都裝入記憶體，完成後再輸出。基于上述原則我們就可以把寫好的規劃引擎程式（Java包)放在一台相對獨立的伺服器上去運作，再以服務的形成為其它用戶端系統提供規劃服務。那你的用戶端系統是用Web還是 C++來寫，是你自己的事了。
原理
那麼OptaPlanner是通過什麼方法，高效地幫我們在盡量短的時間内，找到更佳的方案呢？還記得上一任篇老農提到，我們做排程的時候，通常有兩種限制條件，分别是不可違反的硬限制，如果一個計劃違反了硬限制，那這個計劃就是不可行的，例如：生産計劃中，把産品固定工序的加工次序調亂了，又或者把産品配置設定到錯誤的機台上生産(這些限制條件都是業務上你們自己定義的)，那麼OptaPlanner就把它定義為違反了硬限制。另一類就是軟限制，就是那種可以違反，但違反得越多，就會影響越大（影響包括成本、效率、品質等），所得結果方案的品質越差；違反這種限制，OptaPlanner就把它定義為違反了軟限制。OptaPlanner就是對這兩類限制進行打分，硬限制對應的是硬分數，軟限制對應的是軟分數。那麼得分越高，就表示對應方案的品質越高。在計算這些限制分數的過程中，OptaPlanner會保持優先優化硬分數、然後在硬分數最優的基礎上，再去優化軟分數的原則，來尋找最佳方案。例如：兩個方案A、B對比，方案A的硬分數比方案B的硬分數高1分，方案B的軟分數比方案A的軟高出10萬分。那麼OptaPlanner最後還是認為方案A更佳。也就相當于我們寫SQL腳本時，order by子句中前後兩個字段的關系了，靠前的字段排序比靠後的字段更優先。
思考題：
既然硬限制是不能違反的，那OptaPlanner當然要保證找出來的方案絕對是不違反硬限制的，這個大家覺得在所有情況下都成立嗎？就是OptaPlanner必然給你找到一個絕對不違反硬限制的方案嗎？ - 顯示不是，大家自己思考一下。
這一篇我們先介紹一下OptaPlanner的背景、使用情景和原理。下一篇我們就開始實質的了解它的應用。
一個IT老農，先盡力好當兒子、丈夫和父親的責任，然後做點有趣的事。