張家驊，李愛(ài)平，劉雪梅

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

0 引言

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

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

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

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

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

1.1 問(wèn)題描述

非同步混裝線由多個(gè)工作站和線上緩沖區(qū)組成；裝配線上的工作站數(shù)目和緩沖區(qū)容量提前已知。線上有P種相似產(chǎn)品混合裝配。在一個(gè)生產(chǎn)計(jì)劃期內(nèi)，對(duì)第p（p=1，2，…，P）種產(chǎn)品的需求量為Dp，則對(duì)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ù)量。當(dāng)p種產(chǎn)品按照一定順序，以最小生產(chǎn)循環(huán)投入裝配線時(shí)，循環(huán)次數(shù)h遍后，即可完成總生產(chǎn)量。本問(wèn)題的目標(biāo)是合理分配工作站內(nèi)的操作和產(chǎn)品的投產(chǎn)順序，實(shí)現(xiàn)裝配線的最大生產(chǎn)效率。

圖1 發(fā)動(dòng)機(jī)非同步混裝線示意圖

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

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

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

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

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

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

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

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

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

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

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

3 非同步混裝線排序方法

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

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

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

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

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

步驟4：從S序列中選出第q個(gè)產(chǎn)品，將它放到上一步驟中的產(chǎn)品的序列中任一位置而不改變?cè)瓉?lái)產(chǎn)品的相對(duì)位置，找出最小的最大完工時(shí)間的產(chǎn)品排列順序。

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

4 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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