This paper focuses on a tool replacement problem to determine tool replacement schedules in a machining centre that produces multiple types of products with given due dates using multiple types of tools. For the problem, we develop new tool replacement policies with the objective of minimizing the sum of tool purchasing costs, material costs, and the tardiness penalty costs of not meeting due dates. In these policies, tool replacement intervals or exact times for tool replacements are determined using the information on the accumulated actual processing time and the processing time of the operation. The suggested policies are compared with other policies that are used in practice or suggested in previous research through a series of computational experiments on a number of test problems. Results of the computational tests show that the new replacement policy gives better performance than existing policies.