An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

作者：Koulamas Christos^*; Kyparisis George J

来源：European Journal of Operational Research, 2008, 187(2): 660-666.

DOI：10.1016/j.ejor.2007.04.013

• scheduling
• parallel machines
• LPT
• approximation algorithms

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.

• 出版日期2008-6-1