Abstract: In this paper, we introduce relaxation of a semi-online model and discuss a new semi-online relaxation model: known largest job interval. We investigate P2|known largest job interval| Cmax problem and P2|known largest job interval| Cmin problem, respectively. For these two problems, we present an algorithm called PInterval, and derive its tight competitive ratios. We also discuss characteristics of these two problems and competitive ratio of the LS algorithm.

Key words: semi-online, identical machine, competitive ratio, relaxation