非同步混裝線負荷平衡與投產排序集成優化方法

張家驊，李愛平，劉雪梅

（1.無錫工藝職業技術學院機 電與信息工程學院，宜興 2 142061；2.同濟大學 機械與能源工程學院，上海 201804）

0 引言

混流裝配線由于能在同一條裝配線上混合連續地裝配結構相似、工藝相近的不同品種的產品，能有效幫助企業應對激烈的市場競爭和和多樣的客戶需求，在企業中得到廣泛使用。混流裝配線負荷平衡和投產排序，是為保證混流裝配線的有效運行，重點需要解決的兩個問題。在大部分研究中，混裝線平衡和排序都是單獨研究，而且主要研究對象是以輸送帶作為物料運輸裝置的同步混流裝配線[1,2]。非同步混流裝配線，是工作站間具有有限容量緩沖區的混流裝配線；由于其擴展靈活、維修方便等特點，在汽車行業中得到使用[3]。

針對非同步混流裝配線，王炳剛[4]以最小化最大完工時間和平滑物料利用率作為目標，采用智能算法，單獨研究了排序問題。Battini[5]以最小化工作站數目和平滑工作站負荷波動為平衡與排序的目標，研究了非同步混裝線平衡和排序的集成優化方法，但采用的求解方法是分支定界算法。由于混裝線平衡與排序都是NP-hard問題[6]，分支定界這類精確求解算法當面對實際大規模問題時，無法求解，并不適合企業實際需求[7]。

針對以上問題，本文提出了一種基于啟發式算法的非同步混裝線負荷平衡與產品排序的啟發式方法。分別以與生產效率密切相關的生產節拍和最大完工時間作為平衡與排序的優化目標；平衡階段，通過設計組合優先啟發式方法，找出生產節拍最小的可行解；在排序階段，在緩沖區容量約束下，考慮裝配線的堵塞，采用NEH（Nawaz-Enscore-Ham）算法，找出產品最大完工時間最小的投產排序方案；最終實現提高裝配線生產效率的目的。

1 問題描述和優化方法概述

圖1是發動機非同步混裝線的示意圖，在工作站間，摩擦輥輪積放式輸送帶起到了緩沖區的作用。工作站內的操作任務由裝配線平衡方法確定；投放到裝配線上的產品按照先進先出組成一個排隊隊列；產品投放順序由排序方法決定。

1.1 問題描述

非同步混裝線由多個工作站和線上緩沖區組成；裝配線上的工作站數目和緩沖區容量提前已知。線上有P種相似產品混合裝配。在一個生產計劃期內，對第p（p=1，2，…，P）種產品的需求量為Dp，則對P種產品的總需求量為。生產采用最小生產循環（Minimal Production Set，MPS）策略。MPS是代表產品比例的矢量，可表示為：（d1，…，dp）=（D1/h，…，Dp/h）。其中h表示各種產品需求量Dp（p=1，2，…，P）的最大公約數。MPS中產品的數量。當p種產品按照一定順序，以最小生產循環投入裝配線時，循環次數h遍后，即可完成總生產量。本問題的目標是合理分配工作站內的操作和產品的投產順序，實現裝配線的最大生產效率。

圖1 發動機非同步混裝線示意圖

1.2 集成平衡與排序方法概述

由于混裝線平衡與排序之間的內在聯系，單獨進行研究割裂了兩者之間的關系。本文提出了一個平衡與排序的集成方法，通過逐步求解的過程，確定非同步混裝線的裝配操作與產品投產順序的決策問題，最終實現裝配線的高效運行。圖2是該方法的具體流程圖。

裝配線平衡階段，提出一個組合優先啟發式方法，對問題進行求解。在排序階段，利用NEH算法[8]，通過考慮緩沖區容量的最大完工時間的影響，確定產品的投產順序。

2 非同步混裝線平衡求解方法

非同步混流裝配配線平衡問題的目標是在給定工作站數量下，將所有品種的裝配操作分配到工作站內，達到最小化生產節拍。操作的分配應考慮操作之間的優先關系。

首先通過綜合優先關系圖將多品種混流裝配線平衡問題轉變為單品種裝配線平衡問題，當獲得綜合優先關系圖之后，可以利用優化方法求解裝配線平衡問題。

啟發式方法被認為是用來求解裝配線平衡問題的有效方法之一。至今的研究已經有很多針對裝配線平衡的啟發式方法，如最大候選值方法，位置加權法，最大緊鄰后序任務數目等。

圖2 負荷平衡和投產排序方法流程圖

由于每種啟發式規則都有自身的不足，因此本文提出一種組合式啟發式規則，該規則表示如下：

其中，Ri是操作i的位置加權值，ISi是操作i的最大緊鄰操作數目，CS是可分配操作的集合。在可分配操作集合中，具有最大值θ的操作可以被分配至工作站內。

根據綜合優先關系圖，確定可分配的操作集合CS；選擇CS中具有最大θ值的操作分配至工作站內。

3 非同步混裝線排序方法

流水裝配線是一種置換流水線，因此非同步混裝線可以被簡化為帶緩沖區約束的置換流水線。產品最大完工時間（Makespan）是制造系統生產率的一個重要評價指標。目前已有多種針對置換流水車間，最小化最大完工時間的啟發式算法。其中NEH（Nawaz-Enscore-Ham）被認為是解決該問題最有效的算法，將該方法應用到非同步混流裝配線排序中，算法具體過程描述如下：

步驟1：對MPS中每個產品j，計算其總裝配時間：

其中，tj,m是產品j在工作站m上的裝配時間。

步驟2：對MPS內的所有產品按照裝配時間按遞減順序排列S。

步驟3：從步驟2）所得序列S中選出第一和第二個產品，分別按不同的順序計算出最小的最大完工時間位置。將該產品的位置順序在后面步驟中都固定下來，令q=3。其中，帶緩沖區容量限制的最大完工時間采用文獻[9]計算。

步驟4：從S序列中選出第q個產品，將它放到上一步驟中的產品的序列中任一位置而不改變原來產品的相對位置，找出最小的最大完工時間的產品排列順序。

步驟5：如果q=I，程序停止；否則q=q+1轉上一步驟繼續執行。

4 實例驗證

某發動機裝配車間在一條非同步混流裝配線上混流生產三款發動機缸蓋，分別使用在排量為1.0T的3缸和排量1.4T、1.5T的4缸發動機上；三個品種用1、2、3表示。采用MPS策略生產，在一個MPS生產周期中，d1：d2：d3=1：2：2。裝配線由缸蓋上線工作站、拆卸凸輪軸蓋工作站等共11個工作站組成，其中各個工作站之間各有2個產品的線上緩沖區，具體工藝文件和操作時間可詳見[10]。

圖3是三種缸蓋的裝配操作的綜合優先關系圖。

圖3 三種缸蓋的綜合優先關系圖

圖4和圖5是企業原方案和新方案的工作站負荷分布圖。表1內是企業原工作站分配方案和使用平衡方法后的分配方案。采用本文所提方法后，裝配線的節拍時間從75s降為66s。

圖4 企業原工作站負荷

其中，M是工作站數目，T是瓶頸工作站的時間，ti是綜合優先圖中的加權時間。通過計算，原方案的平衡率為81.6%，新方案的平衡率為92.4%。采用新的線平衡方法，可以改善裝配線的平衡效果。

圖5 優化后工作站負荷

通過產品排序，可以進一步改善由于不同品種產品產品時間波動對生產性能影響。企業原啟發式方法得到的排序方案是（3-2-2-3-1），圖6是采用企業原平衡方案和排序方案的甘特圖。采用本文所提的排序方法的排序方案是（1-2-2-3-3），圖7采用本文所提負荷平衡和排序方法之后的現在的產品最大完工時間。從結果中可以發現，采用本文的集成方法后，產品的最大完工時間為951s，比原方案991s節約了40s，表明裝配線生產效率得到了提高。

表1 不同方法的操作分配方案

圖6 原平衡方案原排序方法的甘特圖

圖7 新平衡方案新排序方法的甘特圖

5 結語

本文提出了一種適用于非同步混流裝配線的負荷平衡與產品排序集成優化方法；其中組合優先啟發式方法和NEH算法被用到了求解方法中。將本文所提出的方法應用到實際發動機缸體的非同步混流裝配生產中，改善了生產線的平衡率，縮短了產品的生產時間，最終提高了產品的生產效率。