Parallel-machine scheduling with an availability constraint

e consider two parallel machines scheduling problem where one machine is not available in a specified time period. The unavailable time period is fixed and known in advance. The objective is to minimize the total weighted completion time. The problem is known to be NP-hard. We give a fully polynomial-time approximation scheme (FPTAS) for the problem. We then generalize the results to the case with m parallel machines.

► We consider two parallel machines scheduling problem with an availability constraint. ► We give an FPTAS for the objective to minimize the total weighted completion time. ► The algorithm can also be easily extended to m machine model.