Worst-case analysis of LPT scheduling on a small number of non-identical processors |
| |
| Affiliation: | 1. The Institute of Mathematical Sciences (CI of Homi Bhabha National Institute, Mumbai), CIT Campus, Taramani, Chennai, 600113, TN, India;2. Indian Institute of Technology Hyderabad, Kandi, Sangareddy, Hyderabad, 502285, Telangana, India;1. Faculty of Engineering, Maebashi Institute of Technology, 460-1 Kamisadori-machi, Maebashi, Gunma 371-0816, Japan;2. Faculty of Science, Kanagawa University, 2946 Tsuchiya, Hiratsuka, Kanagawa 259-1293, Japan;1. Indian Institute of Technology Madras, Chennai, India;2. University of Trier, Trier, Germany;3. Universidade Federal Fluminense, Niterói, Brazil;4. University of Warsaw, Warsaw, Poland |
| |
| Abstract: | The approximation ratio of the longest processing time (LPT) scheduling algorithm has been investigated in various studies. While the tight approximation ratio is known for the cases when all processors are identical, the ratio is unknown when the processors have different speeds. In this study, we provide a tight approximation ratio for three, four, and five processors. We show that the ratios for these cases are no larger than the lower bound provided by Gonzalez et al. (1977) 14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively. |
| |
| Keywords: | Scheduling algorithm LPT algorithm Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
