日本訂閱制APS(先進規劃排程系統) 台灣代理商

生產排程

APS技術中的多目標規劃問題


在進行APS(先進規劃排程系統)系統開發時,絕大多數情況下是需要考慮多目標的。但面對多目標問題進行規劃求解時,我們往往極容易因處理方法不當,而影響輸出結果,令結果與用戶期望產生較大差別。事實上很多時候用戶,面對此類問題也無法給出一個確定的合理的期望,因為多個目標混合在一起的時候,產生覆雜的規劃邏輯,用戶自身也會被迷惑,到最後就錯誤地提出一些所有目標都達到極致的“完美”計劃要求;但客觀上是不存在這種“完美”計劃的。

  本文將以制造業中的生產計劃為背景,介紹APS技術中的處理多目標規劃問題相關知識與經驗,介紹多目標規劃問題的求解,是如果反映在生產計劃優化系統的設計過程中的。在企業供應鏈的其它環節的優化過程,同樣適用此本文所述的理論。

多目標規劃在現實情況下的體現
  在制造業中創建生產計劃時,考慮的因素非常多且繁雜。包含客觀必須符合的規則,稱為硬約束;以及作為計劃優劣的衡量指標、可量化、可違反的規則,稱為軟約束。下面對這兩種約束進行詳細分析。

硬約束
  以制造業的生產環節為例,硬約束是指那些在制定生產計劃過程中,是一種定性的制約因素,其對應的約束必須遵循;一旦違反,會令計劃不可行。也就是說,對於此類制約因素,對其考量只有True(符合)/False(違反)種結論,而不考量其違反程度是大或小。例如產品的工藝要求,生產任務對機台的參數要求,生產工藝產生的環境影響因素等,都是硬性指標,一旦有違反,會令計劃無法執行。再例如嚴重違反政策法規的制約因素,都會被定義為硬約束,力求在計劃過程中無條件、零容忍地遵守。

  在對問題進行數學建模,並使用求解器進行規劃求解的過程中,硬約束將會作為約束條件出現,也即所建立的數學模型中的s.t.(subject to)部分。可以設想到,若一個生產計劃問題可以被認定為規劃問題(不管是線性規劃,還是非線性規劃),其數學模型的s.t.部分將會非常覆雜。事實上在實際生產環節中,絕大部分情況是難以將生產計劃問題直接地抽象成數學模型的。而且對於普通的工程人員而言,將整個系統中的生產計劃制約因素和優化目標都建模成數學模型,再進行規劃求解,要求也是極高的。普通的軟件工程人員,並未受過該方面的專業訓練,並不具備這方面的能力。這也是為什麽一些對業務邏輯表達方式更友好,描述語法語義更豐富,通用性強的規劃引擎(其核心是一個求解器 – Solver),更容易在軟件工程實踐中被成功應用。

軟約束
  從業務的角度看來,軟約束也是制約因素的一種,其目的是讓生產計劃存在一些可議價的、定量的因素,令到計劃生成過程中,趨向我們意願發展。也是說,相對硬約束而言,軟約束是有“商量,議價”余地的。最好的情況下,APS系統生成的生產計劃,其硬約束、軟約束都完全符合。但是因為實踐生產環節中,存在大量客觀因素,有些軟約束是不可避免要被違反的,甚至系統本身設計的邏輯中,已經安排了把一些因素設計為必然會違反的約束,其目的是給規劃引擎指明一個優化方向。即通過此類趨向約束,向規劃引擎提供一個信息 – “盡管規劃所得的解可以違反這些軟約束,但你違反的程度越低,得到的解越優,也就是得到的計劃越優化。”,軟約束在現實業務中,通常對應於成本、機台開動率、生產效率、訂單交期等。也就是說,軟約束是一種定量約束,整個規劃的目標首先是確保硬約束全部符合,再在此基礎上再力求提高軟約束的符合程度。當因客觀原因,某個軟約束無法完全符合時,則進一步尋找軟約束違反得更少的方案。

  在對規劃問題進行建模時,因為軟約束是一個為規劃運算指導方向的組成部分,通常會把它作為規劃目標體現在數學模型中。例如進行生產計劃優化程序設計時,可以把成本最小化作為規劃目標。也就是說,在生成生產計劃時,在保證工藝參數、安全特性等硬條件不被違反的前提下,尋找出最低成本的計劃方案,就是本次規劃運算的目標。在建立的數學模型中,軟約束體現為目標函數。例如,成本最小化在模型中會表示為 Min f(x) (其中f為成本函數).

硬約束與軟約束存可以存在互相轉換的可能
  在實際業務環境中,某些因素被定義為硬約束或軟約束,是與當時具體的情形相關的。某一因素在特定情況下需要確保不違反,則需要被定義為硬約束。但相同的因素,有可能在另外的條件下,可以作出一定程度的讓步,甚至放棄;則可定義為軟約束。

  例如產品交期,對於某些訂單而言,因為其涉及到的合同存在重大責任,或延期會影響到企業商譽,進而影響企業生存,必須保證交付不延誤,不存在任何讓步的空間;因此,需要被定為硬約束。但有些訂單其優先級較低,延誤的損失遠比為了確保不延誤而付出的代價高,則有可能允許一定程度的延期。又如,某些生產活動,會對環境造成某種程度上影響,當政府監管機構對該影響未作出強制消除要求時,企業只會在其它更高優先級的因素得到保證的前提下,盡量減少此類影響的發生。但若政府對這種影響作出明確要求,並以法律法規形式作出限制,要求企業在生產活動中必須消除,否則將會觸犯相關法律法規時,此影響對應的制約因素,需要在制定生產計劃時,作為硬約束考慮,以確保不違規。

  因此,硬約束與軟約束在一定的環境條件下,存在互相轉換的可能。而在我們對規劃模型進行設計時,這種轉則是性質上的改變。當一個因素作為硬約束存在時,它是反映在規劃模型的限制條件中的。而當它轉化為軟約束時,建模時則需要把該因素作為優化目標考慮。

多個優化目標
  在常見的運籌優化教材中多目標優化相關的章節里,涉及規劃問題的數學模型,很多例子都是由多個約束條件及一個優化目標組成的。即對應於實際規劃問題中,多個硬約束和一個軟約束組成。例如各種線性規劃例子中出現的,某工廠的生產活動在若幹項約束條件下,實現利潤最大化的情況。其【利潤最大化】就是該規劃問題的唯一優化目標,利潤函數也是唯一的目標函數。

  但是在實的規劃系統(例如各APS系統)中,面對更為覆雜的規劃情況時,其規劃目標往往不只一個,有可能多個。且這些目標往往錯綜覆雜,有可能存在兩個方向相同的目標,也可能兩個目標是相反的,即互相制衡的。總之,這些目標之間沒有直接的可比性。

  面對這種情況,在設計規劃程序時會變得相當覆雜。在運籌學上,此類問題稱為多目標規劃問題;其數學模型中存在多個目標函數。大家可以想象中,當存在多個目標函數時,其優化的結果往往是無法令所有目標函數都能得到極值的。因此,多目標規劃問題是運籌這中較前沿、較覆雜的問題。因為多個目標對應的指標有可能不存在相關性。因此,並不存在一個所有目標均達到最優的解。只能在多個目標之間做權衡取舍,或將多個目標做出某種混合關聯,得到一個單一目標規劃問題。

求解多目標優化的困惑
  因為多目標規劃問題存在多個目標需要同時被優化,所有這些目標都有一個對應的最優解,但各個目標具有不同的方向,在規劃模型中,每個目標通過一個向量表示。也即不可能存在一個所有目標都達到最優狀態的解決方案存在。

  因此,我們求解此類問題時,只能根據實際情況對不同目標進行個性處理。分別:

是對目標進行優先級劃分,確保優先級越高的目標,其達到優化的程度越高。
根據目標的重要程度,對各個目標設置加權值,令求解器在運算過程中,根據比例來確定各個目標的重要程度,從而得到相應的解決方案。
對多目標問題求解,令其達到帕累托最優狀態,在該狀態中會提供一個解決方案集,用戶可以在此解決方案集中選擇一個解決方案。
多目標規劃問題的處理辦法
  根據上述的多目標規劃,常用的處理方法有三種,分別是:

按各目標的優先級,分層處理,每一層只處理一個目標。從最高優先級目標開始,找出該目標最優狀態下的解決方案集。再在此集合中找出次優先級目標的最優解方案子集。如此類推直到完成所有目標的尋優運算。 獲得解決方案中,即為該多目標規劃問題,目標分層的解決方案。
將多個目標桉權重轉化為單一目標。根據各目標對應的業務因素的重要程度,設置相應目標的權重。通過權重的計算比例,來獲得一個綜合了各個目標的、新的單一目標,再對此新產生的單一目標求極值,所得的解決方案作為該問題的最優解決方案。
對問題進行優化,令其達到帕累托最優狀態。獲得處於此狀態下的非劣最優解集,供用戶來決定最終選用的方案。關於帕累托最優相關的資料,大家可以自行了解。通俗地講,因為多目標規劃問題中,各個目標是除了有輕重緩急外,還有方向性的,目標可表示為一個向量。帕累托最優,表示對多目標規劃問題的各個目標求最優值,當達到這麽一個狀態:不存在對一個目標進一步改善,而不影響其它目標,即為帕累托最優狀態。大家可以設想,這種狀態下的解決方案不可能只有一個,而是一個解決方案集。
多目標規劃問題詳解
  下面,將對上述前兩種處理辦法進行詳細說明。因上述講到關於對多目標規劃問題進行優化,達到帕累托優化狀態,進而獲得非劣解集。目前各個求解器暫時仍未有成熟的方案支持,本文暫不討論此方法。

  在求解多目標規劃問題時,關於求非劣解集的方法。因目前本人尚未接觸過較成熟的、可以對多目標規劃問題,求得非劣最優解集的引擎技術;因此,暫未有辦法對該方法展開討論。關於通過Optaplanner求非劣解集的方法,我曾請教過該項目負責人Geoffrey先生 ,他覺得以目前項目的狀態,若Optaplanner中添加此功能,需要修改的工作量相當大,暫時還未有關於此功能的具體開發計劃;除非該功能真正具體相當的價值。也這是各個求解器在多目標規劃方面類似的地方。因為多目標求解領域,目前在學界深入研究相對非多目標規劃更少,相關的成果也沒有單目標規劃成熟。而且多目標規劃在一定程度及範圍內,確實是應該進行進一步加工,形成單目標規劃,即有相應的替代方案。因此,求非劣解集功能目前並非各大求解器的主要發展方向。

將目標按優先級分塊層處理
  對多目標進行分層按優先級由高到低進行尋優。此方法可理解為,對於問題中需要優化的目標,根據實際業務情況,對其進行優先級劃分並從高到低排序。優先級高的目標,相對優先級低的目標,享有壓倒性的優先保證權。在保證對高優先級的目標達到最優的前提下,再去考慮次優先級目標的優化取值問題。即一個目標的優化範圍,是在其上一級目標優化解決方案子集內進行求解的。

  例如,在實際的智能生產計劃系統設計過程中,存在三個目標,它們的優先級由高到低排列,分別是【保證交期】、【提高機台利用率】和【降低成本】。那麽在對這個問題進行規劃求解時,第一步可以不考慮【提高機台利用率】和【降低成本】兩個目標,只對【保證交期】一目標進行首次優化。當【保證交期】目標處於相對最優狀態時,將存在【提高機台利用率】與【降低成本】兩個目標取值不相同的解決方案集。下一步在將在此解決方案集的基礎上,求【提高機台利用率】目標的相對最優的解決方案集;獲得【提高機台利用率】目標也為最優的解決方案子集。再進一步求得【降低成本】目標的相對最優方案。那麽,最終得到的方案,即為按【保證交期】 -> 【提高機台利用率】 ->【降低成本】遞減的相對最優方案。

  通過Optaplanner實現上述步驟時,只需將【保證交期】、提高機台利用率】和【降低成本】三個目標設計對應的軟約束(大家應該知道為什麽要定義為軟約束),通過BendableScore評分機制,定義為由高到低的三個層次即可。Optaplanner在求解時,將會按上述邏輯,根據不同層次的約束分數的優先次序,來求得相對最優解。

將多個目標轉化為單一目標處理
  有些情況下某些規劃問題,因為目標之間無法劃分明確的優先級,因此,無法對多目標進行分層來逐一求最優解。例如,在特定情況下,有些目標優先級相對較高,但同樣的問題在另外一種情況下,它的優先級則相對較低。因此,無法呈現出目標間優先級高低關系,也即無法在規劃開始之前,就確定各個目標的優先次序。

  但是,這種問題的不同目標的優先級,存在一種“由量變達成質變”的特性。一個目標無法達成,需要被扣除約束分,當扣除分值達到一定量時,它會產生質的變化,會變成一個相對其它目標更為重要的目標。還是以生產計劃中的【保證交期】與【降低成本】兩個目標為例。應該先對交期無法保證時(即【保證交期】目標無法達成),企業所承受的損失量化成貨幣價值。而生產成本也需要以貨幣價值體現。通常情況下,為了強制保證交期,可能需要付出相對更高的成本代價。當為了保證一個訂單的交期而承受的成本價值,高於該訂單延期所遭受的損失貨幣價值時,【保證交期】目標的優先級,將會變得比【降低成本】目標的優先級更低了。這個時候我們希望的是放棄【保證交期】目標,從而令計劃的整體成本得到降低。

  要設計上述邏輯,從Optaplanner的實現方法來看,表面上是簡單的。我們只需要確定好交期的貨幣價值與成本的貨幣價值即可。當引擎在優化運算時,會根據各個可能解決方案的實際的交期和成本屬性,自行對比並選擇較優的解決方案。但看似簡單的設計邏輯,在實現起來卻非常具挑戰性,其難點在於如何分配這兩個目標的權重。這個就需要從業務上明確地甄別出各個目標之間的權重比例。並需要經過眾多實際數據、多輪的規劃進行反覆驗證,才能得到相對最佳的權重比例。而且通過這種比例關系規劃出來的結果,非常不直觀,對結果的驗證也需要花費相當大的精力和時間。但這是一個相對最佳的處理多目標規劃的辦法之一。

總結:多目標規劃的本質
  盡管多目標規劃問題,令運籌優化問題變得更覆雜,但它卻是現實世界中是無時無刻存在的。正是多目標規劃問題,才能真徹地反映現實世界的情況。它反映的是事物的多樣性、沖突性和真實性。雖然單目標規劃問題相對容易解決,也可以求得極佳的解決方案,但它只是現實世界的很少一部分,甚至是理論世界才存在的問題。僅能作為運籌規劃的基本解決方法。真正需要解決的問題,還是相當覆雜的多目標規劃問題。這也是為什麽APS技術在工程應用中實現難度大的最重要原因之一。多目標規劃問題,不僅對於專業的工程人員來說難以解決,對於普通用戶來說,對於APS輸出的解決方案的理解與分析,也存在相當大的挑戰,從而令很多用戶對APS難以接受,甚至而失去信心。