陳 露，陳淮莉

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

1 研究背景及意義

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

圖1 中國(guó)2005～2017汽車(chē)銷(xiāo)量

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

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

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

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

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

3 模型建立

3.1 問(wèn)題描述

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

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

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

圖2 原型樣車(chē)測(cè)試流程圖

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

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

表1 模型參數(shù)

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

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

j＜k表示測(cè)試j必須在測(cè)試k之前完成；

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

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

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

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

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

3.5 約束條件

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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