Strategies of financial institutions on cash replenishment and maintenance for a network of automated teller machines should be treated as a whole instead of independent of one another. Cash replenishment is a type of maintenance and having separate service providers conduct this type of maintenance adds costs and liabilities to the financial institutions. The optimal strategy to be employed focuses on the reduction of cash-related expenses, while maintaining the appropriate banknote-levels in each ATM; minimizing cash-dry instances on individual teller machines. With the increasing concern of financial institutions for customer satisfaction, the optimal strategy will also consider the amount of maintenance to be conducted for each ATM; minimizing downtime on individual teller machines. Factors such as daily service capacity, replenishment need, maintenance need, available time, travel time and service time are to be considered. The proposed model is able to solve situations where multiple machines are expected to breakdown on a certain day, as well as single replenishments spread throughout different days. Furthermore, the dynamic element of the scheduling problem enables the model to consider changes after new forecasts or behavior for replenishment or maintenance have been made for different teller machines, after the service schedule that had been initially made.