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

陳 露，陳淮莉

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

1 研究背景及意義

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

圖1 中國2005～2017汽車銷量

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

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

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

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

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

3 模型建立

3.1 問題描述

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

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

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

圖2 原型樣車測試流程圖

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

3.2 參數(shù)設(shè)置

表1 模型參數(shù)

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

3.3 考慮兩個(gè)測試之間的關(guān)系，j,k ∈J

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

j～k表示測試j和測試k必須在同一個(gè)原型上進(jìn)行；

j≠k表示測試j和測試k不能在同一個(gè)原型上進(jìn)行；

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

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

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

3.5 約束條件

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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