×

Bi-criteria assembly line balancing by considering flexible operation times. (English) Zbl 1228.90034

Summary: This paper addresses a novel approach to deal with flexible task time assembly line balancing problem (FTALBP). In this regard, machines are considered in which operation time of each task can be between lower and upper bounds. These machines can compress the processing time of tasks, but this action may lead to higher cost due to cumulative wear, erosion, fatigue and so on. This cost is described in terms of task time via a linear function. Hence, a bi-criteria nonlinear integer programming model is developed which comprises two inconsistent objective functions: minimizing the cycle time and minimizing the machine total costs. In order to sustain these objectives concurrently, this paper applies the LP-metric method to make a combined dimensionless objective. Moreover, a genetic algorithm (GA) is presented to solve this NP-hard problem and design of experiments (DOE) method is hired to tune various parameters of our proposed algorithm. The computational results demonstrate the effectiveness of implemented procedures.

MSC:

90B30 Production models
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boysen, N.; Fliedner, M.; Scholl, A., Assembly line balancing: which model to use when?, Int. J. Prod. Econ., 111, 509-528 (2008)
[2] Boysen, N.; Fliedner, M.; Scholl, A., A classification of assembly line balancing problems, Eur. J. Oper. Res., 183, 674-693 (2007) · Zbl 1179.90103
[3] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, Eur. J. Oper. Res., 168, 694-715 (2006) · Zbl 1083.90013
[4] Kara, Y.; Paksoy, T.; Chang, C. T., Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing, Eur. J. Oper. Res., 195, 335-347 (2009) · Zbl 1175.90356
[5] Ozcan, U.; Toklu, B., Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming models, Comput. Oper. Res., 36, 1955-1965 (2009) · Zbl 1179.90191
[6] Ozcan, U., Balancing stochastic two-sided assembly lines: a chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm, Eur. J. Oper. Res., 205, 81-97 (2010) · Zbl 1187.90120
[7] Toksarı, M. D.; Isleyen, S. K.; Guner, E.; Baykoc, O. F., Assembly line balancing problem with deterioration tasks and learning effect, Expert Syst. Appl., 37, 1223-1228 (2010)
[8] Shahanaghi, K.; Yolmeh, A. M.; Bahalke, U., Scheduling and balancing assembly lines with the task deterioration effect, Proc. Inst. Mech. Eng. B: J. Eng. Manuf., 224, 7, 1145-1153 (2010)
[9] Agpak, K.; Gokcen, H., Assembly line balancing: two resource constrained cases, Int. J. Prod. Econ., 96, 129-140 (2005)
[10] Chen, R. S.; Lu, K. Y.; Yu, S. C., A hybrid genetic algorithm approach on multi-objective of assembly planning problem, Eng. Appl. Artif. Intell., 15, 447-457 (2002)
[11] Scholl, A.; Fliedner, M.; Boysen, N., ABSALOM: balancing assembly lines with assignment restrictions, Eur. J. Oper. Res., 200, 688-701 (2010) · Zbl 1177.90351
[12] Watkins, R.; Cochran, J., A line balancing heuristic case study for existing automated surface mount assembly line setups, Comput. Ind. Eng., 29, 681-685 (1995)
[13] Andres, C.; Miralles, C.; Pastor, R., Balancing and scheduling tasks in assembly lines with sequence-dependent setup times, Eur. J. Oper. Res., 187, 1212-1223 (2008) · Zbl 1137.90476
[14] Toksari, M. D.; İşleyen, S. K.; Güner, E.; Baykoç, Ö. F., Simple and U-type assembly line balancing problems with a learning effect, Appl. Math. Model., 32, 2954-2961 (2008)
[15] Battini, D.; Faccio, M.; Persona, A.; Sgarbossa, F., Balancing-sequencing procedure for a mixed model assembly system in case of finite buffer capacity, Int. J. Adv. Manuf. Technol., 44, 345-359 (2009)
[16] Becker, C.; Scholl, A., Balancing assembly lines with variable parallel workplaces: problem definition and effective solution procedure, Eur. J. Oper. Res., 199, 359-374 (2009) · Zbl 1176.90480
[17] Berger, I.; Bourjolly, J. M.; Laporte, G., Branch-and-bound algorithms for the multi-product assembly line balancing problem, Eur. J. Oper. Res., 58, 215-222 (1992) · Zbl 0757.90029
[18] Boysen, N.; Fliedner, M., A versatile algorithm for assembly line balancing, Eur. J. Oper. Res., 184, 39-56 (2008) · Zbl 1152.90412
[19] Gokcen, H.; Agpak, K.; Benzer, R., Balancing of parallel assembly lines, Int. J. Prod. Econ., 103, 600-609 (2006)
[20] Scholl, A.; Boysen, N.; Fliedner, M., The sequence-dependent assembly line balancing problem, Oper. Res. Spectrum, 30, 579-609 (2008) · Zbl 1193.90235
[21] Amen, M., Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds, Eur. J. Oper. Res., 168, 747-770 (2006) · Zbl 1083.90012
[22] Amen, M., Heuristic methods for cost-oriented assembly line balancing: a comparison on solution quality and computing time, Int. J. Prod. Econ., 69, 255-264 (2001)
[23] Scholl, A.; Becker, C., A note on “An exact method for cost-oriented assembly line balancing”, Int. J. Prod. Econ., 97, 343-352 (2005)
[24] Bock, S., Using distributed search methods for balancing mixed-model assembly lines in the automotive industry, Oper. Res. Spectrum, 30, 551-578 (2008) · Zbl 1193.90226
[25] Levitin, G.; Rubinovitz, J.; Shnits, B., A genetic algorithm for robotic assembly line balancing, Eur. J. Oper. Res., 168, 811-825 (2006) · Zbl 1083.90018
[26] Bautista, J.; Cano, J., Minimizing work overload in mixed-model assembly lines, Int. J. Prod. Econ., 112, 177-191 (2008)
[27] Kim, Y. J.; Kim, Y. K.; Cho, Y., A heuristic-based genetic algorithm for workload smoothing in assembly lines, Comput. Oper. Res., 25, 99-111 (1997) · Zbl 0906.90083
[28] Bukchin, Y.; Rabinowitch, I., A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs, Eur. J. Oper. Res., 174, 492-508 (2006) · Zbl 1116.90035
[29] Tasan, S. O.; Tunali, S., A review of the current applications of genetic algorithms in assembly line balancing, J. Intell. Manuf., 19, 49-69 (2008)
[30] Scholl, A.; Klein, R., SALOME: a bidirectional branch and bound procedure for assembly line balancing, INFORMS J. Comput., 9, 319-334 (1997) · Zbl 0895.90121
[31] Scholl, A.; Klein, R., Balancing assembly lines effectively – a computational comparison, Eur. J. Oper. Res., 114, 50-58 (1999) · Zbl 0949.90034
[32] Miralles, C.; Garcia Sabater, J.; Andres, C.; Cardos, M., Branch and bound procedures for solving the assembly line worker assignment and balancing problem: application to sheltered work centres for disabled, Discrete Appl. Math., 156, 352-367 (2008) · Zbl 1157.90396
[33] Nicosia, G.; Pacciarelli, D.; Pacifici, A., Optimally balancing assembly lines with different workstations, Discrete Appl. Math., 118, 99-113 (2002) · Zbl 0995.90082
[34] Kim, Y. K.; Song, W. S.; Kim, J. H., A mathematical model and a genetic algorithm for two-sided assembly line balancing, Comput. Oper. Res., 36, 853-865 (2009) · Zbl 1157.90390
[35] Simaria, A. S.; Vilarinho, P. M., 2-ANTBAL: an ant colony optimization algorithm for balancing two-sided assembly lines, Comput. Ind. Eng., 56, 489-506 (2009) · Zbl 1095.90100
[36] Lapierre, S.; Ruiz, A.; Soriano, P., Balancing assembly lines with tabu search, Eur. J. Oper. Res., 168, 826-837 (2006) · Zbl 1083.90017
[37] Kilincci, O., A Petri net-based heuristic for simple assembly line balancing problem of type 2, Int. J. Adv. Manuf. Technol., 46, 329-338 (2010)
[38] Aryanezhad, M. B.; Kheirkhah, A. S.; Deljoo, V.; Mirzapour Al-e-hashem, S. M.J., Designing safe job rotation schedules based upon workers’ skills, Int. J. Adv. Manuf. Technol., 41, 193-199 (2009)
[39] M.B. Aryanezhad, A. Jabbarzadeh, A. Zareei, Combination of genetic algorithm and LP-metric to solve single machine bi-criteria scheduling problem, in: Proceedings of the 2009 IEEE IEEM, Hong Kong 2009, pp. 1915-1919.; M.B. Aryanezhad, A. Jabbarzadeh, A. Zareei, Combination of genetic algorithm and LP-metric to solve single machine bi-criteria scheduling problem, in: Proceedings of the 2009 IEEE IEEM, Hong Kong 2009, pp. 1915-1919.
[40] Mahdavi Mazdeh, M.; Zaerpour, F.; Zareei, A.; Hajinezhad, A., Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs, Appl. Math. Model., 34, 1498-1510 (2010) · Zbl 1193.90105
[41] Gutjahr, A. L.; Nemhauser, G. L., An algorithm for the line balancing problem, Manage. Sci., 11, 308-315 (1964) · Zbl 0137.39303
[42] Sivanandam, S. N.; Deepa, S. N., Introduction to Genetic Algorithms (2008), Springer: Springer New York · Zbl 1129.90001
[43] Zhou, H.; Cheung, W.; Leung, L. C., Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm, Eur. J. Oper. Res., 194, 637-649 (2009) · Zbl 1163.90004
[44] Nearchou, A. C., The effect of various operators on the genetic search for large scheduling problems, Int. J. Prod. Econ., 88, 191-203 (2004)
[45] Vallada, E.; Ruiz, R., Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem, Omega, 38, 57-67 (2010)
[46] Ruiz, R.; Maroto, C.; Alcaraz, J., Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, Eur. J. Oper. Res., 165, 34-54 (2005) · Zbl 1112.90338
[47] Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 461-476 (2006)
[48] Bahalke, U.; Yolmeh, A. M.; Shahanaghi, K., Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs, Int. J. Adv. Manuf. Technol., 50, 749-759 (2010)
[49] Seyed-Alagheband, S. A.; Fatemi Ghomi, S. M.T.; Zandieh, M., A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks, Int. J. Prod. Res., 49, 3, 805-825 (2011)
[50] Keuls, M., The use of the studentized range in connection with an analysis of variance, Euphytica, 1, 112-122 (1952)
[51] Nearchou, A. C., Balancing large assembly lines by a new heuristic based on differential evolution method, Int. J. Adv. Manuf. Technol., 34, 1016-1029 (2007)
[52] Roshanaei, V.; Naderi, B.; Jolai, F.; Khalili, M., A variable neighborhood search for job shop scheduling with set-up times to minimize makespan, Future Gen. Comput. Syst., 25, 654-661 (2009)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.