A New Lower Bound for Flow Shop Makespan with Release Dates

摘要：

In the paper,we consider the flow shop makespan problem with release dates.A new lower bound of the problem is presented.The new lower bound is asymptotically equivalent to the optimality solution,when the size of the problem goes to infinity.And a tight worst case performance ratio,m,of the optimal solution to the new lower bound is obtained.Specially,when the processing times of jobs are all equal,the new lower bound is just the optimal solution.At the end of the paper,computational results show the effectiveness of the new lower bound on a set of random test problems.

关键词： flow shop makespan release date asymptotical analysis worst case analysis

作者: Danyu Bai Manchen Huo Lixin Tang

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

会议类型: 国际会议

会议名称: 2008 IEEE International Conference on Service Operations and Logistics, and Informatics(IEEE/SOLI’2008)(IEEE服务运作、物流与信息年会)

会议地点: 北京

会议语种:英文

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