New exact and approximation algorithms for integrated production and transportation scheduling with committed delivery due dates and order acceptance

The problem of integrated production and transportation scheduling, commonly faced by make-to-order manufacturers under a commit-to-delivery business mode, is known to be strongly NP-hard. In this study, we propose two new exact algorithms to solve the problem with order acceptance decisions also taken into account. These algorithms can achieve polynomial or pseudo-polynomial running times in several practical situations. We also develop the first pseudo-polynomial time approximation scheme for this problem. It not only guarantees a worst-case performance ratio of (1+ϵ) for any fixed ϵ>0, but also achieves good computational performance.