黨少杰，張迪

(合肥工業(yè)大學(xué)機(jī)械工程學(xué)院，安徽 合肥 230009)

基于LINGO的多智能配送單元任務(wù)分配策略研究

黨少杰，張迪

(合肥工業(yè)大學(xué)機(jī)械工程學(xué)院，安徽 合肥 230009)

為了解決作業(yè)車間任務(wù)分配缺乏合理規(guī)劃等問題，本文以路徑最短為目標(biāo)建立了任務(wù)分配模型，然后利用LINGO軟件對(duì)模型進(jìn)行求解。實(shí)例結(jié)果表明，利用LINGO軟件可以快速、準(zhǔn)確的給出分配方案，從而為解決任務(wù)分配問題提供了一個(gè)有效的解決辦法。

任務(wù)分配；整數(shù)規(guī)劃；LINGO

1 問題提出

隨著制造業(yè)市場的競爭越來越激烈，企業(yè)都在考慮如何提高生產(chǎn)效率，降低成本。而任務(wù)分配是企業(yè)以前很少關(guān)注的一個(gè)問題，并且該環(huán)節(jié)處理的好壞將直接影響智能配送單元對(duì)物料需求的響應(yīng)速度以及物料的配送成本。一個(gè)合理的任務(wù)分配方案可以減少運(yùn)送次數(shù)以及運(yùn)送成本，這些指標(biāo)對(duì)于企業(yè)提高生產(chǎn)效率節(jié)約成本起著重要作用。所以對(duì)作業(yè)車間智能配送單元的任務(wù)分配策略的研究有著非常重要的理論價(jià)值和實(shí)際意義。

對(duì)于作業(yè)車間配送單元的任務(wù)分配策略問題，目前已經(jīng)有不少的文章進(jìn)行了研究。傳統(tǒng)的平衡指派問題（AP，Assignment Problem）采用匈牙利算法進(jìn)行求解，在匈牙利算法的基礎(chǔ)上，提出了一種任務(wù)指派問題的快速求解方法-剪枝優(yōu)化算法，該算法大大提高了求解任務(wù)指派問題的求解速度。文獻(xiàn)提出一類帶時(shí)間約束的指派問題，即每臺(tái)機(jī)器有執(zhí)行任務(wù)的時(shí)間窗限制，并給出分枝定界算法。文獻(xiàn)采用lingo軟件求解了鋼鐵企業(yè)產(chǎn)成品轉(zhuǎn)庫運(yùn)作中的混合車輛指派及路徑優(yōu)化問題。目前對(duì)基于時(shí)間窗和容量雙約束的研究不足，本文的模型基于時(shí)間窗和容量雙約束建立。

隨著計(jì)算機(jī)技術(shù)的大戰(zhàn)，已經(jīng)有十分強(qiáng)大的軟件用于解決運(yùn)籌學(xué)問題，其中對(duì)規(guī)劃問題的求解最好的軟件就是LINGO軟件，目前LINGO軟件已經(jīng)升級(jí)到12.0版本，本文就是通過LINGO軟件來對(duì)模型求解，實(shí)例結(jié)果表明其可以迅速給出一套經(jīng)濟(jì)、可行的任務(wù)分配方案。

2 模型建立

作業(yè)車間任務(wù)分配策略是合理規(guī)劃、指派智能配送單元以便于將物料可以及時(shí)、準(zhǔn)確地運(yùn)送到需求工位，由于作業(yè)車間多智能配送單元的任務(wù)分配策略問題比較復(fù)雜，因此在建模的過程中必須考慮智能配送單元任務(wù)分配原則、物料需求情況、配送單元的最大容量、作業(yè)車間的布局等因素，如果智能配送單元物料配送策略不合理，可能使物料配送時(shí)間過長，導(dǎo)致生產(chǎn)成本增加，鑒于作業(yè)車間中物料配送多智能配送單元任務(wù)分配策略研究的復(fù)雜性，故作如下假設(shè)：（1）生產(chǎn)節(jié)拍、作業(yè)車間布局、智能配送單元數(shù)量和容載量已知。（2）所有需求工位只需配送一次，一個(gè)智能配送單元一次最多只能去一個(gè)工位。（3）假定所有智能配送單元同一型號(hào)（容載量、速度等）。（4）智能配送單元的容載量要大于需求工位的需求量。

建立的數(shù)學(xué)模型如下：

其中式（1）為目標(biāo)函數(shù)；式（3）代表每個(gè)需求工位只能由一個(gè)智能配送單元的某個(gè)任務(wù)去配送；式（4）代表某個(gè)智能配送的指定任務(wù)最多只能去一個(gè)需求工位；式（5）表示智能配送單元完成所有的物料配送任務(wù)；式（6）是時(shí)間窗約束；式（7）是容量約束；式（8）示每臺(tái)智能配送單元任務(wù)的總數(shù)小于總的物料配送任務(wù)。

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

某工廠6個(gè)小車，8個(gè)需求工位距離二位表和工位時(shí)間表如圖1所示。

表1 小車—工位距離表

表2 小車—工位時(shí)間表

下面是針對(duì)模型寫的編寫的lingo程序。

model:

sets:

car/car1..car6/: limit_assitant,capacity;

number/number1..number3/:num;

station/station1..station8/: request,time_start,time_ end;

links(car,number,station):distance, time_between, vo;

endsets

!目標(biāo)函數(shù);

min=@sum(links : distance*time_between* vo);

!一個(gè)車一次最多只能去1個(gè)工位(一次可以去多個(gè)工位);

@for(car(I):

@for(number(J):

@sum(station(K): vo(I,J,K))<=1));

!一個(gè)工位只能由一個(gè)車去響應(yīng);

@for(station(K):

@sum(number(J):

@sum(car(I): vo(I,J,K)))=1);

!容量約束加變量;

@for(car(I):

@for(number(J):

@sum(station(K):vo(I,J,K)*request(K))<= capacity(I)));

!任務(wù)數(shù)約束;

@for(car(I):

@sum(number(J):

sum(station(K):vo(I,J,K)))<= imit_assitant(I));

!整數(shù)約束;

@for(links: @bin(vo));

!總和約束;

@sum(car(I):

@sum(number(J):

@sum(station(K):vo(I,J,K))))=8;

!時(shí)間窗約束;

@for(station(K):

@for(number(J):

@sum(car(I):time_between(I,J,K)*vo(I,J,K)) <=time_end(K)-time_start(K)));

在LINGO12.0上運(yùn)行程序返回如下結(jié)果（圖1～2）

圖1 LINGO求解狀態(tài)

圖2 LINGO求解結(jié)果

因此，任務(wù)分配方案是：1號(hào)車配送工位5和2；2號(hào)車配送工位7；3號(hào)車配送工位3；4號(hào)車配送工位8；5號(hào)車配送工位1；6號(hào)車配送工位6；6號(hào)車配送工位4。

4 結(jié)語

本文對(duì)作業(yè)車間的任務(wù)分配問題進(jìn)行分析，建立了數(shù)學(xué)模型，并且采用LINGO軟件進(jìn)行了求解。實(shí)驗(yàn)證明采用LINGO軟件可以高效、便捷地求解此類問提。當(dāng)然一些啟發(fā)式算法、智能算法也可以求解此問題，值得另行研究。

[1]鄒莉. 多目標(biāo)電梯群控系統(tǒng)的研究[J]. 自動(dòng)化與儀器儀表, 2010(3):14-16.

[2]馬云紅, 井哲, 周德云. 一種任務(wù)分配問題的快速剪枝優(yōu)化算法[J]. 西北工業(yè)大學(xué)學(xué)報(bào), 2013, 31(1):40-43.

TH165

A

1671-0711（2017）07（上）-0206-03