TABLE OF CONTENTS To solve the OSP, we must decide which orders to select and, among the selected orders, how much of the order we will satisfy while obeying capacity limits. We can show that this problem is NP-Hard through a reduction from the capacitated lot-sizing problem as follows. If we consider the special case of the OSP in which ? j t=1 C t ? ? j t=1 ? m ? M( t) d mt for j = 1, , T (which implies that satisfying all orders is feasible) and
Given that the OSP is NP-Hard, we would like to find an efficient method for obtaining good solutions for this problem. As our computational test results in Section 4 later show, we were able to find optimal solutions using branch-and-bound for many of our randomly generated test instances. While this indicates that the majority of problem instances we considered were not terribly difficult to solve, there were still many instances in which an optimal solution could not be found in reasonable computing time. Based on our computational test experience in effectively solving problem instances via branch-and-bound using the CPLEX 6.6 solver, we focus on strong LP relaxations for the OSP...
