An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines |
| |
| Authors: | Christos Koulamas George J. Kyparisis |
| |
| Affiliation: | Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA |
| |
| Abstract: | We propose an off-line delayed-start LPT algorithm that sequences the first (longest) 5 jobs optimally and the remaining jobs according to the LPT principle on two identical parallel machines. We show that this algorithm has a sharper tight worst-case ratio bound than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem. |
| |
| Keywords: | Scheduling Parallel machines LPT Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
