带模具约束的两台同型机排序问题的改进算法

甄 谭，张 安，陈光亭，陈 永

(1.杭州电子科技大学理学院，浙江 杭州 310018；2.台州学院电子与信息工程学院，浙江 台州 318000)

0 引 言

1 问题描述

2 算法设计与分析

对P2|mi|Cmax问题，文献[5]给出了基于工件集加工时间不增顺序规则(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里的工件不发生模具冲突。令决定MTLPT算法最大完工时间的工件的加工时间为px，易知px≤p(S1)，MTLPT算法所得排序如图2所示。图2中，a表示px所对应工件的开工时间，b表示机器M1的完工时间。

图2 不发生模具冲突时，MTLPT算法所得排序

(2)M1，M2上属于S1里的工件发生模具冲突。算法解由M1决定时，MTLPT算法所得排序如图3所示，算法解由M2决定时，MTLPT算法所得排序如图4所示。

图3 发生模具冲突且算法解由M1决定时，MTLPT算法所得排序

图4 发生模具冲突且算法解由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，最优排序如图6所示。

图6 紧例的最优排序

4 结束语