摘要
研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的。给出一种新的启发式算法,并证明该算法的最坏性能比是(m+1)/2,且上界是紧的。
Considering m-machine flow-shop problem with delays and release times, we use 3-Partition to prove that the F2RD problem is NP-hard in the strong sense, and then we introduce a simple heuristic and prove that the worst-case performance is (m+1)/2. At last, we give an example to show the bound is tight. Specially, when m =2, the worst-case performance is 3/2, the bound is tight, too.
出处
《西南民族大学学报（自然科学版）》
CAS
2003年第3期258-263,共6页
Journal of Southwest Minzu University(Natural Science Edition)
基金
Supported by the Educational Department of Hubei Province No.2002x13.
