實現不完全規劃的方法

2021 年 12 月 15 日
筆記
APS, OptaPlanner, 生產計劃, 規劃引擎

　　在各種常見的規劃場景中，我們經常會遇到一種不完全規劃的情況。即在正常情況下，在完成了一次規劃運算(甚至是CH階段的運算中)，OptaPlanner的規劃實體(Planning Entity, 下稱規劃實體)中每個規劃變數(Planning Variable，下稱規劃變數)必須非空，即必須被賦予規劃變數取值範圍(ValueRange，規劃變數取值範圍）範圍內的值；儘管有更約束被違反，也必須實現賦值。

　　例如，在CloudBalance示例中，若一個數據集中存在足夠多的進程(CloudProcess對象)，以致啟用所有電腦的記憶體無法裝入所有進程。此時，引擎還是會強行把一些進程塞進一些已經記憶體已經不足的電腦中，從而出現記憶體這個約束(硬約束)被打破。但在我們的實際場景中，面對這種情況，我們並不希望輸出這種違反硬約束的結果；因為在這樣的業務情景中，違反硬約束的結果已經是典型的不可行方案了。我們更希望引擎能更機智靈活地識別出這種實際場景中毫無意義的方案，從而找到一個不會將資源過度分配的方案。

　　這種方案在OptaPlanner中被稱為 Overconstrained Planning，對於這種資源超用的處理情況，可歸結為對資源的過度分配。以下用戶手冊的章節描述了兩種方法實現方法：//www.optaplanner.org/docs/optaplanner/latest/repeated-planning/repeated-planning.html#overconstrainedPlanning

　　從文中可以看到，要實現這種功能，OptaPlanner並沒有開箱即用的方法或功能。但通過其中的一些特性我們仍然可以通過簡單的方法巧妙實現。目前主要有兩種辦法來實現「避免資源超用」情況，分別是 – “讓規劃變數允許為空”和”為規劃變數的取值範圍提供到一些虛擬值”.

讓規劃變數允許為空

　　正常來說，對於一個規劃問題來說，一個可能的方案(Possible Solution)是其所有規劃實體(Planning Entity, 下稱規劃實體)的所有規劃變數)都完成賦值。在規劃的CH階段就是實現對每一個規劃變數進行賦值的階段。通過在定義規劃變數中加入nullable屬性並將其屬性值設置為true來讓一個規劃變數在規則過程中允許保留空值。如下程式碼：

@PlanningVariable(nullable = true)     
public getCloudComputer{
         return cloudComputer;     
}

　　通過該屬性設置，在規划過程中規劃變數除了會從規劃變理取值範圍中獲取可能值生成方案外，空值(null)也將出現在取值範圍內，這種情況下無需向取值範圍列表加入空值，程式會自動空值納入考慮範圍內。

　　細心的同學一定會想到，如果規劃變數可以為空值，那麼會不會得到的方案全部規劃變數都為空，畢竟空值也是規劃變數的取值範圍，且滿足約束。但實際業務場景中，空值對於我們來說，通常是不存在業務意義的；只不過是想讓方案不過度分配資源而已(在資源分配的規劃場景中)，而不是我們的最終目標。通俗地講，我們的最終規劃目標，是在保證資源最大使用率的情況下，找出不超過資源最大可用的方案。從輸入的方案來看，就是想找出一個儘可能所有規劃變數都有值，如果分配的規劃變數超過可用範圍就用空值代替。因此，我們就會想到，添加一條與獨立於業務的約束，用來實現上述意圖，這條約束通常是是中間約束(如果使用的是「硬中軟」約束結構的話)，當然只要使用超過一層的約束，都可以人為地設計一個保持在硬、軟約束之間的約束，來實現「盡可以少的規劃變數被賦空值」的目標。

為規劃變數提供一個「萬能」的虛擬值

　　為了避免資源被超用，除上述將規劃變數設置為空的方法外，還可以為規劃變數的取值範圍設置一個無限的虛擬值，在資源規劃場景中，可以理解為建立一個虛擬資源，這個虛擬資源具有無限資源量。用來承擔那些超出正常資源可用量的分配。還是以CloudBalancing(本文只以該示例的記憶體限制為唯一分配條件)為例，我們可以在可用的電腦列表中，添加一個記憶體無限大的電腦。目的是當可用的電腦的記憶體無法放在所有進程時，超出的進程可以放進這個記憶體無限大的虛擬電腦中。這種情況與上述將規劃變數設定為可以空的情況一樣，如果不作任何額外限，有可能得到一個計算結果是所有的進程都被分配到這台虛擬電腦中。因此，需要額外添加一個中間約束，其目的是在確保儘可能使用完所有真實電腦後，才啟用這台虛擬電腦。

　　以上是在日常跟各位網友的交流中，經常有人提出：如果任務的資源需求比可用資源量多，希望引擎儘可能滿足任務的需求、儘可能分配所有資源，但又想避免一個完全超出資源承受能力的分配方案。其實這種情況在排產、VRP等場景下相當常見。各位遇到這種場景，可以考慮上述兩種辦法加以處理。

本系列文章在公眾號不定時連載，請關注公眾號（搜「讓APS成為可能」或掃以下QR Code）及時接收,二維碼：

如需了解更多關於OptaPlanner的應用，請發電郵致：[email protected]
或到討論組發表你的意見：//groups.google.com/forum/#!forum/optaplanner-cn
若有需要可添加本人微信（13631823503）或QQ(12977379)實時溝通，但因本人日常工作繁忙，通過微信,QQ等工具可能無法深入溝通，較複雜的問題，建議以郵件或討論組方式提出。(討論組屬於google郵件列表，中國網路可能較難訪問，需自行解決)

Tags: APS OptaPlanner 生產計劃規劃引擎