期刊
INFORMATION PROCESSING LETTERS
卷 183, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.ipl.2023.106424
关键词
Scheduling algorithm; LPT algorithm; Approximation algorithms
The investigation on the approximation ratio of the longest processing time (LPT) scheduling algorithm has been conducted in various studies. While the ratio is known for identical processors, it remains unknown for processors with different speeds. This study provides a tight approximation ratio for three, four, and five processors, showing that the ratios 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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据