馮曉川 李江潔

摘 要：針對BTO環(huán)境下汽車供應(yīng)鏈的敏捷性、精益性需求，提出基于延遲策略、模塊化制造的實時排程模型與算法，該模型將一般裝配過程分解為簡單裝配過程，基于簡單裝配排程的線性搜索算法，迭代生成一般裝配過程的排程。再通過設(shè)備排程狀態(tài)與訂單工序需求等實時數(shù)據(jù)進(jìn)行仿真，仿真結(jié)果表明該排程模型及實時算法可以縮短總裝提前期，并能保持系統(tǒng)對定制部分操作時間波動的穩(wěn)定性.此排程模型與算法具有較好的效率，能用于詢單、調(diào)度和協(xié)同等的實時決策支持。

關(guān)鍵詞： BTO;實時供應(yīng)鏈;汽車行業(yè);總裝排程;實時算法

中圖分類號： TH 166文獻(xiàn)標(biāo)志碼：A文章編號：1006-8023（2018）06-0067-04

Research on Real-time Scheduling of Automotive Supply Chain under Builder-to-order

FENG Xiaochuan， LI Jiangjie

（Department of Information， Beijing City University， Beijing 100086）

Abstract：This paper proposes a real-time scheduling model and algorithm based on the delayed different strategy and modularity oriented to the agility and lean character of automotive supply chain. We decomposed general assembly process into ordinary assembly process， and modeled real-time assembly scheduling and proposed the algorithm flow based on the linear search algorithm of ordinary assembly process. The simulation result with real-time data of device scheduling state and order demand shows that the real-time scheduling model can short the dynamic general assembly lead time and keep the stability for operation time fluctuation of customized components， and the algorithm is so efficient that it can support real-time decision in order quotation， dispatch and coordination.

Keywords：BTO; real-time supply chain; automotive industry; general assembly scheduling; real-time algorithm

0 引言

面向訂單生產(chǎn)BTO（Build-to-order）的制造模式不限于通過零部件的組合配置來滿足客戶的個性化需求，對部分零修改部件按訂單生產(chǎn)而大部分基于庫存組合來實現(xiàn)，介于ATO與MTO之間，英國的3DayCar及歐盟的ILIPT研究項目都指出BTO是未來汽車生產(chǎn)的主要模式。總裝及MTO部分零部件的生產(chǎn)對訂單的按時交付至關(guān)重要，相應(yīng)的排程對在制品庫存WIP、資源利用及訂單變更的響應(yīng)都具有較大影響[2] 。供應(yīng)鏈排程方法很多，比如模糊排程[4]、實時排程[3]及執(zhí)行過程中對不確定性的響應(yīng)問題[5-6]。模糊排程基于智能算法考慮了過多的因素，其算法的效率和實時性不足為：現(xiàn)有的實時排程算法則將樹狀的裝配過程線性化分解，同一作業(yè)出現(xiàn)在多個線性過程，產(chǎn)生同步約束，這樣的處理增加了問題的復(fù)雜度。本文通過延遲策略和模塊化制造將總裝過程分成MTS與MTO兩段，個性化需求部分靠近裝配后段，復(fù)雜的總裝過程可以作較大程度的簡化;MTO零部件供應(yīng)商與總裝企業(yè)緊密集成，RFID、移動互聯(lián)網(wǎng)等實時技術(shù)的發(fā)展，都為MTO零部件供應(yīng)商與總裝企業(yè)間訂單變更、供應(yīng)鏈執(zhí)行的實時信息共享提供了條件。本文研究BTO環(huán)境下的實時排程方法，著重研究總裝過程的分解、模型建立與實時算法。

1 裝配過程分解

一般的裝配過程在Z個工序完成，用集合表示為{ A1，A2，…，AZ }，每一個工序AZ需要裝配lZ （lZ≥2）個零部件（序號用j表示），每一個零部件在工序z的裝配可以分解為一系列的操作，表示為u = 1，2，…，Mj，Z;j = 1，2，…，lZ;? z = 1，2，…，Z。每一個最小的加工裝配過程可以用一個三元關(guān)系表示為（u，j，z），記為i，一般的裝配過程如圖1所示。圖1中有填充的方框表示物流過程，物流資源擴(kuò)充容易，這類過程受資源約束小;只有一個前驅(qū)的過程表示簡單加工過程，有多個前驅(qū)的過程表示裝配過程，沒有前驅(qū)的表示從倉庫領(lǐng)貨及定制件的采購或加工過程。

操作u可以在Ku臺設(shè)備上完成，表示為，每臺設(shè)備的空閑時間段（可用時間窗口）用區(qū)間集合表示為。所有設(shè)備可用時間窗口按以下規(guī)則排序：對于任意的k1≠k2，并用k1，k2∈{1，2，…，ku}，時間窗口在下列情況下排在時間窗口的前面。

，或者并且基于以上的排序原則，對所有Ku臺設(shè)備的可用時間窗口進(jìn)行排序，得到操作u可以排程的時間窗口序列，表示為，每個時間窗口的上標(biāo)對應(yīng)著相應(yīng)的設(shè)備編號。

一般的裝配過程排程比較復(fù)雜，可以將其中的部裝看成一個整體，每個裝配操作的前驅(qū)就是簡單的線性操作過程，排程得到部裝的開工時間后，用同樣的方法對部裝的前驅(qū)進(jìn)行排程，迭代完成整個排程工作。簡化過程可以從裝配的最后一道工序開始，使所有裝配的所有前驅(qū)都成為線性過程。如果某個節(jié)點有多個前驅(qū)，則該線性過程分解停止，進(jìn)行其它前驅(qū)過程的搜索;將有多個前驅(qū)的節(jié)點進(jìn)行類似的分解，讓所有的過程都只有最后一個節(jié)點有多個前驅(qū)，其所有前驅(qū)為線性過程。圖1的一般裝配過程，可以分解為圖2的簡單裝配過程。

2 模型建立

用t（u，j，z）表示操作（u，j，z）的開工時間，用θ（u，j，z）表示該操作的標(biāo)準(zhǔn)工時，δ（u，j，z）表示該操作完成時間波動上限，即完成操作的最大時間為θ（u，j，z）+δ（u，j，z）。

排程的目標(biāo)是在交貨期約束下，使裝配工序特別是定制部分的開工時間最晚，以讓訂單修改等需求不確定性的影響最小化。目標(biāo)函數(shù)和約束條件表示為：

J = max（t（ul，jl，z+l）+θ（ul，jl，z+l）） 。? ? ? ?（1）

s.t.：

u（u，j，z）∈ [θ（u，j，z），θ（u，j，z） + δ（u，j，z）]，（u，j，z）。 （2）

t（u，j，z）+ u（u，j，z）≤ t（ul，jl，zl） 。? ? ? ? ?（3）

（u1，j1，z1）是（u，j，z）的后繼操作。

J < delivery time 。? ? ? ? ? ? ? ? ? ? ? ? （4）

公式（1）目標(biāo)函數(shù)表示當(dāng)前裝配工序最晚完工時間;公式（2）表示工時約束，實際工時在標(biāo)準(zhǔn)工時上有一個最大偏差;公式（3）表示前驅(qū)后繼約束;公式（4）表示完工時間必須早于交貨期。

3 實時算法

排程除滿足上一節(jié)的目標(biāo)外，算法實時性要求對交貨期詢單和執(zhí)行過程的調(diào)度也具有重要意義。實時排程可分為3個步驟：①一般裝配過程的分解;②簡單裝配排程;③總裝排程由簡單裝配排程迭代產(chǎn)生。一般裝配過程到簡單裝配過程的分解見前面介紹，簡單裝配排程由線性分支組成，只有一個裝配操作即根節(jié)點，倒排搜索即可完成，迭代形成總裝排程的算法流程如圖3所示。

圖3中p表示各工序開工時間，q表示各工序完工時間，其它參數(shù)同前面所述。首先根據(jù)訂單交貨期計算最后一道裝配工序的開工時間，然后計算各前驅(qū)過程鏈的排程，對每一過程鏈，由后往前根據(jù)工序時間和資源時間窗口確定最晚開工時間。如果某一過程鏈中存在裝配節(jié)點，將該節(jié)點的開工時間視為簡單裝配節(jié)點，重復(fù)上述過程，迭代完成訂單排程計算。

4 實例分析

汽車裝配過程復(fù)雜，但BTO環(huán)境下基于延遲策略與模塊化思想，將定制部件和與之相應(yīng)的裝配，通過供應(yīng)鏈設(shè)計將其配置在總裝的后期完成，將標(biāo)準(zhǔn)部分的裝配及流水線操作部分簡化為整體，以降低計算的復(fù)雜度。本文假設(shè)將這一過程簡化為圖1，依據(jù)總裝工序搜集相應(yīng)設(shè)備及其在某訂單交貨期前后的排產(chǎn)情況，采用基于圖3流程開發(fā)的算法進(jìn)行仿真計算，可以得到圖4中填充模塊的仿真排程結(jié)果。圖1總裝過程各工序的標(biāo)準(zhǔn)工時及其波動見表1，工序所依賴設(shè)備的已有排程情況如圖4所示，矩形方框表示設(shè)備的空閑即可用時間，不同高度代表不同的設(shè)備。仿真排程結(jié)果在圖4中表示為實填充，排程操作所依賴的設(shè)備用斜線填充方框代表的設(shè)備編號決定。

5結(jié)束語

本文將實時算法用于BTO環(huán)境下的總裝排程問題，對每個操作，每一設(shè)備有多個可用的時間窗口，同類設(shè)備的可用時間窗口形成更大的集合，可以進(jìn)行統(tǒng)一的排序。在執(zhí)行過程中，每個操作實際完成時間會在θ（u，j，z）與θ（u，j，z）+ δ（u，j，z）間形成微小的時間窗，需要對未執(zhí)行的操作進(jìn)行調(diào)整，以提高資源利用率。

實時排程針對訂單進(jìn)行，各操作可視為原子操作，不需拆解，搜索加工設(shè)備的可用時間窗口較快。因此，可用于BTO環(huán)境下對個性化需要部分的操作進(jìn)行定制，實時總裝排程也可用于輔助詢單過程以及執(zhí)行過程中調(diào)度與協(xié)同的排程重算。

【參 考 文 獻(xiàn)】

[1]GUNASEKARAN A， NGAI E.W.T. Build-to-order supply chain management： A literature review and framework for development[J]. Journal of Operations Management， 2011，23（5）： 423-451.

[2]PARRY G， GRAVESA. Build to order： the road to the 5-day car[M].London： Springer-Verlag， 2008.

[3]PROTH JM. Scheduling： new trends in industrial environment[J].Annual Reviews in Control， 2007，31（1）： 157-166.

[4]DEMIRLI K， YIMER A D. Fuzzy scheduling of a build-to-order supply chain[J]. International Journal of Production Research， 2008，46（14）：3931-3958.

[5]KRAJEWSKI L， WEI J C， TANG L L.Responding to schedule changes in build-to-order supply chains[J].Journal of Operations Management， 2005，23（5）：452-469.

[6]AYTUG H， LAWLEY M A， MCKAY K. Executing production schedules in the face of uncertainties：A review and some future directions[J]. European Journal of Operational Research， 2005， 161（1）：86-110.

[7]FALISZEWSKI P， HEMASPAANDRA E， HEMASPAANDRA L A. The complexity of manipulative attacks in nearly single-peaked electorates[J]. Artificial Intelligence， 2014， 207： 69-99.

[8]ERDELYI G， LACKNER M， PFANDLER A. Computational aspects of nearly single-peaked electorates[C]. Proceedings of the 27th AAAI Conference on Artificial Intelligence （AAAI-13）， Bellevue， USA， 2013：283-289.

[9]CORMAZ D， GALAND L， SPANJAARD O. Kemenyelections with bounded single-peaked or single-crossing width[C]. Proceedings of the 23rd International Joint Conference on Artificial Intelligence （IJCAI-13）， Beijing， 2013：76-82.

[10]MOULIN H. On strategy-proofness and single-peakedness[J]. Public Choice， 1980， 35（4）：437-455.

[11]MASSO J，BARREDA I M D. On strategy-proofness and symmetric single-peakedness[J]. Games and Economic Behavior， 2011， 72（2）：467-484.

[12]BORDER K C， JORDAN J S. Straightforward elections， unanimity and phantom voters[J]. Review of Economic Studies， 1983， 50（1）：153-170.

[13]LU P Y， SUN X R， WANG Y J， et al. Asymptotically optimal strategy-proof mechanisms for two-facility games[J]. Electronic Commerce， 2010： 315-324.

[14]FOKAKIS D， TZAMOS C. Winner-imposing strategy-proof mechanisms for multiple facility location games[C]. Proceedings of the Sixth International Workshop on Internet and Network Economics （WINE-10）， Stanford， USA， 2010：234-245.

[15] 智川，李志健，冷彩鳳.色度空間轉(zhuǎn)換模型評價體系的研究[J].陜西科技大學(xué)報， 2013，31（4）：20-23.

ZHI C， LI Z J，LENG C F. Study on evaluation system of color space conversion methods[J]. Journal of Shanxi University of Science & Technology， 2013，31（4）：20-23.

[16] FOKAKIS D， TZAMOS C. On the power of deterministic mechanisms for facility location games[C]. International Colloquium on Automate， Languages， and Programming， 2013： 449-460.

[17]LU P Y， WANG Y J， ZHOU Y. Tighter bounds for facility games[C]. Proceedings of the Fifth International Workshop on Internet and Network Economics （WINE-09）， Rome， Italy， 2009： 137-148.