This paper deals with the advanced planning and scheduling (APS) problem with multilevel structured products. A constraint programming model is constructed for the problem with the consideration of precedence constraints, capacity constraints, release time and due date. A new constraint programming (CP) method is proposed to minimize the total cost. This method is based on iterative solving via branch and bound. And, at each node, the constraint propagation technique is adapted for domain filtering and consistency check. Three branching strategies are compared to improve the search speed. The results of computational study show that the proposed CP method performs better than the traditional mixed integer programming (MIP) method. And the binary constraint heuristic branching strategy is more effective than the other two branching strategies. 1. Introduction The complexity of planning processes makes most of companies develop the enterprise resource planning (ERP) system to deal with it [1]. However, as the core planning module of ERP system, material requirement planning (MRP) has its limitations. MRP generally makes plan according to finite material requirements and infinite capacity requirements, meanwhile the production lead time which is actually depending on production planning is predetermined. To cope with these limitations, advanced planning and scheduling (APS) has evolved from both software developers and academics. Compared to these traditional planning systems, APS systems offer the advantage that plans can be optimized within the boundaries of material and capacity constraints [2]. Both academicians and commercial APS providers (such as SAP APO, i2, and Asprova) have attempted to construct effective methods to generate detailed production schedules to balance the demand of the marketplace with the resources capacity. Mathematical programming and heuristic algorithms are often used to achieve this balance. Heuristic algorithms usually concentrate on bottleneck resources [3]. For example, Kung and Chern propose a heuristic factory planning algorithm (HFPA) to solve factory planning problem for product structures with multiple final products. It first identifies the bottleneck work, center then sorts jobs according to various criteria, and finally plans jobs in three iterations [4]. Previous studies have often adopted mix integer programming model to represent the planning and scheduling problem. Moon et al. suggested an advanced planning and scheduling model which integrates capacity constraints and precedence constraints to minimize the
References
[1]
K. Sheikh, Manufacturing Resource Planning (MPR II) with an Introduction to ERP, SCM, and MRP, McGraw-Hill, New York, NY, USA, 2003.
[2]
Advanced Planning and Scheduling in High Tech industry. A Eyeon white paper.
[3]
H. Stadtlere and C. Kilger, Supply Chain Management and Advanced Planning: Concepts, Models, Software and Case Studies, Springer, Berlin, Germany, 3rd edition, 2005.
[4]
L.-C. Kung and C.-C. Chern, “Heuristic factory planning algorithm for advanced planning and scheduling,” Computers and Operations Research, vol. 36, no. 9, pp. 2513–2530, 2009.
[5]
C. Moon, J. S. Kim, and M. Gen, “Advanced planning and scheduling based on precedence and resource constraints for e-plant chains,” International Journal of Production Research, vol. 42, no. 15, pp. 2941–2954, 2004.
[6]
K. J. Chen and P. Ji, “A mixed integer programming model for advanced planning and scheduling (APS),” European Journal of Operational Research, vol. 181, no. 1, pp. 515–522, 2007.
[7]
A. ？rnek, S. ？zpeynirci, and C. ？ztürk, “A note on ‘A mixed integer programming model for advanced planning and scheduling (APS)’,” European Journal of Operational Research, vol. 203, no. 3, pp. 784–785, 2010.
[8]
C. ？ztürk and A. M. Ornek, “Operational extended model formulations for advanced planning and scheduling systems,” Applied Mathematical Modelling, vol. 38, no. 1, pp. 181–195, 2014.
[9]
S. Kreipl and M. Pinedo, “Planning and scheduling in supply chains: an overview of issues in practice,” Production and Operations Management, vol. 13, no. 1, pp. 77–92, 2004.
[10]
Y. Chen, Z. Guan, Y. Peng, X. Shao, and M. Hasseb, “Technology and system of constraint programming for industry production scheduling. Part I: a brief survey and potential directions,” Frontiers of Mechanical Engineering in China, vol. 5, no. 4, pp. 455–464, 2010.
[11]
S. Topaloglu, L. Salum, and A. A. Supciller, “Rule-based modeling and constraint programming based solution of the assembly line balancing problem,” Expert Systems with Applications, vol. 39, no. 3, pp. 3484–3493, 2012.
[12]
H.-H. Hvolby and K. Steger-Jensen, “Technical and industrial issues of advanced planning and scheduling (APS) systems,” Computers in Industry, vol. 61, no. 9, pp. 845–851, 2010.
[13]
K. Steger-Jensen, H.-H. Hvolby, P. Nielsen, and I. Nielsen, “Advanced planning and scheduling technology,” Production Planning and Control, vol. 22, no. 8, pp. 800–808, 2011.
[14]
Y.-S. Yun and M. Gen, “Advanced scheduling problem using constraint programming techniques in SCM environment,” Computers and Industrial Engineering, vol. 43, no. 1-2, pp. 213–229, 2002.
[15]
L. J. Zeballos, O. D. Quiroga, and G. P. Henning, “A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations,” Engineering Applications of Artificial Intelligence, vol. 23, no. 2, pp. 229–248, 2010.
[16]
F. Rossi and P. T. Walsh, Handbook of Constraint Programming, Elsevier, Amsterdam, The Netherlands, 2006.
[17]
A. S. Jain and S. Meeran, “Deterministic job-shop scheduling: past, present and future,” European Journal of Operational Research, vol. 113, no. 2, pp. 390–434, 1999.
[18]
C. Artigues and D. Feillet, “A branch and bound method for the job-shop problem with sequence-dependent setup times,” Annals of Operations Research, vol. 159, pp. 135–159, 2008.
