A Linearization and Decomposition Based Approach to Minimize the Non-Productive Time in Transfer Lines
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:54668", author = "Hany Osman and M. F. Baki", title = "A Linearization and Decomposition Based Approach to Minimize the Non-Productive Time in Transfer Lines", 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.", volume = "7", number = "2", pages = "222-6", }
