Title :
Semi-online bin stretching with non-increasing job processing times
Author :
Wu, Yong ; Yang, Qifan ; Huang, Yikun
Author_Institution :
Ningbo Inst. of Technol., Zhejiang Univ., Ningbo, China
Abstract :
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.
Keywords :
parallel machines; processor scheduling; bin stretching problem; competitive ratio; non-increasing job processing times; parallel identical machines; scheduling; semi-online algorithm; semionline bin stretching; Schedules; Competitive ratio; Design and analysis of algorithms; Parallel machines; Scheduling; Semi-online;
Conference_Titel :
Computer Application and System Modeling (ICCASM), 2010 International Conference on
Conference_Location :
Taiyuan
Print_ISBN :
978-1-4244-7235-2
Electronic_ISBN :
978-1-4244-7237-6
DOI :
10.1109/ICCASM.2010.5622660
