Semi-online Bin Stretching with Non-increasing Job Processing Times

摘要：

In this paper, we study an semi-online version of bin stretching problem on m parallel identical machines. Where the jobs arrive sorted by non-increasing processing times. We propose an semi-online algorithm and prove that the competitive ratio of the algorithm is at most 1 + m-1-4m-2 < 5/4. We also show that the lower bound of the problem is at least 10/9.

关键词： scheduling semi-online parallel machines design and analysis of algorithms competitive ratio

作者: Yong Wu Qifan Yang Yikun Huang

作者单位: Ningbo Institute of Technology Zhejiang University Ningbo 315100, PR China Department of Mathematics Zhejiang University Hangzhou 310027, PR China School of Sciences Linyi Normal University Linyi, 276000, PR China

会议类型: 国际会议

会议名称: The 2010 International Conference on Computer Application and System Modeling(2010计算机应用与系统建模国际会议 ICCASM 2010)

会议地点: 太原

会议语种:英文

页码: 562-566

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