Just-in-time scheduling with inventory holding costs

Reducing work-in-process and finished goods inventory holding (earliness) costs and improving on-time customer delivery are two conflicting objectives in a make-to-order supply chain. Ideally, in order to avoid inventory holding costs one would like to start production of a customer order such that it is completed just at the delivery due date; however, this strategy increases the risk of missing the delivery due date which is associated with explicit and/or implicit tardiness costs. In this thesis, we analyze this trade-off between inventory holding and tardiness costs for two systems, and develop approaches to minimize the total cost.; First, we consider a single-machine earliness/tardiness scheduling problem with general weights, ready times and due dates. Using completion time information obtained from the optimal solution to a preemptive relaxation, we generate feasible solutions to the original non-preemptive problem. We report extensive computational results demonstrating the speed and effectiveness of this approach.; Second, we consider the problem of scheduling customer orders in a serial supply chain with relatively expensive work-in-process, and potential delays between processing stages. We pose the problem as a flow shop scheduling problem with tardiness, earliness and intermediate inventory holding costs. We formulate this problem as an integer program, and based on solutions to two different, but closely related, Dantzig-Wolfe reformulations, which are solved approximately by column generation, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig-Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with simple and effective ways of obtaining near-optimal feasible integer solutions. To the best of our knowledge, this is the first time column generation is applied to a scheduling problem with different types of strongly $NP$-hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, and they yield good lower bounds and near-optimal feasible integer solutions.