带有平行机成组加工中的延迟和延误工件数问题

同类机成组加工中的延迟和延误工件数问题何龙敏 孙世杰 罗润梓（上海大学数学系，上海200436）摘要 本文考虑带同类机（Qm ）的成组排序问题，分别取目标函数：L max ，j U ∑。

文中将此类成组排序的某些算法转化为相应经典排序问题，并揭示了它们的某种联系。

关键词 排序,成组, 同类机，弱（逆）一致性，L max ，j U ∑。

§1 引言传统排序问题往往考虑逐个工件的排序，柔性制造系统中的现代技术引出了一些新的排序问题——成组（批）加工，记为：·|BI,B |·，其中：BI 指同组（批）工件必须在一起同时加工（Group Technology Assumption ）；B 指每批工件最大容量。

半导体元件生产中的这类排序问题由Lee et al.(1992) [5，6] 首先引进，但Ikrura 和Gincple （1986）[3]或许是第一个研究这类问题的学者。

文献[4]证明了Pm │BI ,B │g, g ∈{C max,L max }为强NP-hard 的（由此Qm |BI,B |g ，g ∈{C max,L max }也为强NP-hard ），并利用解P ‖C max 的近似算法求解该二个问题，估计了相应误差。

Chandru et al （1993）[1]对Pm |BI,B |C max 给出了分枝定界算法和近似算法。

但以往研究的机器类型以同型机较为多见。

文献[9]将此类机器推广至同类机中的最大完工时间（C max ）以及用它研究最大迟后（L max ）问题的上界。

本文以此为基础，在新的假设条件下，将原目标函数推广至最大迟后（L max ）和延误工件数（j U ∑）这两个排序问题。

主要讨论在同型机环境下的分组（批）排序与经典排序这两类问题之间的最优解及性能比的联系（据此，可将一些经典排序的有效算法用以解决某些分组（批）排序问题）。

最后，对文中建立的联系展开了一些定性分析和推广，拟提出可以进一步讨论的内容。

本文考虑的问题为n 个工件N=（J 1，J 2，…，J n ）需要在m 台同类机上加工，工件J j 在单位速度机器上所需加工时间为p j ，工件J j 的应交工时间为d j ，其中j =1，…，n ；工件可被分成若干组（批）B i ，任机器上的任组（批）B i 允许所含工件数至多为B 个，即|B i |≤B ，同批工件同时加工；第i 批工件所需加工时间为该批工件中所有p j 中最长者，可记为T i ；机器i 的加工速度为v i ≥1（i =1，…，m ）；一组工件只能在其中一台机器上加工一次，且中间不能中断加工，因而同组工件的完工时间相同。

要求适当分组（批）并安排这n 个工件，使最大迟后（L max ）或总延误工件数(j U ∑)达最小。

用三参数表示法[2]，以上两类问题分别记作Qm |BI,B | L max 和Qm |BI,B |j ΣU 。

文中定义⑪若(),p p ,n ,1,k j,k j k j ≥=≠∀ ⇒ k j d d ≥，则称工件间满足弱一致性； ⑫若(),p p ,n ,1,k j,k j k j ≤=≠∀ ⇒ k j d d ≥，则称工件间满足弱逆一致性。

§2 成组加工中的延迟问题（Lateness ）1、算法算法1（GLS 算法）Step1 将工件、机器分别按工件加工时间、机器加工速度非增序重新编号，即n 21p p p ≥≥≥ 与m 21v v v ≥≥≥ 。

Step2 按工件非增序及最大批容量进行分批：()()sB n 1B 1s B 21B B 1J J ,,J ;;J ,,J ;J ,,J ≤+-+ ，S=⎥⎥⎤⎢⎢⎡B n 。

这样，除了末批可能未满，前面的批都是满批（据定义有：s 21T T T ≥≥≥ ）。

Step3 一批为一个复合工件b ，并相应编号成s 21b ,,b ,b ，再用LS(list scheduling)算法[7，8]排序（即：将已编号的各批工件排于可最先完工的机器上加工，若同时有多于二个这样的机器，则将工件排在依编号从小到大的机器序上加工。

由于n 21p p p ≥≥≥ ，这里的LS 序实际上已为LPT 序）。

由于Step1的计算量为O(nlogn)；Step2的计算量为O(n)； Step3为LS 规则，计算量至多为O(n)。

所以，整个算法计算量为O(nlogn)。

如果工件按GLS 算法编号、分批，将每批视作一个复合工件（b i ），考虑到n 21p p p ≥≥≥ 及弱(逆)一致性，易知该复合工件b i 的加工时间为：i b T =(()B 1i 1p -+)；复合工件b i 的应交工时间为：①（逆一致时）i b d =()B 1i 1d -+ 、②（一致时）i b d =()B 1i B d -+。

其中,,2,1i =⎥⎥⎤⎢⎢⎡B n 。

这样，Qm |BI,B | L max 问题就转换为如此构造的⎥⎥⎤⎢⎢⎡B n 个复合工件的Qm ‖L max 问题（属于经典排序问题）。

记该问题为Qm |I B ~,B | L max （相应算法为LS ）。

这样定义的复合工件组成的Qm ‖L max （即Qm |I B ~,B | L max ）与原Qm |BI,B | L max 问题存在某种联系，即下面的定理1。

上述LS 算法视情况也可改为其它一些算法。

以下均假设工件加工时间与机器加工速度为非增序，即 n 21p p p ≥≥≥ 与m 21v v v ≥≥≥ 。

2、性质引理1 在弱（逆）一致性条件下，Qm |BI,B | L max 问题一定存在这样的优势分批序：每批中的工件从小到大连续编号。

证：不妨设最优序π1中有这样的工件组，在其中的工件不是依从小到大连续编号分批，即存在工件P J '、j 1j J J 、-、1j J +和P J ''满足P p p p P 1j j 1j ''≥≥≥≥'+-。

但P J '、1j J - 和1j J +∈i B ⊂1M ，j J 和P J ''∈t B ⊂2M ，且i B 批在t B 批的前面加工。

其中除工件j 1j J J 、-和1j J +外，i B 批中其余工件记作P J '，加工时间取P J '中最大的一个（记为P '），各自交工时间不变（记为P d '），相应目标值为（P '-P d '）；t B 批中其余工件记作P J ''，加工时间取P J ''中最大的一个（记为P ''），各自交工时间不变（记为P d ''），相应目标值为（P ''-P d ''）。

由于P p p p P 1j j 1j ''≥≥≥≥'+-和弱一致性，有P 1j j 1j P d d d d d ''+-'≥≥≥≥。

如果将1j J +与j J 对调，其它各工件不动。

由此，i B 变为i B '，t B 变为t B '（参考图1）。

现分析工件调换前后其目标函数L max 的大小。

由于为同类机，其余工件未变，只要考虑这五个工件所在批的变化引起L max 的变化情况。

记五个工件P J '、j 1j J J 、-、1j J +和P J ''调换前后构成的相应目标值为L max （t i B B 、）和)B ,B (L t i m ax ''。

设L max （t i B B 、）=max{①,②,③,④,⑤}={}P t 1j i ,j t 1j i p i d T ,d T d T ,d T ,d T max ''+-'-----和)B ,B (L t i m ax ''=max{⑥,⑦,⑧,⑨,⑩}{}P t 1j t ,j i 1j i p i d T ,d T d T ,d T ,d T max ''+-'-'-'-'-'-'。

i B i B '1M 1j 1j P J ,J ,J +-' 1M ' j 1j P J ,J ,J -'i T i T '()调换后Jj ,1Jj +⇒==========t B t B '2M P j J ,J '' 2M ' P 1j J ,J ''+t Tt T '图1 其中：i T 和i T '为工件1j J +和j J 调换前后，批i i B B '、在机器M 上的批加工时间，有i T =t T '（∵1j j 1j p p p P +-≥≥≥'）；t T 为批t B 中（含工件j J ）在机器M '上的批加工时间； t T '为批t B '中（含工件1j J +）在机器M '上的批加工时间，有t T ≥t T '（1j j p p +≥ ）。

∵由弱一致性条件：①≤②≤④,③≤⑤; ⑥≤⑦≤⑧,⑨≤⑩; ④≥⑧。

又∵⑤≥⑩（1j j p p +≥ ）。

∴L max （t i B B 、）≥)B ,B (L t i m ax ''。

若存在工件j 1j J J 、-、1j J +、P J '和P J ''满足P P p p p 1j j 1j ''≥'≥≥≥+-，但1j J -、1j J +、P J '∈i B ⊂1M ，j J 和P J ''∈t B ⊂2M ，且i B 批在t B 批前加工；或存在工件P J '、j 1j J J 、-、1j J +、P J ''和P J '''满足P P p p p P 1j j 1j '''≥''≥≥≥≥'+-，但P J '、1j J -、1j J +、P J ''∈i B ⊂1M ，j J 和P J '''∈t B ⊂2M ，且i B 批在t B 批前加工。

其中：P J '、P J ''、P J '''、P '、P ''和P '''的定义仿前。