zbMATH — the first resource for mathematics

Balancing and scheduling of flexible mixed model assembly lines. (English) Zbl 1304.90149
Summary: 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.

90C11 Mixed integer programming
90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] 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.
[2] Agnetis, A; Arbib, C, Concurrent operations assignment and sequencing for particular assembly problems in flow lines, Annals of Operation Research, 69, 1-31, (1997) · Zbl 0880.90068
[3] Akgündüz, OS; Tunalı, S, An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem, International Journal of Production Research, 48, 5157-5179, (2009) · Zbl 1197.90320
[4] 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.
[5] Andres, C; Miralles, C; Pastor, R, Balancing and scheduling tasks in assembly lines with sequenc-dependent setup times, European Journal of Operational Research, 187, 1212-1223, (2008) · Zbl 1137.90476
[6] 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.
[7] Baptiste, P., Le Pape, C., Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer Academic Publishers, Boston. · Zbl 1094.90002
[8] Bartak, R. (2003). Constraint-based scheduling: An introduction for newcomers. Intelligent manufacturing systems 2003 (pp. 69-75). · Zbl 1160.90464
[9] 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.
[10] Boysen, N; Fliedner, M; Scholl, A, Assembly line balancing: which model to use when, International Journal of Production Economics, 111, 509-528, (2008)
[11] Boysen, N; Fliedner, M; Scholl, A, Sequencing mixed-model assembly lines: survey, classification and model crituqe, European Journal of Operational Research, 192, 349-773, (2009) · Zbl 1157.90405
[12] Boysen, N; Fliedner, M; Scholl, A, Production planning of mixed-model assembly lines: overview and extensions, Production Planning & Control, 20, 455-471, (2009)
[13] Brailsfard, SC; Potts, CN; Smith, BM, Constraint satisfaction problems: algorithms and applications, European Journal of Operational Research, 119, 557-581, (1999) · Zbl 0938.90055
[14] Davenport, A., Gefflot, C., Beck, J. (2001). Slack-based techniques for robust schedules. In Proceedings of 6th European conference on planning (ECP-01). · Zbl 1193.90235
[15] 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. · Zbl 1073.90514
[16] Drexl, A; Kimms, A, Sequencing JIT mixed-model assembly lines under station-load and part-usage constraints, Management Science, 47, 480-491, (2001) · Zbl 1232.90110
[17] Focacci, F; Lodi, A; Milano, M, Mathematical programming techniques in constraint programming: A short overview, Journal of Heuristics, 8, 7-17, (2002) · Zbl 1073.90035
[18] Focacci, F., Laborie, P., Nuijten, W. (2000). Solving scheduling problems with setup times and alternative resources. AIPS 2000 Proceedings (pp. 92-101).
[19] Fourer, R; Gay, DM, Extending an algebraic modeling language to support constraint programming, INFORMS Journal on Computing, 14, 322-344, (2002) · Zbl 1238.90113
[20] 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. · Zbl 0949.90570
[21] Haralick, RM; Elliott, GL, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263-314, (1980)
[22] Hentenryck, P, Constraint and integer programming in OPL, INFORMS Journal on Computing, 14, 345-372, (2002) · Zbl 1238.90102
[23] Hentenryck, P; Perron, L; Puget, JF, Search and strategies in OPL, ACM Transactions on Computational Logic, 1, 285-320, (2000) · Zbl 1365.90281
[24] Hentenryck, P. (1989). Constraint satisfaction in logic programming. MIT Press, Cambridge.
[25] Hentenryck, P., Carillon, J.P. (1988). Generality versus specificity: An experience with AI and OR techniques (AAAI-88, 1988) (pp. 660-664). Minnesota.
[26] Hoeve, W; Katriel, I; Rossi, F (ed.); Beek, P (ed.); Walsh, T (ed.), Global constraints, 169-208, (2006), Amsterdam · Zbl 1190.90240
[27] ILOG (2003). OPL Studio 3.7. Language Manual.
[28] Jain, V; Grossmann, IE, Algorithms for hybrid MILP/CP models for a class of optimization problems, INFORMS Journal on Computing, 13, 258-276, (2001) · Zbl 1238.90106
[29] Kara, Y, Line balancing and model sequencing to reduce work overload in mixed-model U-line production environments, Engineering Optimization, 40, 669-684, (2008)
[30] Karabatı, S; Sayın, S, Assembly line balancing in a mixed-model sequencing environment with synchronous transfers, European Journal of Operational Research, 149, 417-429, (2003) · Zbl 1103.68117
[31] Khayat, GE; Langevin, A; Riopel, D, Integrated production and material handling scheduling using mathematical programming and constraint programming, European Journal of Operations Research, 175, 1818-1832, (2006) · Zbl 1142.90371
[32] Kim, YK; Kim, JY; Kim, Y, A coevolutionary algorithm for balancing and sequencing in mixed model assembly lines, Applied Intelligence, 13, 247-258, (2000)
[33] Kim, YK; Kim, SJ; Kim, JY, Balancing and sequencing mixed-model U-lines with a co-evolutionary algorithm, Production Planning & Control, 11, 754-764, (2000)
[34] Kim, YK; Kim, JY; Kim, Y, An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines, European Journal of Operational Research, 168, 838-852, (2006) · Zbl 1083.90016
[35] Krogt, R; Geraghty, J; Salman, MR; Little, J, On supporting Lean methodologies using constraint-based scheduling, Journal of Scheduling, 13, 301-314, (2010)
[36] 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). · Zbl 1232.90110
[37] Laborie, P., & Rogerie, J. (2008). Reasoning with conditional time-intervals. In Proc. 21th international FLAIRS conference (FLAIRS 2008) (pp. 555-560).
[38] 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). · Zbl 0880.90068
[39] Martino, L; Pastor, R, Heuristic procedures for solving the general assembly line balancing problem with setups, International Journal of Production Research, 48, 1787-1804, (2010)
[40] Merengo, C; Nava, F; Pozzetti, A, Balancing and sequencing manual mixed-model assembly lines, International Journal of Production Research, 37, 2835-2860, (1999) · Zbl 0949.90570
[41] Milano, M; Wallace, M, Integrating operations research in constraint programming, OR, 4, 175-219, (2006) · Zbl 1125.90392
[42] Milano, M; Ottosson, G; Refalo, P; Thorsteinsson, ES, The role of integer programming techniques in constraint programming’s global constraints, INFORMS Journal on Computing, 14, 387-402, (2002) · Zbl 1238.90101
[43] Miltenburg, J, Balancing and scheduling mixed-model U-shaped production lines, International Journal of Flexible Manufacturing Systems, 14, 119-151, (2002)
[44] Ottosson, G; Thorsteinsson, ES; Hooker, JN, Mixed global constraints and inference in hybrid CLP-IP solvers, Annals of Mathematics and Artificial Intelligence, 34, 271-290, (2002) · Zbl 1026.90062
[45] Özcan, U; Toklu, B, Balancing two-sided assembly lines with sequence-dependent setup times, International Journal of Production Research, 48, 5363-5383, (2009) · Zbl 1197.90224
[46] Ö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.
[47] Pastor, R; Ferrer, L; Garcia, A, Evaluating optimization models to solve SALBP, Lecture Notes in Computer Science, 2007, 791-803, (2007)
[48] Pinedo, M.L. (2008). Scheduling theory, algorithms, and systems, 3rd edn. Springer, New York. · Zbl 1155.90008
[49] Policella, N., Cesta, A., Oddi, A., Smith, S. (2004). Generating robust schedules through temporal flexibility. In Proc. ICAPS 04. · Zbl 1152.90460
[50] Puget, JF; Lustig, I, Constraint programming and maths programming, Knowledge Engineering Review, 16, 5-23, (2001) · Zbl 0994.90133
[51] Regin, J.C. (1994). A filtering algorithm for constraints of difference in CSPs (AAAI-94) (pp. 362-367). Washington.
[52] Sawik, T, Simultaneous vs. sequential loading and scheduling of flexible assembly systems, International Journal of Production Research, 38, 3267-3282, (2000) · Zbl 1094.90563
[53] Sawik, T, Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line, European Journal of Operational Research, 143, 115-124, (2002) · Zbl 1073.90514
[54] Sawik, T, Loading and scheculing of a flexible assembly system by mixed integer programming, European Journal of Operational Research, 154, 1-19, (2004) · Zbl 0176.13301
[55] Scholl, A. (1999). Balancing and sequencing assembly lines, 2nd edn. Physica, Heidelberg. · Zbl 0949.90034
[56] Scholl, A; Boysen, N; Fliedner, M, The sequence-dependent assembly line balancing problem, OR Spectrum, 30, 579-609, (2008) · Zbl 1193.90235
[57] 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. · Zbl 1260.90098
[58] Smith, B; Rossi, F (ed.); Beek, P (ed.); Walsh, T (ed.), Modelling, 377-406, (2006), Amsterdam
[59] Valle, CD; Marquez, AA; Gasca, RM; Toro, M, On selecting and scheduling assembly plans using constraint programming, Lecture notes in computer science, 2003, 1329-1336, (2003)
[60] Wilhelm, WE, A column-generation approach for the assembly system design problem with tool changes, International Journal of Flexible Manufacturing Systems, 11, 177-205, (1999)
[61] Yavuz, M; Akcali, E, Production smoothing in just-in-time manufacturing systems: a review of the models and solution approaches, International Journal of Production Research, 45, 3579-3597, (2007) · Zbl 1160.90464
[62] Zeballos, LJ; Quiroga, OD; Henning, GP, A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations, Engineering Applications of Artificial Intelligence, 23, 229-248, (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.