Simultaneous scheduling of machines and automated guided vehicles in flexible manufacturing systems using genetic algorithms

Abstract

The problem of simultaneous scheduling of machines and vehicles in flexible manufacturing system (FMS) was addressed. A spreadsheet based genetic algorithm (GA) approach was presented to solve the problem. A domain independent general purpose GA was used, which was an add-in to the spreadsheet software. An adaptation of the propritary GA software was demonstrated to the problem of minimizing the total completion time or makespan for simultaneous scheduling of machines and vehicles in flexible manufacturing systems. Computational results are presented for a benchmark with 82 test problems, which have been constructed by other researchers. The achieved results are comparable to the previous approaches. The proposed approach can be also applied to other problems or objective functions without changing the GA routine or the spreadsheet model.

Keywords

automated guided vehicles (AGVs) / scheduling / job-shop / genetic algorithms / flexible manufacturing system (FMS) / spreadsheet

References

[1] van Dyke ParunakH.. Characterizing the manufacturing scheduling problem [J]. Journal of Manufacturing Systems, 1992, 10(3): 241-259

[2] BrittD.. Managing temporal relations in MAESTRO scheduling system [C]. Proceedings of Space Network Control Conference on Resource Allocation Concepts and Approaches, 1992, Greenbelt, MD, NASA Goddard: 233-240

[3] GrooverM. P.Automation, production systems and computer integrated manufacturing [M], 1987, New York, Prentice-Hall

[4] BuzzacottJ. A., YaoD. D.. Flexible manufacturing systems: A review of analytical models [J]. Management Science, 1986, 32: 890-905

[5] GunaserkaranA., MartikainenT., Yli-oliP.. Flexible manufacturing systems: An investigation for research and applications [J]. European Journal of Operations Research, 1993, 66: 1-26

[6] KusiakA.. Application of operational research models and techniques in flexible manufacturing systems [J]. European Journal of Operations Research, 1986, 24: 336-345

[7] LiuJ., MaccarthyB. L.. The classification of FMS scheduling problems [J]. International Journal of Production Research, 1996, 34: 647-656

[8] MaccarthyB. L., LiuJ.. A new classification scheme for flexible manufacturing systems [J]. International Journal of Production Research, 1993, 31: 299-309

[9] SteckeK.. Planning and scheduling approaches to operate a particular FMS [J]. European Journal of Operations Research, 1992, 61(3): 273-291

[10] RamanN., TalbotF. B., RachamadguR. V., SteckeK. E., SuriR.. Simultaneous scheduling of machines and material handling devices in automated manufacturing [C]. Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, 1986, Ann Arbor, MI, USA, University of Michigan: 455-466

[11] UlusoyG., BilgeU.. Simultaneous scheduling of machines and automated guided vehicles [J]. International Journal of Production Research, 1993, 31(12): 2857-2873

[12] BilgeU., UlusoyG.. A time window approach to simultaneous scheduling of machines and material handling system in FMS [J]. Operations Research, 1995, 43: 1058-1070

[13] UlusoyG., Sivrikaya-SerifogluF., BilgeU.. A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles [J]. Computers & Industrial Engineering, 1997, 24(4): 335-351

[14] AbdelmaguidT. F., NassefO. N., KamalB. A., HassanM. F.. A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles [J]. International Journal of Production Research, 2004, 42: 267-281

[15] MURAYAMA N. KAWATA S. An evolutional computing approach to the simultaneous scheduling of machines and automated guided vehicles [J]. Jido Seigyo Rengo Koenkai Koen Ronbunshu, 2004, 47. (in Japanese)

[16] MurayamaN., KawataS.. A genetic algorithm approach to simultaneous scheduling of processing machines and multiple-load automated guided vehicles [J]. Transactions of the Japan Society of Mechanical Engineers C, 2005, 71(712): 3638-3643

[17] MurayamaN., KawataS.. Job-shop scheduling considering material handling by multiple-load AGVs [R]. The Institute of Electronics, Information and Communication Engineers, IEICE Tech. Report, 2005, 105(159): 17-21

[18] JeraldJ., AsokanP., SaravananR., RaniA. D. C.. Simultaneous scheduling of parts and AGVs in an FMS using non-traditional optimization algorithms [J]. International Journal of Applied Management and Technology, 2005, 3(1): 305-315

[19] JeraldJ., AsokanP., SaravananR., RaniA. D. C.. Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithms [J]. International Journal of Advanced Manufacturing Technology, 2006, 59: 584-589

[20] JeraldJ., AsokanP., PrabhaharanG., SaravananR.. Scheduling of parts and AS/RS in FMS using genetic algorithm [J]. International Journal of Applied Management and Technology, 2006, 4(1): 25-34

[21] MURAYAMA N, KAWATA S. Simulated annealing method for simultaneous scheduling of machines and multiple-load AGVs [C]// IJCC Workshop on Digital Engineering. Pyeongchang-gun, Gangwon-do, South Korea, 2006: 55–62. (in Japanese)

[22] ReddyB. S. P., RaoC. S. P.. A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS [J]. International Journal of Advanced Manufacturing Technology, 2006, 31(5/6): 602-613

[23] DeroussiL., GourgandM., TchernevN.. A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles [J]. International Journal of Production Research, 2008, 46(8): 2143-2164

[24] SteckeK. E.. Design, planning, scheduling, and control problems of flexible manufacturing systems [J]. Annals of Operations Research, 1985, 3(1): 3-12

[25] GoldbergD. E.Genetic algorithms in search, optimization and machine learning [M], 1989, New York, Addison-Wesley Publishing Company

[26] DavisL.. Job shop scheduling with genetic algorithms [C]. Proceedings of the 1st International Conference on Genetic Algorithms, 1985, Hillsdale, NJ, Lawrence Erlbaum: 136-140

[27] ChaudhryI. A.. Minimizing flow time for the worker assignment problem in identical parallel machine models using GA [J]. International Journal of Advanced Manufacturing Technology, 2009, 48(5/6/7/8): 747-760

[28] ChaudhryI. A., DrakeP. R.. Minimizing flow time variance in a single machine system using genetic algorithms [J]. International Journal of Advanced Manufacturing Technology, 2008, 39: 355-366

[29] ChaudhryI. A., DrakeP. R.. Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms [J]. International Journal of Advanced Manufacturing Technology, 2009, 42: 581-594

[30] Evolver user’s guide [M]. New York: Palisade Corp, 1998.

[31] HeD., GrigoryanA.. Construction of double sampling s-control charts for agile manufacturing [J]. Quality and Reliability Engineering International, 2002, 18: 43-55

[32] BarkhiR., RollandE., ButlerJ., FanW.. Decision support system induced guidance for model formulation and solution [J]. Decision Support Systems, 2005, 40(2): 269-281

[33] OstfeldA., MuzaffarE., LanseyK.. HANDSS: The hula aggregated numerical decision support system [J]. Journal of Geographic Information and Decision Analysis, 2001, 5(1): 16-31

[34] HegazyT., KassabM.. Resource optimization using combined simulation and genetic algorithms [J]. Journal of Construction Engineering and Management, 2003, 129(6): 698-705

[35] SarangaH., KumarU. D.. Optimization of aircraft maintenance/support infrastructure using genetic algorithms-level of repair analysis [J]. Annals of Operations Research, 2006, 143: 91-106

[36] ShumY.-S., GongD.-C.. The application of genetic algorithm in the development of preventive maintenance analytic model [J]. International Journal of Advanced Manufacturing Technology, 2007, 32: 169-183

[37] HayatN., WirthA.. Genetic algorithms and machine scheduling with class setups [J]. International Journal of Computer and Engineering Management, 1997, 5(2): 10-23

[38] HegazyT., ErsahinT.. Simplified spreadsheet solutions: II. Overall schedule optimization [J]. Journal of Construction Engineering and Management, 2001, 127(6): 469-475

[39] JeongS. J., LimS. J., KimK. S.. Hybrid approach to production scheduling using genetic algorithm and simulation [J]. International Journal of Advanced Manufacturing Technology, 2006, 28: 129-136

[40] NassarK.. Evolutionary optimization of resource allocation in repetitive construction schedules [J]. ITcon, 2005, 10: 265-273

[41] RUIZ R, MAROTO C. Flexible manufacturing in the ceramic tile industry [C]// Proceedings of Eighth International Workshop on Project Management and Scheduling. Valencia, Spain, 2002: 301–304.

[42] SadegheihA.. Sequence optimization and design of allocation using GA and SA [J]. Applied Mathematics and Computation, 2007, 186(2): 1723-1730

[43] ShiueY.-R., GuhR.-S.. Learning-based multi-pass adaptive scheduling for a dynamic manufacturing cell environment [J]. Robotics and Computer-Integrated Manufacturing, 2006, 22: 203-216

[44] CheungS.-O., TongT. K.-L., TamC.-M.. Site pre-cast yard layout arrangement through genetic algorithms [J]. Automation in Construction, 2002, 11: 35-46

[45] WhitleyD.. GENITOR: a different genetic algorithm [C]. Proceedings of the Rocky Mountain Conference on Artificial Intelligence, 1988, Morgan Kaufman, Denver: 118-130

[46] DavisL.Handbook of genetic algorithms [M], 1991, New York, Van Nostrand Reinhold: 332-349

[47] GuptaM. C., GuptaY. P., KumarA.. Minimizing the flow time variance in a single machine system using genetic algorithms [J]. European Journal of Operational Research, 1993, 70: 289-303

[48] HAIDA T, AKIMOTO Y. Genetic algorithms approach to voltage optimization [C]// Proceedings of the IEEE First International Forum on the Applications of Neural Networks to Power Systems. Seattle, USA, 1991: 139–143.