Semi-online bin stretching with non-increasing job processing times
Yong Wu, Qifan Yang, Yikun Huang · 2010
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 + 2m-1/4m-2 <; 5/4 We also show that the lower bound of the problem is at least 10/9.