BTO環境下的汽車供應鏈實時排程研究

馮曉川 李江潔

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

關鍵詞： BTO;實時供應鏈;汽車行業;總裝排程;實時算法

中圖分類號： TH 166文獻標志碼：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 引言

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

1 裝配過程分解

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

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

，或者并且基于以上的排序原則，對所有Ku臺設備的可用時間窗口進行排序，得到操作u可以排程的時間窗口序列，表示為，每個時間窗口的上標對應著相應的設備編號。

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

2 模型建立

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

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

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）目標函數表示當前裝配工序最晚完工時間;公式（2）表示工時約束，實際工時在標準工時上有一個最大偏差;公式（3）表示前驅后繼約束;公式（4）表示完工時間必須早于交貨期。

3 實時算法

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

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

4 實例分析

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

5結束語

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

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

【參 考 文 獻】

[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] 智川，李志健，冷彩鳳.色度空間轉換模型評價體系的研究[J].陜西科技大學報， 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.