MULTI-OBJECTIVE ROUTING AND SCHEDULING IN FLEXIBLE MANUFACTURING SYSTEMS UNDER UNCERTAINTY

Document Type: Research Paper

Authors

Department of Industrial Engineering, South-Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

The efficiency of transportation system management plays an important role in the planning and operation efficiency of flexible manufacturing systems. Automated Guided Vehicles (AGV) are part of diversified and advanced techniques in the field of material transportation which have many applications today and act as an intermediary between operating and storage equipment and are routed and controlled by an intelligent computer system. In this study, a two-objective mathematical programming model is presented to integrate flow shop scheduling and routing AVGs in a flexible manufacturing system. In real-life problems parameters like demand, due dates and processing times are always uncertain. Therefore, in order to solve a realistic problem, foregoing parameters are considered as fuzzy in our proposed model. Subsequently, to solve fuzzy mathematical programming model, one of the most effective technique in the literature is used. To solve the problem studied, two meta-heuristic algorithms of Non-dominated Sorting Genetic Algorithm-II (NSGAII) and multi-objective particle swarm optimization (MOPSO) are offered that the accuracy of mathematical models and efficiency of algorithms provided are assessed through numerical examples.

Keywords


[1] A. Asef-Vaziri, N. G. Hall and R. George, The signi cance of deterministic empty vehicle
trips in the design of a unidirectional loop
ow path, Computers & Operations Research,
35(5) (2008), 1546-1561.
[2] W. X. Bing, The application of analytic process of resource in an AGV scheduling, Computers
& industrial engineering, 35(1) (1998), 169-172.
[3] J. Blazewicz, R. E. Burkard, G. Finke and G. J. Woeginger, Vehicle scheduling in two-cycle

exible manufacturing systems, Mathematical and computer modelling, 20(2) (1994), 19-31.
[4] I. A. Chaudhry, S. Mahmood and M. Shami, Simultaneous scheduling of machines and au-
tomated guided vehicles in
exible manufacturing systems using genetic algorithms, Journal
of Central South University of Technology, 18(5) (2011), 1473-1486.
[5] C. A. C. Coello, G. T. Pulido and M. S. Lechuga, Handling multiple objectives with particle
swarm optimization, Evolutionary Computation, IEEE Transactions on, 8(3) (2004), 256-
279.
[6] A. I. Correa, A. Langevin and L. M. Rousseau, Scheduling and routing of automated guided
vehicles: A hybrid approach, Computers & operations research, 34(6) (2007), 1688-1707.
[7] K. Deb, Multi-objective optimization using evolutionary algorithms, John Wiley & Sons, 16
(2001).
[8] M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle
routing problem with time windows, Operations research, 40(2) (1992), 342-354.
[9] G. Desaulniers, A. Langevin, D. Riopel and B. Villeneuve, Dispatching and con
ict-free
routing of automated guided vehicles: An exact approach, International Journal of Flexible
Manufacturing Systems, 15(4) (2003), 309-331.
[10] M. E. Dogan and I. E. Grossmann, A decomposition method for the simultaneous planning
and scheduling of single-stage continuous multiproduct plants, Industrial & engineering chemistry
research, 45(1) (2006), 299-315.
[11] I. G. Drobouchevitch and V. A.Strusevich, Heuristics for the two-stage job shop scheduling
problem with a bottleneck machine, European journal of operational research,123(2) (2000),
229-240.
[12] G. El Khayat, A. Langevin and D. Riopel, Integrated production and material handling
scheduling using mathematical programming and constraint programming, European Journal
of Operational Research, 175(3) (2006), 1818-1832.
[13] H. Fazlollahtabar, B. Rezaie, and H. Kalantari, Mathematical programming approach to op-
timize material
ow in an AGV-based
exible jobshop manufacturing system with perfor-
mance analysis, The International Journal of Advanced Manufacturing Technology, 51(9-12)
(2010), 1149-1158.
[14] H. Fazlollahtabar and M. Saidi-Mehrabad, Methodologies to optimize automated guided ve-
hicle scheduling and routing problems: a review study, Journal of Intelligent & Robotic
Systems,77(3-4) (2013), 525-545.

[15] H. Fazlollahtabar, M. Saidi-Mehrabad and J. Balakrishnan, Mathematical optimization for
earliness/tardiness minimization in a multiple automated guided vehicle manufacturing sys-
tem via integrated heuristic algorithms, Robotics and Autonomous Systems, 2015.
[16] M. L. Fisher, K. O. ornsten and O. B. Madsen, Vehicle routing with time windows: Two
optimization algorithms, Operations Research, 45(3) (1997), 488-492.
[17] N. Gans and G. Van Ryzin, Dynamic vehicle dispatching: Optimal heavy trac performance
and practical insights, Operations Research, 47(5) (1999), 675-692.
[18] M. Gen, R. Cheng, and L. Lin, Advanced planning and scheduling models, Network Models
and Optimization: Multiobjective Genetic Algorithm Approach, (2008), 297-417.
[19] H. H. Gotting, Automation and Steering of Vehicles in ports, Port Technology International,
10 (2000), 101-111.
[20] A. L. Gui rida and R. Nagi, Fuzzy set theory applications in production management re-
search: a literature survey, J. Intell. Manuf., 9 (1998), 39-56.
[21] R. Hamana, M. Konishi and J. Imai, Simultaneous optimization of production and transporta-
tion planning by using logic cut algorithm, Memoirs of the Faculty of Engineering, Okayama
University, 41(1) (2007), 31-43.
[22] M. Hamzeei, R. Z. Farahani and H. Rashidi-Bejgan, An exact and a simulated annealing
algorithm for simultaneously determining
ow path and the location of P/D stations in bidi-
rectional path, Journal of Manufacturing Systems, 32(4) (2013), 648-654.
[23] S. Hartmann, A general framework for scheduling equipment and manpower at container
terminals, Springer Berlin Heidelberg, (2005), 207-230.
[24] C. F. Hsueh, A simulation study of a bi-directional load-exchangeable automated guided ve-
hicle system, Computers & Industrial Engineering, 58(4) (2010), 594-601.
[25] O. R. Ilic, Analysis of the number of automated guided vehicles required in
exible manu-
facturing systems, The International Journal of Advanced Manufacturing Technology, 9(6)
(1994), 382-389.
[26] N. Jawahar, P. Aravindan, S. G. Ponnambalam and R. K Suresh, AGV schedule integrated
with production in
exible manufacturing systems,The International Journal of Advanced
Manufacturing Technology, 14(6) (1998), 428-440.
[27] J. Jerald, P. Asokan, R. Saravanan and A. D. C. Rani, Simultaneous scheduling of parts and
automated guided vehicles in an FMS environment using adaptive genetic algorithm, The
International Journal of Advanced Manufacturing Technology, 29(5-6) (2006), 584-589.
[28] M. Jimenez, M. Arenas, A. Bilbao and M. V. Rodriguez, Linear programming with fuzzy
parameters: an interactive method resolution, European Journal of Operational Research,
177 (2007), 1599-1609.
[29] N. Kohl, J. Desrosiers, O. B. Madsen, M. M. Solomon and F. Soumis, 2-path cuts for the
vehicle routing problem with time windows, Transportation Science, 33(1) (1999), 101-116.
[30] P. Lacomme, A. Moukrim and N. Tchernev, Rsolution conjointe de problmes dordon-
nancement et de la gestion du chariot loguid: couplage Branch and Bound-simulation a
evenements discrets, Congres ROADEF, (2000), 128-129.
[31] A. Langevin, D. Lauzon and D. Riopel, Dispatching, routing, and scheduling of two auto-
mated guided vehicles in a
exible manufacturing system, International Journal of Flexible
Manufacturing Systems, 8(3) (1996), 247-262.
[32] T. E. Liang, Application of interactive possibilistic linear programming to aggregate pro-
duction planning with multiple imprecise objectives, Production Planning & Control, 18(7)
(2007), 548-560.
[33] W. A. Lodwick and K. D. Jamison, Theoretical and semantic distinctions of fuzzy, possi-
bilistic, and mixed fuzzy/possibilistic optimization, Fuzzy Sets and Systems, 158(17) (2007),
1861-1872.
[34] F. Mahmoodi, C. T. Mosier and J. R. Morgan, The e ects of scheduling rules and rout-
ing
exibility on the performance of a random
exible manufacturing system, International
journal of
exible manufacturing systems, 11(3) (1999), 271-289.
[35] P. J. M. Meersmans, Optimization of container handling systems, Erasmus School of Economics
(ESE)., 2002.

[36] P. J. Meersmans and A. P. Wagelmans, E ective algorithms for integrated scheduling of
handling equipment at automated container terminals, 2001.
[37] C. Moon and Y. Seo, Evolutionary algorithm for advanced process planning and scheduling
in a multi-plant, Computers & Industrial Engineering,48(2) (2005), 311-325.
[38] C. Moon, Y. Seo, Y. Yun and M. Gen, Adaptive genetic algorithm for advanced planning in
manufacturing supply chain, Journal of Intelligent Manufacturing, 17(4) (2006), 509-522.
[39] T. Muller, Automated Guided Vehicles, IFS (Publications) Ltd./Springer-Verlag, UK/Berlin,
1983.
[40] M. Nageswararao, K. N. Rao and G. Rangajanardhana, Integration of strategic tactical and
operational level planning of scheduling in FMS by metaheuristic algorithm, International
Journal of Advanced Engineering Research and Studies, I (II), 2012.
[41] T. Nishi, Y. Hiranaka and I. E. Grossmann, A bilevel decomposition algorithm for simultane-
ous production scheduling and con
ict-free routing for automated guided vehicles, Computers
& Operations Research, 38(5) (2011), 876-888.
[42] M. A. Parra, A. B. Terol, B. P. Gladish and M. V. Rodriguez Uria, Solving a multiobjective
possibilistic problem through compromise programming, European Journal of Operational
Research, 164 (2005), 748-759.
[43] M. L. Pinedo, Scheduling: theory, algorithms, and systems, Springer Science & Business
Media.
[44] M. S. Pishvaee and S. A. Torabi, A possibilistic programming approach for closed-loop supply
chain network design under uncertainty, Fuzzy Sets and Systems, 161 (2010), 26682683.
[45] L. Qiu and W. J. Hsu, A bi-directional path layout for con
ict-free routing of AGVs, International
Journal of Production Research, 39(10) (2001), 2177-2195.
[46] S. Rajotia, K. Shanker and J. L. Batra, A semi-dynamic time window constrained routeing
strategy in an AGV system, International Journal of Production Research, 36(1) (1998a),
35-50.
[47] S. Rajotia, K. Shanker and J. L. Batra, Determination of optimal AGV
eet size for an
FMS, International Journal of Production Research, 36(5) (1998b), 1177-1198.
[48] H. Rashidi and E. P. Tsang, A complete and an incomplete algorithm for automated guided
vehicle scheduling in container terminals, Computers & Mathematics with Applications,
61(3) (2011), 630-641.
[49] M. Saidi-Mehrabad, S. Dehnavi-Arani, F. Evazabadian and V. Mahmoodian, An Ant Colony
Algorithm (ACA) for solving the new integrated model of job shop scheduling and con
ict-free
routing of AGVs, Computers & Industrial Engineering, 2015.
[50] A. Salehipour, H. Kazemipoor and L. M. Naeini, Locating workstations in tandem automated
guided vehicle systems, The International Journal of Advanced Manufacturing Technology,
52(1-4) (2011), 321-328.
[51] A. J. Sanchez-Salmeron, R. Lopez-Tarazon, R. Guzman-Diana and C. Ricolfe-Viala, An inter-
machine material handling system for micro-manufacturing based on using a standard car-
rier, The International Journal of Advanced Manufacturing Technology, 47(9-12) (2010),
937-943.
[52] B. R. Sarker and S. S. Gurav, Route planning for automated guided vehicles in a manufac-
turing facility, International journal of production research, 43(21) (2005), 4659-4683.
[53] M. Savelsbergh and M. Sol, DRIVE: Dynamic routing of independent vehicles, Operations
Research, 46(4) (1998), 474-490.
[54] D. Sinriech and L. Palni, Scheduling pickup and deliveries in a multiple-load discrete carrier
environment, IIE transactions, 30(11) (1998), 1035-1047.
[55] D. Sinriech and J. Kotlarski, A dynamic scheduling algorithm for a multiple-load multiple-
carrier system, International Journal of Production Research, 40(5) (2002), 1065-1080.
[56] D. Spensieri, J. S. Carlson, F. Ekstedt, and R. Bohlin, An iterative approach for collision
free routing and scheduling in multirobot stations, IEEE Transactions on Automation Science
and Engineering, 13(2) (2016), 950-962.
[57] G. Taguchi, System of experimental design; engineering methods to optimize quality and
minimize costs, No. 04; QA279, T3, (1987).

[58] E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational
Research, 64(2) (1993), 278-285.
[59] J. A.Tompkins, J. A. White, Y. A. Bozer, and J. M. A. Tanchoco, Facilities planning, John
Wiley & Sons, 2010.
[60] Y. Tanaka, T. Nishi and M. Inuiguchi, Dynamic optimization of simultaneous dispatching
and con
ict-free routing for automated guided vehicles-Petri net decomposition approach,
Journal of Advanced Mechanical Design, Systems, and Manufacturing, 4(3) (2010), 701-715.
[61] P. Udhayakumar and S. Kumanan, Task scheduling of AGV in FMS using non-traditional
optimization techniques, International Journal of Simulation Modelling, 9(1) (2010), 28-39.
[62] G. Ulusoy, F. Sivrikaya-Serifo^glu and Bilge, U. A genetic algorithm approach to the simul-
taneous scheduling of machines and automated guided vehicles, Computers & Operations
Research, 24(4) (1997), 335-351.
[63] B. Vahdani, Vehicle positioning in cell manufacturing systems via robust optimization, Applied
Soft Computing, 24 (2014), 78-85.
[64] M. C. Van der Heijden, M. Ebben, N. Gademann, and A. van Harten, Scheduling vehicles in
automated transportation systems Algorithms and case study, OR spectrum,24(1) (2002a),
31-58.
[65] M. C. Van der Heijden, A. Van Harten, M. J. R. Ebben, Y. A. Saanen, E. C. Valentin, and
A. Verbraeck, Using simulation to design an automated underground system for transporting
freight around Schiphol Airport, Interfaces, 32(4) (2002b), 1-19.
[66] B. Veeravalli, G. Rajesh and N. Viswanadham, Design and analysis of optimal material
distribution policies in
exible manufacturing systems using a single AGV, International
journal of production research, 40(12) (2002), 2937-2954.
[67] I. F. Vis and I. Harika, Comparison of vehicle types at an automated container terminal, OR
Spectrum, 26(1) (2004), 117-143.
[68] I. F. Vis, Survey of research in the design and control of automated guided vehicle systems,
European Journal of Operational Research, 170(3) (2006), 677-709.
[69] K. Vivaldini, L. F. Rocha, N. J. Martarelli, M. Becker and A. P. Moreira, Integrated tasks
assignment and routing for the estimation of the optimal number of AGVS, The International
Journal of Advanced Manufacturing Technology, 82(1-4) (2016), 719-736.
[70] N. Wu, and M. Zhou, Modeling and deadlock control of automated guided vehicle systems,
Mechatronics, IEEE/ASME Transactions on,9(1) (2004), 50-57.
[71] C. H. Yang, Y. S. Choi and T. Y. Ha, Simulation-based performance evaluation of transport
vehicles at automated container terminals, Or Spectrum,26(2) (2004), 149-170.
[72] J. W. Yoo, E. S. Sim, C. Cao and J. W. Park, An algorithm for deadlock avoidance in an
AGV System, The International Journal of Advanced Manufacturing Technology, 26(5-6)
(2005), 659-668.
[73] M. B. ZA Remba, A. Obuchowicz, Z. A. Banaszak and K. J. Jed Rzejek, A max-algebra
approach to the robust distributed control of repetitive AGV systems, International journal
of production research, 35(10) (1997), 2667-2688.