Scheduling with fixed delivery dates and temporary storage

摘要

We considered the single machine scheduling with fixed delivery dates and temporary storage. The objective is to minimize the sum of the makespan and the total inventory costs. We showed that the problem is strongly NP-hard and polynomial-time approximation algorithm with a fixed performance ratio does not exist for the problem unless P=NP. A polynomial 3/2 -approximation algorithm for the case with period delivery times was presented and the performance ratio of 3/2 can not be improved unless P=NP.