陳 露，陳淮莉

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

1 研究背景及意義

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

圖1 中國2005～2017汽車銷量

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

2 國內(nèi)外研究現(xiàn)狀

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

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

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

3 模型建立

3.1 問題描述

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

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

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

圖2 原型樣車測試流程圖

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

3.2 參數(shù)設置

表1 模型參數(shù)

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表示在同一原型上的最后一項測試集合。

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

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

3.5 約束條件

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

4 算例分析與結(jié)論

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

表2 給定數(shù)據(jù)集的具體信息

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

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

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

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

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

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

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

5 結(jié)束語

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