A practical approach for integrated order and production scheduling problems

Many commercial manufacturers sell products to end users through retail dealers, referred to as customers. With limited manufacturing capacity and long lead times for raw materials, a manufacturer may not be able to fully deliver customer orders on time. Determining when to deliver and what quantities to deliver is the “order scheduling” problem. Ideally, order scheduling should be coupled with shop production scheduling. In view of the complexity of manufacturing environments, however, they are usually treated separately, leading to poor system performance. In this paper, the integrated order and production scheduling is considered for a simplified flowshop where the bottleneck is at the first stage of production, and the arrivals of raw materials are assumed to be given. A separable problem formulation is presented, and the problem, is solved by using the Lagrangian relaxation technique. Subproblems are solved by enumeration, and the Lagrange multipliers are updated at the high level by using the facet ascending algorithm. The algorithm is currently under implementation. This method has the potential to efficiently generate near optimal schedules with quantifiable quality