A Linearization and Decomposition Based Approach to Minimize the Non-Productive Time in Transfer Lines

Authors: Hany Osman, M. F. Baki

Abstract:

We address the balancing problem of transfer lines in this paper to find the optimal line balancing that minimizes the nonproductive time. We focus on the tool change time and face orientation change time both of which influence the makespane. We consider machine capacity limitations and technological constraints associated with the manufacturing process of auto cylinder heads. The problem is represented by a mixed integer programming model that aims at distributing the design features to workstations and sequencing the machining processes at a minimum non-productive time. The proposed model is solved by an algorithm established using linearization schemes and Benders- decomposition approach. The experiments show the efficiency of the algorithm in reaching the exact solution of small and medium problem instances at reasonable time.

Keywords: Transfer line balancing, Benders' decomposition, Linearization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061306

References:

[1] A. Dolgui, N. Guschinsky, and G. Levin, "Optimal Design of Transfer Lines and Multi-Position Machines,"Proceedings of the 7th Mediterranean Conference on Control and Automation (MED99)Haifa, Israel, June 28-30, pp. 1962-1973, 1999.
[2] A. Dolgui, N. Guschinsky, and G. Levin, "On problem of optimal design of transfer lines with parallel and sequential operations,"In J. M. Fuertes (Ed.), Proceedings of the 7th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 99) Barcelona, Spain,vol. 1, pp. 329-334, 1999.
[3] A. Dolgui, N. Guschinsky, N., and G. Levin, "Approaches to balancing of transfer line with block of parallel operations,"Institute of Engineering Cybernetics/University of Technology of Troyes, Minsk, Preprint no. 8, 42 pages, 2000.
[4] A. Dolgui, B. Finel, N. Guschinsky, G. Levin, and F. Vernadat, "MIP approach to balancing transfer lines with blocks of parallel operations," IIE Transactions, vol. 38, pp. 869-882, 2006.
[5] A. Dolgui, B. Finel, F. Venadat, N.Guschinsky, and G. Levin, "A heuristic approach for transfer lines balancing,"Journal of Intelligent Manufacturing, vol. 16, pp. 159-172, 2005.
[6] B.Finel, A. Dolgui, and F. Vernadat, "A random search and backtracking procedure for transfer line balancing,"International Journal of Computer Integrated Manufacturing, Vol. 21, no. 4, pp. 376 - 387, 2008.
[7] O. Guschinskaya andA.Dolgui, "Heuristic methods for a transfer line balancing problem,"Proceedings of the 19th International Conference on Production Research, Valparaiso, Chile, 6 pages, 2007.
[8] O. Guschinskaya and A. Dolgui, "A transfer line balancing problem by heuristic methods: industrial case studies,"Decision Making in Manufacturing and Services, Vol. 2, no. 1, pp. 33-46, 2008.
[9] A. Dolgui, N.Guschinsky, and G. Levin, "A special case of transfer lines balancing by graph approach,"European Journal of Operational Research, Vol. 168, pp. 732-746, 2006.
[10] S. Belmokhtar, A.Dolgui, N. Guschinsky, and G. Levin, "Integer programming models for logical layout design of modular machining lines,"Computers & Industrial Engineering, Vol. 51, pp. 502-518, 2006.
[11] X. Delorme, A. Dolgui, and M.Y. Kovalyov, "Combinatorial design of a minimum cost transfer line,"Omega, vol. 40, pp. 31-41, 2012.
[12] P. Borisovsky, A. Dolgui, and S. Kovalev, "Modelling transfer line design problem via a set partitioning problem,"Optimization Letters, vol. 6, pp. 915-926, 2012.
[13] A. Dolgui, B. Finel, O. Guschinskaya, N. Guschinsky, G. Levin, and F. Vernadat, "Balancing large-scale machining lines with multi-spindle heads using decomposition,"International Journal of Production Research, Vol. 44, no. 18-19, pp. 4105-4120, 2006.
[14] A. Dolguiand I.Ihnatsenka, "Branch and bound algorithm for a transfer line Design problem: stations with sequentially activated multi-spindle heads,"European Journal of Operational Research,vol. 197, no. 3, pp. 1119-1132, 2009.
[15] A. Dolguiand I. Ihnatsenka, "Balancing modular transfer lines with serial-parallel activation of spindle heads at stations,"Discrete Applied Mathematics, vol. 157, pp. 68-89, 2009.
[16] E. Gurevsky, O. Guschinskaya, A.Eremeev, and A. Dolgui, "Balancing machining transfer lines using genetic algorithms,"Proceedings of the 39th IEEE International Conference on Computers & Industrial Engineering, Troyes, France, pp. 1850-1855, 2009.
[17] A. Dolgui, A. Eremeev, and O. Guschinskaya, "MIP-based GRASP and genetic algorithm for balancing transfer lines,"Annals of Information Systems, vol. 10, pp. 189-208, 2010.
[18] A. Dolgui, N. Guschinsky, and G. Levin, "Graph approach for optimal design of transfer machine with rotary table,"International Journal of Production Research, vol. 47, no. 2, pp. 321-341, 2009.
[19] M. Essafi, X. Delorme, X. and A.Dolgui, "Balancing lines with CNC machines: A multi-start ant based heuristic,"CIRP Journal of Manufacturing Science and Technology, vol. 2, pp. 176-182, 2010.
[20] S. Masood, "Line balancing and simulation of an automated production transfer line,"Assembly Automation, vol. 26, no. 1, pp. 69-74, 2006.
[21] K. Das, M.F. Baki, and X. Li, "Optimization of operation and changeover time for production planning and scheduling in a flexible manufacturing system,"Computers & Industrial Engineering, vol. 56, pp. 283-293, 2009.
[22] A.M. Geoffrion, "Generalized Benders-decomposition," Journal of Optimization Theory and Applications,vol. 10, no. 4, pp. 237-260, 1972.
[23] P.M. Hahn, B.J. Kim, M. Guignard, J.M. Smith, and Y.R. Zhu, "An algorithm for the generalized quadratic assignment problem,"Computational Optimization and Applications, vol. 40, no. 3, pp. 351-372, 2008.