摘要
考虑有独立调整时间的同型号平行机排序问题，极小化最迟完工时间．产品允许拆分，同一产品被拆分后各部分可以在不同机器上同时加工．该问题是 Ｎ Ｐｈａｒｄ 问题．本文首先给出该问题的一个启发式算法 Ｍ Ｌ，然后证明了其最坏情况估计不超过７／４－ １／ｍ （ｍ ≥２）
An identical parallel machine scheduling problem is considered in this paper. In the problem, a product can be split, the split parts can be processed with setup times on two different machines at the same time. The paper presents a heuristic ML for the problem and proves that its worst case ratio is within 7/4-1/ m(m≥2).
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1999年第4期480-484,共5页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
国家自然科学基金
