Semi on-line scheduling on two parallel processors with known sum and lower bound on the size of the tasks

In this paper a semi on-line scheduling problem is studied and an optimal algorithm (with respect to the competitive ratio) is proposed. A finite number of tasks have to be assigned to two parallel processors. The tasks are released one at a time and must be immediately assigned to a processor. The size of the tasks is known only at the time they are released, but the total sum and a lower bound β on the size of the tasks are given in advance. The minimization of the maximum completion time (makespan) is required. When all the information is known in advance, the problem is said to be of-line and is known to be NP-hard. In this case a linear time complexity algorithm with worst case ratio equal to 12/11 is known. The pure on-line problem, where no information is given in advance, can be approached by 3/2-competitive optimal algorithms. Optimal 4/3-competitive algorithms are proposed in the literature on different semi on-line variants. We consider one of these problems where the total size of the tasks is given, propose an alternative 4/3-competitive optimal algorithm and show that if a lower bound β on the size of the tasks is known to hold, then the competitive ratio of the algorithm may improve and the algorithm is guaranteed to be optimal with respect to β for all β's.