基于約束規劃的整車測試排程問題研究

陳 露，陳淮莉

（上海海事大學 物流科學與工程研究院，上海 201306）

1 研究背景及意義

汽車工業一直是經濟發達國家的支柱產業之一，在國民經濟中具有重要的地位。各國經濟發展的經驗表明，保持經濟的快速增長離不開若干個高于平均增長速度的主導產業的帶動。汽車工業是綜合性工業，具有較強的產業波及效果和帶動作用。汽車工業是附加值很高的加工工業，它的發展帶動了與之相關的鋼鐵，機械，電子電器，橡膠等行業的發展，是創造社會財富，提高國民收入的重要來源。圖1所示為歷年來中國汽車銷量統計，數據來源于中國產業信息網[1]。

圖1 中國2005～2017汽車銷量

在汽車企業，在新車型大規模生產之前，汽車制造商通常對所研發的新車輛進行數百次測試。由于是研發的新車型，配套的生產線還不存在，這些樣車原型大部分是手工制造，價格一般都比較昂貴。如果測試按照合適的順序排列，大部分原型可以進行多個測試，這樣就大大地節約了制造成本。這個問題類似于并行機的調度問題，原型和測試對應著機器和作業。因此需要合理的分配測試的順序，忽略原型的不同變型之間的成本差異，盡量減少所使用的原型數量及最大完工時間，確保盡快投入生產。

2 國內外研究現狀

原型樣車測試排程類似于同型機并行調度問題，這是實際制造業生產過程中一類典型的調度問題。早期學者Garey和Johnson證明了在機器數量模糊的情況下，以最小化加工時間為目標的并行機調度屬于NP-Hard問題[2]。Pinedo在其文章中指出并行機調度已經引起了眾多學者的廣泛關注與研究，并在許多行業有了成熟的發展與應用[3]。汪恭書等[4]研究了目標函數以最小化總加權完成時間，工件具有最遲開始處理時間的并行機實時調度問題，建立了混合整數規劃模型并融合了拉格朗日（LR）和列生成（CG）的混合算法。Scheffermann等[5]針對考慮投放時間、截止時間以及其他條件的調度問題，提出一種啟發式搜索策略，但利用概率統計的方法調節影響原型樣車數目的參數仍有一定的困難。Sadykov和Wolsey[6]針對考慮投放時間和截止時間的并行機任務分配問題，提出了整數規劃和約束傳播求解方法。采用區間情景來刻畫加工時間，并采用最小最大遺憾原則，許曉晴等[7]研究了不確定加工時間下同型并行機的魯棒排程。

目前，計算機仿真技術已經應用于執行各種測試，例如在駕駛室進行傳熱模擬、風洞試驗、碰撞模擬等。然而，Kohlhoff[8]堅持使用真實的原型樣車進行測試，畢竟計算機仿真與模擬的準確性和可靠性有限。不考慮組件要求和樣車變體選擇過程，Schwindt[9]應用混合整數線性規劃求解了簡化的調度問題。

除了這些以前的研究，有幾個與汽車制造商的汽車測試相關的項目。他們的問題特點略有不同，并使用各種不同方法解決。然而，他們都有相同的目標，就是降低測試過程的成本。對于福特汽車公司，Lockledge等[10]應用多級數學規劃模型優化原型船隊。第一步，他們確定所有測試的組件要求所需的變種數量。第二個模型確定每個變量的最低數量的汽車，使得所有的測試可以在到期日期之前執行。Bartels和Zimmermann[11]考慮了組件的要求和時間的限制，只是一些額外的約束略有不同。他們考慮部分有序的破壞性測試，而不是在相同或不同的原型執行測試。例如，駕駛測試，可能會損壞機箱，使這個原型不再適合進行聲學測試。因此，此驅動測試在聲學測試之后執行，或者它們被分配在不同的原型上。他們提出了一個混合整數線性規劃配方可用于解決小規模的問題。為了處理較大的情況下，他們提出了一種啟發式方法的基礎上的優先級規則。Zakarian[12]為通用汽車卡車集團開發了一個分析模型和決策支持工具，以評估性能的產品驗證和測試計劃。他模擬與測試時間和產品故障相關的不確定性，以確定驗證計劃中使用的車輛數量和完成測試的百分比之間的權衡。

3 模型建立

3.1 問題描述

大部分汽車制造商都有專門生產汽車原型的工廠，由于工廠空間容量有限，汽車原型依次按照要求制造出來，這就會產生每個原型的可用時間。在原型制造之后，原型需要初始設置過程，其持續時間取決于原型的所選變體以及該原型上計劃的測試序列。例如，在執行腐蝕測試時原型必須涂漆，而在執行碰撞測試時就不需要涂漆。因此只有建立好指定的原型才能進行測試，而且有效的排程必須滿足所有的時間約束。圖2為原型樣車（prototype）測試示意圖，中間的橫線代表用于測試的m輛原型樣車，這些原型樣車用來完成右邊所示的n項測試，左邊所示為準備完好的l個樣車變體。一輛樣車的各個組成部件有多種類型，不同類型的組成部件之間會有大量的組合方式，這些組合方式是為了測試不同組件之間的協調性和相容性，滿足每項性能測試的特殊要求。

本文使用約束規劃（Constraint Programming）來求解測試排程問題。原型樣車的數量是離散的，而完工時間是連續的。因此本文中采用經典的參數化方法，即在所有約束條件下確定了原型的數量并最小化了完工時間。最初假設大量的原型，使得完工時間只取決于時間的限制。然后反復減少原型的數量，然后再解決問題，這就產生了原型數量和完工時間之間的關系。

約束規劃是制定和解決一個優化問題的另一種確定性方法。它最初是為計算機科學應用，經過幾十年的發展，約束規劃已經在規劃、調度、生物信息學、車輛路徑、配置等領域得到了廣泛的應用。要應用約束規劃，首先將需要描述的問題制定作為一組決策變量和約束。每個變量有自己的有限集的可能值（域），而約束限制的值，變量可以同時采取。約束規劃的解決方案是一個值分配給每一個變量，使所有的約束滿足。接下來，可以指定一個搜索方案來描述求解器如何從可能的分配中進行枚舉，到實現一個解決方案。當搜索過程中出現矛盾時，約束規劃有一個叫做回溯的功能來繼續嘗試其他可能的決定。

圖2 原型樣車測試流程圖

約束規劃在表達約束方面優于混合整數規劃（MILP），因為它不局限于線性不等式。例如，它支持邏輯表達式，像if…else，而不是使用許多復雜的線性不等式來表示機器的資格約束，這樣復雜的調度問題就可以用邏輯表達式自然地表示出來。

3.2 參數設置

表1 模型參數

VMj?V 表示可以進行測試j∈J的 原型變體集合。由于測試時不間斷的，測試j的完成時間cj必須滿足， 最大完成時間cmax= maxj∈J{cj}。此外，每個原型i?I有 一個可用的時間ai，原型建立時間Svi，由變體vi決定；在原型制造時，一些組件無法及時到達并進行組裝，原型交貨時間為yv，變體v的建立被延遲，因此測試時間必須在時間max{ai+svi,yvi}之后才能開始進行測試。

3.3 考慮兩個測試之間的關系，j,k ∈J

j＜k表示測試j必須在測試k之前完成；

j～k表示測試j和測試k必須在同一個原型上進行；

j≠k表示測試j和測試k不能在同一個原型上進行；

JLast?J表示在同一原型上的最后一項測試集合。

在用約束規劃解決測試排程問題時，參照資源分配問題引入向量[t,p,c,C]，t=[t1,…,tn]表示測試起始時間向量，p=[p1,…,pn]表示每項測試處理時間向量，c=[c1,…,cn]表示工作消耗率向量，C是機器容量（machine capacity）。是時間t在進行中的任務集合，如果在有效的時間中所有時間t都滿足，那么約束就是被滿足了。因此，所有測試工作的總消耗率不會超過機器容量C。設每個原型容量C=1，每個測試需要單個的原型，。

另外還需定義一些變量，每個測試j的起始時間tj必須在區間內，遵從投放日期和到期日的限制。表示測試j分配給原型i。表示原型i的變體。

3.5 約束條件

約束（1）確保完工時間不小于任何測試的完成時間。約束（2）和約束（3）規定測試必須在各自的投放和到期日期之間執行。約束（4）是資源約束，(tj|xi=i)表示分配到原型i上的測試開始時間的數組。約束限制了兩項測試在一個機器上同時執行。約束（5）表示防止將測試分配給不具備測試所需條件的變體的原型。約束（6）和約束（7）確保機器i上的測試在原型的可用性之前開始。原型設置建立時間svi，組件可用時間yvi取決于變量vi的值，在問題得到優化之前這個值是未知的。CP方法的另一個好處是變量可以索引參數數組。約束（8）表示優先約束。約束（9）表示測試j和k在同一個原型上執行。約束（10）表示測試j和k必須在不同原型上執行。約束（11）表示測試?j∈JLast是分派到該原型上的最后一項測試。

4 算例分析與結論

為驗證本文解決策略的實用性及有效性，使用OPL Studio12.6實現了本文的算法。從現實的汽車制造廠商選取一組具有代表性的數據，測試個數從幾十到幾百個。表2給出了相關實例的計算結果，包括所需要的原型數量，計算時間，特殊約束等。對于測試數目比較大的數據，特殊約束對結果會產生比較大的影響。

表2 給定數據集的具體信息

本文是采用ILOG CPLEX Optimization Studio來求解的，除了標準的功能之外，OPL還有具體的調度模塊，包括解決調度問題的幾種功能。此外，它還具有良好的約束傳播技術和高效的搜索方法。表2中列出的變量和約束條件與前文中建立的模型相對應，給出了他們在計算過程中給出問題大小及其變化的規律，研究了給定原型數量與最大完工時間之間的關系。

表3 給定原型數量的最小化完工時間

表3顯示了計算結果。 對于每個數據集和給定數量的原型，使得完工時間最小化。 最初可以將m設置為一個很大的值，這意味著需要嘗試構建盡可能多的原型，以適應所有的測試。在某些情況下，例如如果在很早的到期日期內進行了很多測試，原型可能太晚了，這個過程不會產生一個可行的解決方案。但是，產生這個沖突的原因可能來自時間約束，而不是有限的原型數量。

在獲得結果之后，逐步減少原型的數量，看看它是如何影響到完工時間的。重復此過程，直至找到找不到可行的解決方案，或者計算無法在給定時限內終止。本文中規定數據1～3的時間限制為1小時，數據4的時間限制為6小時。例如在數據1中，從m=14開始，獲得330天的完工時間。如果只限制5個原型，仍然可以得到相同的最佳完工時間。但是，如果設定m=4，那么問題變得不可行，因為它沒有足夠的原型來執行所有約束的所有測試。

如果有足夠的時間，求解器要么可以為這個原型獲得最優解，要么證明這個問題是不可行的。但是，當問題規模變大時，所需的計算時間會迅速增長。由于實踐中計算時間的限制，解算器可能無法證明問題的不可行性。即使找到了可行的解決方案，只要搜索樹中還有未探索的節點，這樣就不能確定它的最優性。

結果表明，對于所有數據集，當給定原型的數量足夠大時，可以實現最優解。如果可用原型的數量減少，則找到任何可行的解決方案或證明最優性會變得越來越困難，盡管變量和約束的數量減少了。然而，如果原型的數量減少得足夠多，那么求解器可以再次在限制時間內證明不可行性，因為搜索空間已經大大縮小。例如，對數據3的計算表明，當m=20時，可以得到最優解。對于m=18或者m=19，在1小時的計算時間之后發現了可行解，但是，在9≤m≤17原型的范圍內有一個未知的差距，無法確定這個問題是否可以解決。

此外，應該注意的是，步驟m中的完工時間的最優值可以被認為是下一步m′=m-1中的完工時間的下限。這可以在約束更緊的情況下減小搜索空間。然而，這個想法在這里不能有效地實施，因為在發現最佳解決方案的每種情況下，完成時間實際上是由具有很長處理時間的測試的最早完成時間（rj+pj）確定的。通常在約束傳播期間，完工時間的下限已經被限制為大于或等于所有工作的最早完成時間。

5 結束語

研究了汽車原型的測試排程，并以實際數據進行算例分析，通過算例的分析證明模型是有效的，可以在測試關系約束和和時間約束的條件下，通過改變不同給定原型的數量，研究其與完工時間之間的關系。但本文建立的模型未涉及到測試過程中測試處理時間不確定的情況，有待進一步研究。