New algorithms for integrated production and transportation scheduling problems with committed delivery due dates

Abstract

Production and transportation, which are two key processes in the supply chains, play critical roles in improving the competitiveness of a company in the global markets. Therefore, integrated production and transportation scheduling becomes more necessary for companies to be responsive to the demands of the customers and reduce the costs to the best of their ability. In this thesis, we focus on two variants of the integrated production and transportation problem faced by manufacturing companies under a make-to-order business strategy and a commit-to-delivery business mode. One variant is to consider the issue of order acceptance. It means that when receiving the orders, the manufacturing company needs to decide which orders are to be accepted and which are to be rejected. The other variant is to incorporate the inventory holding costs incurred during the production and shipping processes of the orders. The original integrated production and transportation problem with committed delivery due dates is known to be strongly NP-hard and the computational hardness can also be applied to these two variants. This thesis contributes to the development of new exact algorithms and approximation algorithms for these two variants. The first problem we studied in this thesis is the integrated production and transportation scheduling problem with committed delivery due dates and order acceptance (IPTSDA). For this problem, we develop two new exact algorithms that can solve the problem IPTSDA to optimality, and we prove that they can achieve polynomial or pseudo-polynomial running times for two practical cases of problem IPTSDA, respectively. In addition to the two exact algorithms, and by extending the second exact algorithm, we also develop a pseudo-polynomial time approximation scheme for the problem IPTSDA. It not only ensures a worst-case performance ratio of (1 + e) for any fixed e > 0, but also achieves good computational performance through the computational experiments. The second problem we studied in this thesis is the integrated production and transportation scheduling problem with committed delivery due dates and inventory holding costs (IPTSDI). The incorporation of inventory holding costs into the objective function makes the problem more complex. To reduce possible inventory holding costs, the manufacturer wants to postpone the production as late as possible. However, this would lead to an increase in the shipping costs due to the decrease in transportation time. Therefore, the manufacturer needs to determine a production plan and a shipping plan that could delicately balance the shipping costs and inventory holding costs. For this problem, we innovatively propose a backward-forward construction algorithm. Based on the backward-forward algorithm, and utilizing our algorithms for problem IPTSDA in the first study, we develop several new exact algorithms with pseudo-polynomial running times for two practical cases of problem IPTSDI. The backward-forward algorithm also helps to develop the new approximation algorithms that can guarantee a worst-case performance ratio of (1 + e) for any positive constant e.