Performance Analysis of a Lower Bound for Flow Shop Weighted Completion Time Problem

摘要：

This paper considers the M-machine Flow Shop problem with the objective ofminimizing Weighted Completion Time. We show that a Lower Bound (LB) which is given by Kaminsky and Simchi-Levi 5 is asymptotically equivalent to the optimal solution, and its tight worst case performance ratio is m. Based on the LB a worst case performance ratio of WSPT heuristic, m, is obtained.

关键词： Worst case analysis asymptotic analysis Flow shop weighted completion time problem WSPT heuristic.

作者: Danyu Bai Lixin Tang

作者单位: The Logistics Institute Northeastern University Shenyang, P. R. China

会议类型: 国际会议

会议名称: 2007 Conference on Systems Science, Management Science and System Dynamics(第二届系统科学、管理科学与系统动力学国际会议)

会议地点: 上海

会议语种:英文

页码: 45-50

在线出版日期: 2007-10-19（万方平台首次上网日期，不代表论文的发表时间）