While demands for express service are rapidly increasing according to recent progress of electronic commerce, express service companies are struggling to take a larger delivery service market share through ongoing improvement in their service processes. Extension of cut-off time for express service centers can provide the express company with increase of total sales, but it may also cause to increase the possibility not to satisfy customer needs due to work delay in the consolidation terminal. Therefore, compromised decision for cut-off time of each service center should be made by taking operation characteristics of the consolidation terminal into account. This study suggests an approach for determining the cut-off time for express service centers according to operational characteristics of the consolidation terminal with the objective of maximizing expected incremental sales. The problem defined in this study can be represented as two successive models; one is an integer programing model in which the best cut-off time for each sales center are determined, and the other is a single machine scheduling model in which a working schedule in the consolidation terminal is obtained. A genetic algorithm is developed to solve the two models simultaneously. Finally, an example problem is carried out to verify applicability and performance of the algorithm with the data set collected from an express company.