Parallel machines scheduling with deteriorating jobs and availability constraints

We consider parallel machines scheduling problem in which the actual processing time of the job is a proportional function of its starting time and each machine is not available in a specified time period. We consider the non-resumable case. The objective is to minimize the weighted sum of completion times. We show that the general case of the problem is inapproximable unless P = NP and present a pseudopolynomial dynamic programming algorithm. We also present a fully polynomial-time approximation scheme for the special case of the problem where only one machine is not available in a specified time period.