帶模具約束的兩臺(tái)同型機(jī)排序問題的改進(jìn)算法

甄 譚，張 安，陳光亭，陳 永

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺(tái)州學(xué)院電子與信息工程學(xué)院，浙江 臺(tái)州 318000)

0 引 言

1 問題描述

2 算法設(shè)計(jì)與分析

對P2|mi|Cmax問題，文獻(xiàn)[5]給出了基于工件集加工時(shí)間不增順序規(guī)則(Longest Processing Time first，LPT)[6]的近似算法，簡稱TLPT算法。TLPT算法主要步驟如下。

(1)將工件集按照處理時(shí)間非增順序排列，即p(S1)≥p(S2)≥……≥p(Sq)。

(2)將工件集S2,S3,……,Sq按照上述順序安排在使其最早開工的機(jī)器上加工。

(3)假設(shè)不考慮模具約束，將工件集S1里的工件按照LPT算法安排在使其最早開工的機(jī)器上加工，令M1為完工時(shí)間較大的那臺(tái)機(jī)器。

(4)從M1的零時(shí)刻開始插入M1上屬于S1的工件。

圖1 TLPT算法步驟3和步驟4得到的排序

(1)將工件集按照處理時(shí)間非增順序排列，即p(S1)≥p(S2)≥……≥p(Sq)。

證明運(yùn)用MTLPT算法得到的排序中，最大完工時(shí)間有以下2種情況。

證畢。

(1)M1，M2上屬于S1里的工件不發(fā)生模具沖突。令決定MTLPT算法最大完工時(shí)間的工件的加工時(shí)間為px，易知px≤p(S1)，MTLPT算法所得排序如圖2所示。圖2中，a表示px所對應(yīng)工件的開工時(shí)間，b表示機(jī)器M1的完工時(shí)間。

圖2 不發(fā)生模具沖突時(shí)，MTLPT算法所得排序

(2)M1，M2上屬于S1里的工件發(fā)生模具沖突。算法解由M1決定時(shí)，MTLPT算法所得排序如圖3所示，算法解由M2決定時(shí)，MTLPT算法所得排序如圖4所示。

圖3 發(fā)生模具沖突且算法解由M1決定時(shí)，MTLPT算法所得排序

圖4 發(fā)生模具沖突且算法解由M2決定時(shí)，MTLPT算法所得排序

3 算法緊例

圖5 緊例通過MTLPT算法所得排序

機(jī)器M1和M2分別加工3個(gè)工件集S1,S2,S3，其中S1中有2個(gè)工件，加工時(shí)間p1=p2=1；S2中有2個(gè)工件，加工時(shí)間p3=p4=1；S3中有1個(gè)工件，加工時(shí)間p5=2。通過MTLPT算法得到排序如圖5所示。

從圖5可以看出，MTLPT算法所得到的排序的最大完工時(shí)間為4，最優(yōu)排序如圖6所示。

圖6 緊例的最優(yōu)排序

4 結(jié)束語