非同步混裝線負荷平衡與投產(chǎn)排序集成優(yōu)化方法

張家驊，李愛平，劉雪梅

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

0 引言

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

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

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

1 問題描述和優(yōu)化方法概述

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

1.1 問題描述

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

圖1 發(fā)動機非同步混裝線示意圖

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

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

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

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

非同步混流裝配配線平衡問題的目標是在給定工作站數(shù)量下，將所有品種的裝配操作分配到工作站內(nèi)，達到最小化生產(chǎn)節(jié)拍。操作的分配應考慮操作之間的優(yōu)先關系。

首先通過綜合優(yōu)先關系圖將多品種混流裝配線平衡問題轉變?yōu)閱纹贩N裝配線平衡問題，當獲得綜合優(yōu)先關系圖之后，可以利用優(yōu)化方法求解裝配線平衡問題。

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

圖2 負荷平衡和投產(chǎn)排序方法流程圖

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

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

根據(jù)綜合優(yōu)先關系圖，確定可分配的操作集合CS；選擇CS中具有最大θ值的操作分配至工作站內(nèi)。

3 非同步混裝線排序方法

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

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

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

步驟2：對MPS內(nèi)的所有產(chǎn)品按照裝配時間按遞減順序排列S。

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

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

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

4 實例驗證

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

圖3是三種缸蓋的裝配操作的綜合優(yōu)先關系圖。

圖3 三種缸蓋的綜合優(yōu)先關系圖

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

圖4 企業(yè)原工作站負荷

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

圖5 優(yōu)化后工作站負荷

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

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

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

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

5 結語

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