Abstract:  In the process of two competitive companies zero-sum game, maximize the product of the two company proceeds, equivalent to minimize the sum of the squares of the machine completion times on two identical parallel machines. We consider an off-line modified delayed-start LPT algorithm: firstly, renumber the jobs in the non-decreasing processing time order; secondly, if the total processing time $P(2m)$ of the longest $2m$ jobs is less than $(2m+1)p_{2m+1}$, schedule the first $2m+1$ jobs optimally followed by the remaining jobs scheduled according to the LPT rule; otherwise, $P(2m)$ is not less than $ (2m+1)p_{2m+1}$, schedule the first $2m$ jobs optimally followed by the remaining jobs scheduled according to the LPT rule. We prove that the worst case ratio of this algorithm is not greater than $1+ (\frac{1}{2m+2} )^2$, and the bound is tight.

Key words: off-line scheduling, modified delayed-start LPT algorithm, worst case ratio