Abstract
Mixed model assembly line literature involves two problems: balancing and model sequencing. The general tendency in current studies is to deal with these problems in different time frames. However, in today’s competitive market, the mixed model assembly line balancing problem has been turned into an operational problem. In this paper, we propose mixed integer programming (MIP) and constraint programming (CP) models which consider both balancing and model sequencing within the same formulation along with the optimal schedule of tasks at a station. Furthermore, we also compare the proposed exact models with decomposition schemes developed for solving different instances of varying sizes. This is the first paper in the literature which takes into account the network type precedence diagrams and limited buffer capacities between stations. Besides, it is the first study that CP method is applied to balancing and scheduling of mixed model assembly lines. Our empirical study shows that the CP approach outperforms the MIP approach as well as the decomposition schemes.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aggoun, A., & Beldiceanu, N. (1993). Extending CHIP in order to solve complex scheduling and placement problems (Mathl. Comput. Modelling) (vol. 17, no. 7, pp. 57–73). Pergamon Press Ltd.
Agnetis, A., & Arbib, C. (1997). Concurrent operations assignment and sequencing for particular assembly problems in flow lines. Annals of Operation Research, 69, 1–31.
Akgündüz, O.S., & Tunalı, S. (2009). An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem. International Journal of Production Research, 48(17), 5157–5179.
Appa, G., Mourtos, I., Magos, D. (2002). Integrating constraint and integers programming for the orthogonal latin squares problem, principles and practice of constraint programming - CP 2002 (pp. 79–90). Springer.
Andres, C., Miralles, C., Pastor, R. (2008). Balancing and scheduling tasks in assembly lines with sequenc-dependent setup times. European Journal of Operational Research, 187, 1212–1223.
Baptiste, P., & Le Pape, C. (1996). Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. In Proceedings of the fifteenth workshop of the UK planning special interest group. Liverpool.
Baptiste, P., Le Pape, C., Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer Academic Publishers, Boston.
Bartak, R. (2003). Constraint-based scheduling: An introduction for newcomers. Intelligent manufacturing systems 2003 (pp. 69–75).
Bockmayr, A., & Pisaruk, N. (2001). Solving an assembly line balancing problem by combining IP and CP. In Proceedings of the 6th annual workshop of ERCIM working droup on constraints. Prague, Czech Republic.
Boysen, N., Fliedner, M., Scholl, A. (2008). Assembly line balancing: Which model to use when. International Journal of Production Economics, 111, 509–528.
Boysen, N., Fliedner, M., Scholl, A. (2009). Sequencing mixed-model assembly lines: Survey, classification and model crituqe. European Journal of Operational Research, 192, 349–773.
Boysen, N., Fliedner, M., Scholl, A. (2009). Production planning of mixed-model assembly lines: overview and extensions. Production Planning & Control, 20(5), 455–471.
Brailsfard, S.C., Potts, C.N., Smith, B.M. (1999). Constraint satisfaction problems: algorithms and applications. European Journal of Operational Research, 119, 557–581.
Davenport, A., Gefflot, C., Beck, J. (2001). Slack-based techniques for robust schedules. In Proceedings of 6th European conference on planning (ECP-01).
Dincbas, M., Simonis, H., van Hentenryck, P. (1988). Solving the car-sequencing problem in constraint logic programming. In Proceedings of the European conference on artificial intelligence (ECAI-88) (pp. 290–295). München.
Drexl A., & Kimms, A. (2001). Sequencing JIT mixed-model assembly lines under station-load and part-usage constraints. Management Science, 47(3), 480–491.
Focacci, F., Lodi, A., Milano, M. (2002). Mathematical programming techniques in constraint programming: A short overview. Journal of Heuristics, 8, 7–17.
Focacci, F., Laborie, P., Nuijten, W. (2000). Solving scheduling problems with setup times and alternative resources. AIPS 2000 Proceedings (pp. 92–101).
Fourer, R., & Gay, D.M. (2002). Extending an algebraic modeling language to support constraint programming. INFORMS Journal on Computing, 14(4), 322–344.
Gao, H. (1995). Building robust schedules using temporal protection protection-an empirical study of constraint based scheduling under machine failure uncertainty. Master’s thesis, Department of Industrial Engineering, University of Toronto.
Haralick, R.M., & Elliott, G.L. (1980). Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263–314.
Hentenryck, P. (2002). Constraint and integer programming in OPL. INFORMS Journal on Computing, 14(4), 345–372.
Hentenryck, P., Perron, L., Puget, J.F. (2000). Search and strategies in OPL. ACM Transactions on Computational Logic, 1(2), 285–320.
Hentenryck, P. (1989). Constraint satisfaction in logic programming. MIT Press, Cambridge.
Hentenryck, P., Carillon, J.P. (1988). Generality versus specificity: An experience with AI and OR techniques (AAAI-88, 1988) (pp. 660–664). Minnesota.
Hoeve, W., Katriel, I. (2006). Global Constraints. In Rossi, F., van Beek, P., Walsh, T. (Ed.), Handbook of constraint programming (pp. 169–208). Elsevier Science, Amsterdam.
ILOG (2003). OPL Studio 3.7. Language Manual.
Jain, V., & Grossmann, I.E. (2001). Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems. INFORMS Journal on Computing, 13(4), 258–276.
Kara, Y. (2008). Line balancing and model sequencing to reduce work overload in mixed-model U-line production environments. Engineering Optimization, 40(7), 669–684.
Karabatı, S., & Sayın, S. (2003). Assembly line balancing in a mixed-model sequencing environment with synchronous transfers. European Journal of Operational Research, 149, 417–429.
Khayat, G.E., Langevin, A., Riopel, D. (2006). Integrated production and material handling scheduling using mathematical programming and constraint programming. European Journal of Operations Research, 175, 1818–1832.
Kim, Y.K., Kim, J.Y., Kim, Y. (2000a). A coevolutionary algorithm for balancing and sequencing in mixed model assembly lines. Applied Intelligence, 13, 247–258.
Kim, Y.K., Kim, S.J., Kim, J.Y. (2000b). Balancing and sequencing mixed-model U-lines with a co-evolutionary algorithm. Production Planning & Control, 11, 754–764.
Kim, Y.K., Kim, J.Y., Kim, Y. (2006). An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines. European Journal of Operational Research, 168, 838–852.
Krogt R., Geraghty J., Salman M.R., Little J. (2010). On supporting Lean methodologies using constraint-based scheduling. Journal of Scheduling, 13, 301–314.
Laborie, P., & Godard, D. (2007). Self-adapting large neighbourhood search: Application to single-mode scheduling problems. In Proc. of the 3rd multidisciplinary international conference on scheduling: Theory and applications (MISTA) (pp. 276–284).
Laborie, P., & Rogerie, J. (2008). Reasoning with conditional time-intervals. In Proc. 21th international FLAIRS conference (FLAIRS 2008) (pp. 555–560).
Laborie, P., Rogerie, J., Shaw, P., Vilím, P. (2009). Reasoning with conditional time-intervals, Part II: An algebraical model for resources. In Proc. 22th international FLAIRS conference (FLAIRS 2009) (pp. 201–206).
Martino, L. & Pastor, R. (2010). Heuristic procedures for solving the general assembly line balancing problem with setups. International Journal of Production Research, 48(6), 1787–1804.
Merengo, C., Nava, F., Pozzetti, A. (1999). Balancing and sequencing manual mixed-model assembly lines. International Journal of Production Research, 37(12), 2835–2860.
Milano, M., & Wallace, M. (2006). Integrating operations research in constraint programming. OR, 4, 175–219.
Milano, M., Ottosson, G., Refalo, P., Thorsteinsson, E.S. (2002). The role of integer programming techniques in constraint programming’s global constraints. INFORMS Journal on Computing, 14(4), 387–402.
Miltenburg, J. (2002). Balancing and scheduling mixed-model U-shaped production lines. International Journal of Flexible Manufacturing Systems, 14, 119–151.
Ottosson, G., Thorsteinsson, E.S., Hooker, J.N. (2002). Mixed global constraints and inference in hybrid CLP-IP solvers. Annals of Mathematics and Artificial Intelligence, 34(4), 271–290.
Özcan, U., & Toklu, B. (2009). Balancing two-sided assembly lines with sequence-dependent setup times. International Journal of Production Research, 48(18), 5363–5383.
Özdemir, R.G., Ayaǧ, Z., Çakır, D. (2004). Hazırlık sürelerinin azaltılması için bir hat dengeleme modeli (YA/EM 2004). Kocaeli.
Pastor, R., Ferrer, L., Garcia, A. (2007). Evaluating optimization models to solve SALBP. Lecture Notes in Computer Science, 2007(4705), 791–803.
Pinedo, M.L. (2008). Scheduling theory, algorithms, and systems, 3rd edn. Springer, New York.
Policella, N., Cesta, A., Oddi, A., Smith, S. (2004). Generating robust schedules through temporal flexibility. In Proc. ICAPS 04.
Puget, J.F., & Lustig, I. (2001). Constraint programming and maths programming. Knowledge Engineering Review, 16(1), 5–23.
Regin, J.C. (1994). A filtering algorithm for constraints of difference in CSPs (AAAI-94) (pp. 362–367). Washington.
Sawik, T. (2000). Simultaneous vs. sequential loading and scheduling of flexible assembly systems. International Journal of Production Research, 38, 3267–3282.
Sawik, T. (2002). Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line. European Journal of Operational Research, 143, 115–124.
Sawik, T. (2004). Loading and Scheculing of a flexible assembly system by mixed integer programming. European Journal of Operational Research, 154, 1–19.
Scholl, A. (1999). Balancing and sequencing assembly lines, 2nd edn. Physica, Heidelberg.
Scholl, A., Boysen N., Fliedner M. (2008). The sequence-dependent assembly line balancing problem. OR Spectrum, 30(3), 579–609.
Scholl, A., Boysen, N., Fliedner, M. (2011). The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics. OR Spectrum. doi:10.1007/s00291-011-0265-0.
Smith, B. (2006). Modelling. In Rossi, F., van Beek, P., Walsh, T. (Eds.), Handbook of constraint programming (pp. 377–406). Elsevier Science, Amsterdam.
Valle, C.D., Marquez, A.A., Gasca, R.M., Toro, M. (2003). On selecting and scheduling assembly plans using constraint programming. Lecture notes in computer science, 2003(2774), 1329–1336.
Wilhelm, W.E. (1999). A column-generation approach for the assembly system design problem with tool changes. International Journal of Flexible Manufacturing Systems, 11, 177–205.
Yavuz, M., & Akcali, E. (2007). Production smoothing in just-in-time manufacturing systems: a review of the models and solution approaches. International Journal of Production Research, 45(16), 3579–3597.
Zeballos, L.J., Quiroga, O.D., Henning, G.P. (2010). A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations. Engineering Applications of Artificial Intelligence, 23, 229–248.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Öztürk, C., Tunalı, S., Hnich, B. et al. Balancing and scheduling of flexible mixed model assembly lines. Constraints 18, 434–469 (2013). https://doi.org/10.1007/s10601-013-9142-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-013-9142-6