On-line and semi on-line scheduling on parallel machines with non-simultaneous machine available times

This paper investigates on-line and semi on-line scheduling problems on parallel machines with non-simultaneous machine available times. In on-line version, we prove that the worst-case ratio of LS algorithm is 2–1/m. Three semi on-line scheduling problems are studied, where the jobs are ordered by decreasing processing times, the total processing time or the largest processing time. For each problem, we analyze its lower bound and give approximation algorithms. The algorithms are all the best possible ones for a two-machine case.