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

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

0 引 言

1 問題描述

2 算法設計與分析

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

3 算法緊例

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

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

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

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

4 結束語