Makespan Minimization For Two Parallel Machines Scheduling With A Periodic Availability Constraint

摘要

A two parallel machines scheduling problem where one machine is periodically unavailable with the objective of minimizing makespan is considered,It is showed that the worst-case ratio of the classical LPT algorithm and the competitive ratio of the LS algorithm are 3/2 and 2,respectively,for the offline version and the online version of the problem.