Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lập lịch đồng thời cho các công việc và xe tự hành trong hệ thống xưởng linh hoạt: một thuật toán meta-heuristic lai PSO-GA theo kiểu song song
Tóm tắt
Nghiên cứu này đề xuất một mô hình lập trình nguyên hợp (MILP) mới cùng với một Thuật toán Lai PSO-GA Theo Kiểu Song Song (PPSOGA) nhằm giải quyết vấn đề lập lịch đồng thời cho các công việc và Xe Tự Hành (AGV) trong một hệ thống xưởng linh hoạt. Trong đó, nhiều AGV hữu hạn, các lộ trình xử lý thay thế, và việc tái nhập công việc được xem xét. Theo kiến thức tốt nhất của chúng tôi, chưa có nghiên cứu nào trong tài liệu nêu bật hiệu quả của việc tính toán song song trong lập lịch đồng thời cho các công việc và các phương tiện vận chuyển trong một hệ thống xưởng linh hoạt, điều này làm giảm đáng kể thời gian chạy. Để đạt được mục đích này, meta-heuristic được đề xuất được thiết kế tương thích với tính toán song song và được so sánh với một số meta-heuristic nổi tiếng (tức là Genetic Algorithm, Particle Swarm Optimization, và Ant Colony Optimization) trên một bộ 40 trường hợp chuẩn được tạo ra bằng cách kết hợp các phân bố khác nhau (tức là, phân bố đồng nhất, phân bố mũ, và phân bố chuẩn). Sử dụng hai bài kiểm tra Tukey, thời gian chạy trung bình và giá trị mục tiêu trung bình của tất cả các meta-heuristic được đề xuất được kiểm tra và so sánh lẫn nhau, kết quả nhấn mạnh sự ưu việt của PPSOGA so với tất cả các phương pháp giải pháp khác về giá trị của hàm mục tiêu và thời gian chạy. Cuối cùng, kết quả cho thấy ngay cả chế độ tuần tự của PPSOGA (tức là PSOGA) cũng tạo ra các giá trị mục tiêu tốt hơn so với các meta-heuristic khác.
Từ khóa
#lập lịch đồng thời #xe tự hành #hệ thống xưởng linh hoạt #lập trình nguyên hợp #thuật toán meta-heuristic lai #phương pháp tính toán song songTài liệu tham khảo
Abdelmaguid TF, Nassef AO, Kamal BA, Hassan MF (2004) A hybrid ga/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. Int J Prod Res 42(2):267–281
Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401
Ahmadi-Javid A, Hooshangi-Tabrizi P (2017) Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: a mathematical formulation and an anarchic society optimization algorithm. Comput Oper Res 84:73–91
Anwar MF, Nagi R (1998) Integrated scheduling of material handling and manufacturing activities for just-in-time production of complex assemblies. Int J Prod Res 36(3):653–681
Asadzadeh L (2016) A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy. Comput Ind Eng 102:359–367
Bilge Ü, Ulusoy G (1995) A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Oper Res 43(6):1058–1070
Bożejko W, Gnatowski A, Pempera J, Wodecki M (2017) Parallel tabu search for the cyclic job shop scheduling problem. Comput Ind Eng 113:512–524
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41(3):157–183
Caumond A, Lacomme P, Moukrim A, Tchernev N (2009) An milp for scheduling problems in an FMS with one vehicle. Eur J Oper Res 199(3):706–722
Dabah A, Bendjoudi A, AitZai A, Taboudjemat NN (2019) Efficient parallel tabu search for the blocking job shop scheduling problem. Soft Comput 23(24):13283–13295
Dao T-K, Pan T-S, Pan J-S et al (2015) Parallel bat algorithm for optimizing makespan in job shop scheduling problems. J Intell Manuf 29(2):451–462
De Giovanni L, Pezzella F (2010) An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. Eur J Oper Res 200(2):395–408
Deroussi L, Norre S (2010) Simultaneous scheduling of machines and vehicles for the flexible job shop problem. In: International conference on meta-heuristics and nature inspired computing. Djerba Island Tunisia, pp 1–2
Deroussi L, Gourgand M, Tchernev N (2008) A simple meta-heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. Int J Prod Res 46(8):2143–2164
Drießel R, Mönch L (2012) An integrated scheduling and material-handling approach for complex job shops: a computational study. Int J Prod Res 50(20):5966–5985
Huang R-H, Yu T-H (2017) An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Appl Soft Comput 57:642–656
Hurink J, Knust S (2002) A tabu search algorithm for scheduling a single robot in a job-shop environment. Discret Appl Math 119(1–2):181–203
Hurink J, Knust S (2005) Tabu search algorithms for job-shop problems with a single transport robot. Eur J Oper Res 162(1):99–111
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of ICNN’95-international conference on neural networks, vol 4, IEEE, pp 1942–1948
Lacomme P, Larabi M, Tchernev N (2007) A disjunctive graph for the job-shop with several robots. In: MISTA conference, vol 20, pp 285–292
Lacomme P, Larabi M, Tchernev N (2013) Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. Int J Prod Econ 143(1):24–34
Li M, Lei D (2021) An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times. Eng Appl Artif Intell 103:104307
Li J-Q, Deng J-W, Li C-Y, Han Y-Y, Tian J, Zhang B, Wang C-G (2020) An improved jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowl-Based Syst 200:106032
Liu Z, Guo S, Wang L (2019) Integrated green scheduling optimization of flexible job shop and crane transportation considering comprehensive energy consumption. J Clean Prod 211:765–786
Luo J, El Baz D, Xue R, Hu J (2020) Solving the dynamic energy aware job shop scheduling problem with the heterogeneous parallel genetic algorithm. Future Gener Comput Syst 108:119–134
Maroosi A, Muniyandi RC, Sundararajan E, Zin AM (2016) A parallel membrane inspired harmony search for optimization problems: a case study based on a flexible job shop scheduling problem. Appl Soft Comput 49:120–136
Mastrolilli M, Gambardella LM (2000) Effective neighbourhood functions for the flexible job shop problem. J Sched 3(1):3–20
Nouri HE, Driss OB, Ghédira K (2016) Hybrid meta-heuristics for scheduling of machines and transport robots in job shop environment. Appl Intell 45(3):808–828
Pandit R (1993) Job shop scheduling with explicit material handling considerations. Working paper, Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, IL
Raman N (1986) Simultaneous scheduling of machines and material handling devices in automated manufacturing. In: Proceedings of the first ORSA/TIMS conference on flexible manufacturing systems, Ann Arbor, MI’, pp 455–465
Sotskov YN, Shakhlevich NV (1995) Np-hardness of shop-scheduling problems with three jobs. Discret Appl Math 59(3):237–266
Sun J, Zhang G, Lu J, Zhang W (2021) A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times. Comput Oper Res 132:105263
Taguchi G (1986) Introduction to quality engineering: designing quality into products and processes, Technical report, sidalc.net
Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54(3):453–473
Tukey JW (1949) Comparing individual means in the analysis of variance. Biometrics, pp 99–114
Ulusoy G, Sivrikaya-Şerifoǧlu F, Bilge Ü (1997) A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles. Comput Oper Res 24(4):335–351
Van Laarhoven PJ, Aarts EH, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40(1):113–125
Zhang Q, Manier H, Manier M-A (2012) A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Comput Oper Res 39(7):1713–1723
Zhang Q, Manier H, Manier M-A (2014) A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints. Int J Prod Res 52(4):985–1002
Zhang G, Sun J, Lu X, Zhang H (2020) An improved memetic algorithm for the flexible job shop scheduling problem with transportation times. Meas Control 53(7–8):1518–1528
Zhang H, Xu G, Pan R, Ge H (2021) A novel heuristic method for the energy-efficient flexible job-shop scheduling problem with sequence-dependent set-up and transportation time. Eng Optim 1:1–22. https://doi.org/10.1080/0305215X.2021.1949007