We propose a novel method for integrating planning and scheduling problems under production uncertainties. The integrated problem is formulated into a bi-level program. The planning problem is solved in the upper level, while the scheduling problems in the planning periods are solved under uncertainties in the lower level. The planning and scheduling problems are linked via service level constraints. To solve the integrated problem, a hybrid method is developed, which iterates between a mixed-integer linear programming solver for the planning problem and an agent-based reactive scheduling method. If the service level constraints are not met, a cutting plane constraint is generated by the agent-based scheduling method and appended to the planning problem which is solved to determine new production quantities. The hybrid method returns an optimality gap for validating the solution quality. The proposed method is demonstrated by two complicated problems which are solved efficiently with small gaps less than 1%.
Planning and scheduling are two core decision layers in a man-ufacturing organization (Wassick et al., 2012). Owing to differentobjectives and time scales, planning and scheduling problems areoften solved separately in a sequential way. For example, a planningproblem can be solved to determine weekly production quanti-ties according to the customer orders. The output of the planningproblem, the weekly production quantities, are then passed tothe scheduling problem and a production schedule in each weekis determined, such as assigning an operational task to a capa-ble unit and sequencing the tasks in every unit. The sequentialnature of the traditional approach prevents the planning modelfrom using detailed production schedule information as the sched-uling problem is not solved in the planning phase. Instead, theplanning problem is solved based on aggregate information whichis commonly a rough approximation of the real production data. Forexample, a planning model often includes a parameter to denotethe time required to process a product but the actual processingtime, due to product transition policies, is highly dependent on theproduction schedule. Though widely applied for its simplicity, thesequential methods often result in a suboptimal solution for theentire production process, or even an infeasible production plan(F. You).that cannot be fulfilled by the scheduling procedure (Shen, Wang,& Hao, 2006; Tan & Khoshnevis, 2000).To overcome the drawbacks of sequential methods, a greatvariety of integrated methods have been developed (Birewar &Grossmann, 1990; Maravelias & Sung, 2009; Phanden, Jain, &Verma, 2011; Shao, Li, Gao, & Zhang, 2009), which aim to improvethe overall performance of the entire planning process by col-laboratively solving the production planning problem and thescheduling problem. A major category of the integrated methodsis the simultaneous methods, which solve a monolithic model for-mulated by combining all constraints of the planning model andthe scheduling model. The computational difficulty arising fromthe formulated complex model can be addressed by a decomposi-tion method (Li & Ierapetritou, 2009). The simultaneous methodscan theoretically obtain the global optimal solution for the entireprocess. However, they encounter some practical difficulties dueto the computational challenges (Shobrys & White, 2002). Imple-mentation of the simultaneous method may require dismantlingand reorganizing the existing production hierarchy in a company(Pinedo, 2009).Other types of integrated methods, based on bi-level pro-gramming, have been proposed in the literature (Ryu, Dua, &Pistikopoulos, 2004). The planning problem is the upper level prob-lem while the scheduling problem is the lower level problem, whichis consistent with the existing production hierarchy. A bi-leveloptimization problem is closely related with a Stackelberg gamewhich is played between a leader and multiple followers (Colson,Marcotte, & Savard, 2007). The planning problem acts as the leader,
ConclusionWe propose a bi-level model for formulating an integratedplanning and scheduling problem under production uncertainties.The upper level problem is the planning problem formulated asan MILP, while the lower level problem consists of schedulingproblems over the planning periods, which are modeled by agent-based systems. The planning problem is linked to the schedulingproblems via service level constraints that are probabilistic con-straints dependent on detailed schedules. To solve the integratedproblem, we develop a hybrid method combining an MILP solverand the agent-based method. The MILP planning problem issolved to determine production quantities over each planningperiod, which are then passed on to the agent-based simulationsfor scheduling. The agent-based method solves the reactivescheduling problems under certainties. When the service levelsare not satisfied, because of the assigned production quantitiesexceeding the available capacity, the agent-based method gener-ates cutting plane constraints. These constraints are then appendedto the planning problem, which is then solved again to determinethe new production quantities in the next iteration. The algorithmterminates when all service level constraints are satisfied.The bi-level formulation and the hybrid method are demon-strated by two complicated case studies. In the first case studywhere the threshold of the service levels is set as 0.95, the hybridmethod solves the problem using 8 iterations in 69 min. In the sec-ond case study where the threshold of the service levels is set as1.00, the hybrid method solves the problem using 12 iterationsin 101 min. The optimality gap for both case studies is less than1%.As the integrated planning and scheduling problem underuncertainties is too complicated to solve exactly, the proposedmethod include heuristics in the cutting plane approach and theevaluation of the probability service level functions. Also becauseof the complexity and the variety of the integrated problems, it isdifficult to determine, for a general problem, if the cutting planemethod will return a close-to-optimal solution or if the numberof samples for the Monte Carlo method is adequate with a givenprobability confidence. However, we can validate the performanceof the proposed method by applying it to a given specific problem.From the statistical test on the final solution, we can validate ifthe service level constraints are satisfied with the given probabilityconfidence. From the optimality gap, we can validate if the returnedobjective function value is close to the optimal one.
