Models and algorithms for supply chain network with bi-directional flows

This dissertation was motivated by several operational scheduling problems encountered in real life distribution networks with bi-directional flows, where the forward flow sends new supplies to meet the customer demand while the reverse flow brings back the used ones. The operational performance of such networks depends, to a great extent, the efficiency and the effectiveness of the scheduling algorithms. However, despite an enormous amount of existing literature results, search algorithms for scheduling the operations, especially the integrated production, inventory, and distribution operations, with bi-directional flows are very limited. Analyzing, constructing, and evaluating the new search algorithms for effectively solving the scheduling problems in a bi-directional flow network is therefore the main focus of this research.; The first model focuses on the integrated production and distribution problem with bi-directional flows defined upon a three-stage supply chain network. We propose a partial linear programming relaxation-based heuristic approach to solve a variation of this problem, and derive a theoretical error gap between the optimal solution and the heuristic solution provided by this partial relaxation. We then report the computational performance of the proposed heuristic under various parameter settings. Applications to a medical equipment leasing network that involves a forward flow for new and refurbished devices and a reverse flow for used devices to be returned to suppliers over a multiple time-period planning horizon are discussed.; The second model focuses on the container-vessel scheduling problem involving the forward flow of cargo containers and a reverse flow of empty containers between foreign origin port and a domestic destination port. The forward order of cargoes for period t must arrive at the destination no later than t, and the return order of empty containers for period t becomes available at the destination port only at or after t. Each vessel can perform a round trip, departing from and then returning to the origin port, in each time period. We prove that this problem is strongly NP-hard and present three results. First, we show that if all the forward and return orders are integer multiples of vessel load, then the problem is totally unimodular and can be solved optimally as a linear program. Second, we show that if every order, either forward or return, is less than a vessel load, then in the optimal solution at most one vessel trip is needed for each time period. Third we propose a mathematical problem based heuristic algorithm for solving the general problem based on the first two results. Empirical observations on the error gaps by this heuristic are reported.; Our third model extends the work reported on the second model, and focuses on the customer order assignments to the vessels in a bi-directional flow shipping process. We provide the properties of the resulting vessel scheduling problem, show its complexity, and derive the optimality conditions under which the vessel scheduling problem can be decomposed. The result of this analysis then lead to the construction of a fast greedy heuristic vessel scheduling algorithm. Computational performance of the proposed heuristic is presented.; Finally, several major extensions of this research are discussed.