Modeling and Analytical Solution of Integrated Scheduling and Capacity Planning Problem: Lower Bounds and Efficient Branch and Bound Algorithm

Production capacity planning and scheduling are parts of decision process in supply chain of many manufacturing and service industries, which have important role in satisfying customer requirements and enhancing customer service level. Since these two processes performs in two different levels of supply chain (capacity planning in tactical level and scheduling in operational one), usually their decision are made independently. In such circumstances, the feasibility of capacity decisions in tactical level, when plan imports into the shop floor, is one of the critical challenges in this decision making approach. Hence in this paper, after formulating the capacity planning and two-machine scheduling problems integrately, an analytical solution approach will be presented. In order to minimize the maximum completion time of orders, concept of order pairs is defined and the optimal orders pairs are established based on the optimal solution of symmetric assignment problem. Afterwards, to determine the optimal sequence of order pairs, a branch and bound procedure is designed which is based on three proposed lower bounds, depth first and best first strategies. To improve the efficiency of algorithm, some mathematical properties are proved and some corresponding dominance rules are derived. Furthermore, to delineate the quantity of resource allocation to the operations, a neighborhood search algorithm is designed and improved based on some structural properties of problem.