In this paper, we introduce a new approach based on DC (Difference of Convex functions) Programming and DCA (DC Algorithm) for minimizing the maintenance cost involving flow-time and tardiness penalties. The main idea is to divide the horizon considered into H intervals and the problem is first formulated as a mixed integer linear problem (MILP). It is afterward reformulated in the form of a DC program by an exact penalty technique. Solution method based on DCA is investigated to solve the resulting problem. The efficiency of DCA is compared with the algorithm based on the new flow-time and tardiness rule (FTR) given in [8]. The computational results on several test problems show that the solutions provided by DCA are better.