Not only in civil economic system but also in military, there are supplier and customer. Each combat unit is supplied with military commodities by support units. One of the problems facing the commander of support units during a combat situation is how to plan the deployment of the units under his command to make logistics service effectively. Commodities of military logistics are usually classified into 9 classes such as food, fuel, ammunition and so on and each support unit of ROK (Republic of Korea) army manages only one of them. To meet various logistics commodity needs combat units must be supported by various support units. When the location and demand of each combat unit is known, it is the objective of this paper to find the optimal deployment plan to maximize total effectiveness of logistics service over planning periods. In this paper the deployment problem of support units is formulated as an integer programming model and an optimal solution can be obtained by a dynamic programming model finding an optimal deployment plan over planning periods. A heuristic based on genetic algorithm is developed for same problem and its performance is analyzed.