作者：宋靖宇

宋靖宇，曼海姆大學運營管理碩士，現就職於 DHL。

編者按

現實生活中，生產現場由於缺乏科學的管理，卡車的排程往往效率不高，容易出現擁堵現象。那麼，是否可以透過數學模型對該問題建模，提高其運作效率呢？本文介紹了卡車排程問題的數學模型，透過算例分析驗證：較先進先出的排程方法，數學模型排程法可提高 16%的運作效率。

1。簡介

本文旨在介紹一種解決現實場景中卡車排程問題的方法。該方法基於柔性作業車間問題（flexible job shop）模型，使用混合整數線性規劃來解決此類問題。

現實場景簡述如下：卡車到達生產現場，需要在現場完成一些必需的任務。在一個工作站上處理一個任務，一個任務對應一個工作站。在生產現場有多個工作站，每個工作站可由多個資源組成，下文將使用停靠站（dock）來表示這些資源。在某些工作站的前面，有可供卡車等待的緩衝區 。某些緩衝區僅專用於一個站，而共享緩衝區可用於多個站。在某些沒有緩衝區的工作站上，提供了無限的等待空間。

在這種情況下，這個生產現場有意最佳化卡車的執行。這項研究的目的是為每輛卡車找到一條最佳路徑，以便在卡車到達現場後快速完成所有任務。該卡車排程問題被建模為柔性作業車間排程問題（flexible job shop scheduling： FJSS），其目的是最大程度地減少完工時間（makespan）。作業車間排程問題（job shop scheduling： JSS）是計算機科學和運籌學中的一個最佳化問題，方案是將作業在特定時間分配給資源。柔性作業車間排程問題是作業車間排程的擴充套件。在作業車間環境中，每個作業在所有機器上都有預定的處理順序，因為每個機器只能執行某個操作。而在柔性作業車間環境中，則有一組有能力的機器可以執行這個操作。在上述環境中，整個生產現場可以看作是一個車間（Job Shop）。卡車需要的各項操作可以看作是任務（Job）。工作站上的多個資源被認為是可以在工作站處理所需任務的一組有能力的機器。這樣一來，卡車排程就可以看作卡車經過預定工作站完成任務次序的規劃，目的是減少整體的完工時間。

2。數學模型

2.1 實際問題簡化

問題中的要素是：大門，由停靠站（dock）和緩衝區 （buffer）組成的工作站（station）。所有元素的簡化圖舉例如下圖。該現場上有四個工作站。在每個站，都有兩個緩衝區和兩個停靠站（dock）。所有這些元素均按順序命名和編號。緩衝區和停靠站（dock）聚集在工作站上。例如，緩衝區1、2和停靠站1、2屬於工作站1。它們只能用於在工作站1處理的卡車。進來的卡車需要被分配到相應的工作站，以完成所有必要的操作（operations）。這種排程問題的實質是為卡車分配在每個工作站的時間間隔，以完成相應的任務。由於每個工作站有多個停靠站（dock），因此還需要分配停靠站（dock）。可能會有這樣的情況，當卡車到達車站時，所有停靠站都被佔用，因此，卡車必須等待在屬於該工作站的緩衝區。

2.2 假設條件

1。卡車在大門口登記的時間可以忽略，它可以在大門外面等待。大門外有無限的等候空間。

2。每輛卡車訪問工作站的順序是預先確定的。

3。在每一個工作站上有兩個過程。首先是在緩衝區上等待，其次是在停靠站上進行操作。這並不意味著卡車必須在每個工作站等待。如果沒有等待，緩衝區上的處理時間將為0。停靠站上的處理時間為實數。

4。每個工作站的停靠站和緩衝區數量是確定的。每個工作站的停靠站都是一樣的，即，卡車的處理時間不依賴於停靠站。

5。在處理過程中，每個操作都不能中斷，即不允許進行任何搶佔。

6。假設所有引數：到達時間，處理時間等都是確定的，

7。停靠站之間，停靠站和緩衝區以及工作站和大門之間的行駛時間可以忽略。

2.3 索引，引數和變數

2.4 目標函式

2.5 約束條件

3。算例分析

以本文2。1中的場景為例，我們可以使用一些模擬資料利用以上模型，在 GAMS（General Algebraic Modeling System）軟體中進行編碼，並用CPLEX求解器求解得到一個卡車排程方案。在這個場景裡有4個工作站，每個工作站上有兩個停靠站和緩衝區，即 m=16。如下表所示，有8輛卡車需要排程，即n=8。表格第二列給出了它們到達生產現場的時間。由於卡車的操作與工作站相關，所以可以用工作站的順序來表示各項操作的順序。比如，卡車i1的整個流程包含8項操作。第一個操作（j=1）和第二個操作（j=2）是在工作站1（s1）上進行的。第一個操作是在s1上等待，緩衝區1和緩衝區2都有能力執行，但這並不代表卡車i1必須在緩衝區等待。因為對於任何一輛卡車，在緩衝區的操作時間引數都被設定為0。只有在變數等待時間不為0的情況下，卡車需要在緩衝區等待。第二個操作是在s1上進行處理，停靠站1和停靠站2都有能力執行。第二個操作是由停靠站1或停靠站2執行取決於解出的變數Vijk的值。卡車的第三和第四個操作是在s2上進行的。緩衝區3和4有能力執行第三個操作，停靠站3和4有能力執行第四個操作。依此類推，剩下的操作依次在s3和s4上完成。

輸入以上引數，GAMS 給出的一個最優解如下面的甘氏圖所示。

整個過程的最小完工時間是 36 個時間單位，相比下面的在先進先出原則下的規劃可以節約 7 個時間單位，效率提高 16%。

4 模型擴充套件：魯棒模型

在此卡車排程問題中，某些引數可能不受控制。例如，卡車的到達時間和處理時間。由於交通條件的不同，卡車可能比預期的到達時間更早或更晚。處理時間可能會受到機器狀況（例如機器停機時間，維護等）的影響。這些不確定性會干擾卡車的時間表。在現實中，隨機到達時間一直是困擾該生產現場卡車管理的最具破壞性的因素。我們以隨機到達時間為例，放鬆假設條件 6，擴充套件文章第二部門的模型，引入情景（scenarios）索引可以將問題的隨機性考慮到魯棒模型中。此處的情景即多組卡車的到達時間，每組情景包含了所有卡車的到達時間。

約束條件（19）是為了計算新的目標函式。其他約束條件（1）-（18）需要根據上面變數的改動加以修改引入情景索引。

參考文獻

［1］Zhang， G。， X。 Shao， P。 Li， and L。 Gao （2009）。 An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem。 Computers & Industrial Engineering 56（4）， 1309–1318。