A car production planning problem of minimizing the total cost concerning transportation and production constraints

This paper deals with a production planning problem at Toyota Motor Corporation. Car dealerships order cars on the basis of weekly instructions given by Toyota Motor Corporation. A weekly production plan for each type of car is made according to the orders obtained from the car dealerships. If a certain type of car is produced on more than one assembly line, weekly production plans need to be made for those assembly lines. When making a weekly production plan for each assembly line, there are two objectives that we must achieve. One is to minimize the total cost of shipment from the assembly lines to car dealerships. The other is related to the production constraints on the assembly lines. Factories with the assembly lines and suppliers have already finished preparing for production based on monthly production plans. If the difference between the monthly and weekly production plans for each assembly line is minimal, cars and parts can be produced without loss. If the difference is much, however, then the weekly production plan becomes impossible without changing production preparations. Hence, the second objective is to minimize the differences between monthly and weekly production plans. To achieve two objectives, we firstly define the production constraint cost for the difference between two production plans and consider minimizing the sum of the shipment cost and the production constraint cost. As a result, this production planning problem can be formulated as a separable programming problem with integer constraints. From another point of view, this problem can be considered as a Hitchcock transportation problem with the piecewise linear objective function for the sum of some variables and integer constraints. The algorithm for this problem has not yet been developed. At first we show that we can convert the problem into the minimum cost flow problem, if the production constraints satisfy certain conditions. These conditions hold for many practical problems. And we also show that the practical problems that do not satisfy the conditions have an integer solution due to the structure of the production constraints. Moreover, a local optimal solution of the problem is a global optimal solution. Then we can apply the linear programming algorithms to the problem instead of separable programming and solve it efficiently.