×

Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints. (English) Zbl 1403.90287

Summary: Assembly line balancing problems (ALBPs) are among the most studied combinatorial optimization problems due to their relevance in many production systems. In particular, the accessibility windows ALBP (AWALBP) may arise when the workpieces are larger than the workstations, which implies that at a given instant the workstations have access to only a portion of the workpieces. Thus, the cycle is split into forward steps and stationary stages. The workpieces advance during the forward steps and the tasks are processed during the stationary stages. Several studies have dealt with the AWALBP assuming that there are no precedence relationships between tasks. However, this assumption is not always appropriate. In this work, we solve the first level of AWALBP (AWALBP-L1) considering the existence of precedence relationships. Specifically, this work deals with variant 1 (AWALBP-L1-1), in which each task can be performed at only one workstation and, therefore, only the stationary stages and the starting instants in which the tasks are performed have to be decided. We design a solution procedure that includes pre-processing procedures, a matheuristic and a mixed integer linear programming model. An extensive computational experiment is carried out to evaluate its performance.

MSC:

90B30 Production models
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdullah Make, M. R.; Ab. Rashid, M. F.F.; Razali, M. M., A review of two-sided assembly line balancing problem, International Journal of Advanced Manufacturing Technology, 89, 1743-1763, (2017)
[2] Adenso-Díaz, B.; Laguna, M., Fine-tuning of algorithms using fractional experimental designs and local search, Operations Research, 54, 99-114, (2006) · Zbl 1167.90654
[3] Akpinar, S.; Elmi, A.; Bektaş, T., Combinatorial benders cuts for assembly line balancing problems with setups, European Journal of Operational Research, 259, 527-537, (2017) · Zbl 1394.90246
[4] Battaïa, O.; Dolgui, A., A taxonomy of line balancing problems and their solution approaches, International Journal of Production Economics, 142, 259-277, (2013)
[5] Bautista, J.; Pereira, J., Procedures for the time and space constrained assembly line balancing problem, European Journal of Operational Research, 212, 473-481, (2011) · Zbl 1237.90082
[6] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management Science, 32, 909-932, (1986) · Zbl 0601.90081
[7] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, European Journal of Operational Research, 168, 694-715, (2006) · Zbl 1083.90013
[8] Bentaha, M. L.; Battaïa, O.; Dolgui, A.; Hu, S. J., Second order conic approximation for disassembly line design with joint probabilistic constraints, European Journal of Operational Research, 247, 957-967, (2015) · Zbl 1346.90298
[9] Borba, L.; Ritt, M.; Miralles, C., Exact and heuristic methods for solving the robotic assembly line balancing problem, European Journal of Operational Research, (2018) · Zbl 1403.90652
[10] Bowman, E. H., Assembly-line balancing by linear programming, Operations Research, 8, 385-389, (1960) · Zbl 0093.32805
[11] Boysen, N.; Fliedner, M.; Scholl, A., A classification of assembly line balancing problems, European Journal of Operational Research, 183, 674-693, (2007) · Zbl 1179.90103
[12] Boysen, N.; Fliedner, M.; Scholl, A., Assembly line balancing: which model to use when, International Journal of Production Economics, 111, 509-528, (2008)
[13] Calleja, G.; Corominas, A.; García-Villoria, A.; Pastor, R., A MILP model for the accessibility windows assembly line balancing problem (AWALBP), International Journal of Production Research, 51, 3549-3560, (2013)
[14] Calleja, G.; Corominas, A.; García-Villoria, A.; Pastor, R., Combining matheuristics and MILP to solve the accessibility windows assembly line balancing problem level 2 (AWALBP-L2), Computers & Operations Research, 48, 113-123, (2014) · Zbl 1348.90221
[15] Calleja, G.; Corominas, A.; García-Villoria, A.; Pastor, R., Hybrid metaheuristics for the accessibility windows assembly line balancing problem level 2 (AWALBP-L2), European Journal of Operational Research, 250, 760-772, (2016) · Zbl 1346.90300
[16] Capacho, L.; Pastor, R.; Dolgui, A.; Gunshinskaya, O., An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem, Journal of Heuristics, 15, 109-132, (2009) · Zbl 1172.90377
[17] Fathi, M.; Álvarez, M. J.; Rodríguez, V., A new heuristic-based bi-objective simulated annealing method for U-shaped assembly line balancing, European Journal of Industrial Engineering, 10, 145-169, (2017)
[18] Fleszar, K., A new MILP model for the accessibility windows assembly line balancing problem level 2 (AWALBP-L2), European Journal of Operational Research, 259, 169-174, (2017) · Zbl 1394.90248
[19] García-Villoria, A.; Corominas, A.; Pastor, R., Pure and hybrid metaheuristics for the response time variability problem, (Vasant, P., Meta-heuristics optimization algorithms in engineering, business, economics, and finance, (2012), IGI Global), Chapter 10
[20] García-Villoria, A.; Corominas, A.; Pastor, R., Heuristics and simulated annealing procedures for the accessibility windows assembly line balancing problem level 1 (AWALBP-L1), Computers & Operations Research, 62, 1-11, (2015) · Zbl 1348.90223
[21] Gaudlitz, R., Optimization algorithms for complex mounting machines in PC board manufacturing, (2004), Technical University of Darmstadt Germany, Diploma thesis
[22] Koltai, T.; Kalló, N., Analysis of the effect of learning on the throughput-time in simple assembly lines, Computers and Industrial Engineering, 111, 507-515, (2017)
[23] Krishnan, K. K.; Almaktoom, A. T.; Udayakumar, P., Optimisation of stochastic assembly line for balancing under high variability, International Journal of Industrial and Systems Engineering, 22, 440-465, (2016)
[24] Martin, R., Modeling an optimization problem from the automated manufacting of PC boards, (2002), Universität Konstanz Germany, Diploma thesis
[25] Moreira, M. C.O.; Cordeau, J-F.; Costa, A. M.; Laporte, G., Robust assembly line balancing with heterogeneous workers, Computers & Industrial Engineering, 88, 254-263, (2015)
[26] Morrison, D. R.; Sewell, E. C.; Jacobson, S. H., An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset, European Journal of Operational Research, 236, 403-409, (2014) · Zbl 1317.90258
[27] Müller-Hannemann, M.; Weihe, K., Moving policies in cyclic assembly-line scheduling, Theoretical Computer Science, 351, 425-436, (2006) · Zbl 1086.90026
[28] Nikolaev, A. G.; Jacobson, S. H., Simulated annealing, (Gendreau; Potvin, Handbook of metaheuristics, (2010), Springer New York), 1-39, Chapter 1
[29] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop problem, Management of Science, 42, 797-813, (1996) · Zbl 0880.90079
[30] Otto, A.; Battaïa, O., Reducing physical ergonomic risks at assembly lines by line balancing and job rotation: a survey, Computers and Industrial Engineering, 111, 467-480, (2017)
[31] Quyen, N. T.P.; Chen, J. C.; Yang, C.-L., Hybrid genetic algorithm to solve resource constrained assembly line balancing problem in footwear manufacturing, Soft Computing, 21, 6279-6295, (2017)
[32] Ritt, M.; Costa, A. M., Improved integer programming models for simple assembly line balancing and related problems, International Transactions in Operational Research, 25, 1345-1359, (2015) · Zbl 1395.90188
[33] Roy, B.; Saussmann, B., LES problèmes d’ordonnancement avec contraintes disjonctives, (Note DS No. 9 bis, SEMA, Paris, (1964))
[34] Scholl, A.; Becker, C., State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, European Journal of Operational Research, 168, 666-693, (2006) · Zbl 1083.90019
[35] Sewell, E. C.; Jacobson, S. H., A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS Journal on Computing, 24, 433-442, (2012) · Zbl 1462.90112
[36] Stille, W., Solution techniques for specific bin packing problems with applications to assembly line optimization, (2008), Technical University of Darmstadt Germany, PhD thesis
[37] Tazari, S., Algorithmic approaches for two fundamental optimization problemsworkload-balancing and planar Steiner trees, (2006), Technical University of Darmstadt Germany, Diploma thesis
[38] Zelter, L.; Aghezzaf, E.-H.; Limère, V., Workload balancing and manufacturing complexity levelling in mixed-model assembly lines, International Journal of Production Research, 55, 2829-2844, (2017)
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.