Integrated Production, Inventory and Delivery Problems: Complexity and Algorithms

We consider several integrated production, inventory, and delivery problems that arise in a number of practical settings where customer orders have pre-specified delivery time windows. These orders are first processed in a plant and then delivered to the customers by transporters (such as trains and air flights) which have fixed delivery departure times. If an order is completed but not immediately delivered by a transporter, the order is kept temporarily in inventory, which incurs an inventory cost. There is a delivery cost for delivering an order, which varies with the departure time. Given a set of orders, the objective is to find an integrated schedule for processing the orders, keeping finished orders in inventory if necessary, and delivering them to the customers such that the total inventory and delivery cost is minimum. We consider two classes of problems: where order delivery is splittable and where order delivery is nonsplittable. For each of the problems considered, we study its computational complexity by either showing that the problem is NP-hard or proposing an algorithm that can find an optimal solution. For the two most general problems, we show that any polynomial time algorithm has an arbitrarily bad worst-case performance bound, and propose combined column generation and tabu search heuristic algorithms that can find near optimal solutions for them in a reasonable computational time.