PHÁT TRIỂN THUẬT TOÁN BEES GIẢI BÀI TOÁN JOB SHOP SCHEDULING
Nội dung chính của bài viết
Tóm tắt
Bài toán Job Shop Scheduling (Job Shop Scheduling Problem - JSSP) là một trong những bài toán tối ưu tổ hợp thuộc lớp NP-hard. JSSP có ý nghĩa quan trọng cả về mặt lý thuyết lẫn ứng dụng, đặc biệt là trong các lĩnh vực quản lý sản xuất, lập kế hoạch công việc, vận tải và hệ thống dịch vụ. Trong nhiều thập kỷ qua, JSSP đã thu hút sự quan tâm của cộng đồng nghiên cứu, với nhiều hướng tiếp cận được đề xuất, bao gồm các thuật toán giải chính xác, heuristic và metaheuristic. Trong bài báo này, chúng tôi phát triển một thuật toán mới dựa trên thuật toán Bees cơ bản để giải JSSP; chúng tôi đặt tên thuật toán này là BeeJSS.
Chúng tôi đã tiến hành đánh giá hiệu quả của thuật toán BeeJSS trên hệ thống dữ liệu thực nghiệm chuẩn Lawrence. Kết quả thực nghiệm cho thấy thuật toán BeeJSS có hiệu năng so sánh được với một số thuật toán metaheuristic hiện biết.
Từ khóa
bees algorithm, heuristic algorithm, job shop scheduling, lawrence benchmark dataset, metaheuristic algorithm
Chi tiết bài viết
Tài liệu tham khảo
[2]. Brucker P, “A branch and bound algorithm for the Job Shop scheduling problem”, Elsevier, 1992. [3]. Brucker P, “Scheduling algorithms”, Springer, 2007.
[4]. Carlier J, Pinson E, “An algorithm for solving the Job Shop problem”, Management Science, pp.164-176, 1989.
[5]. Dervis Karaboga, Bahriye Basturk, “On the performance of artificial bee colony
algorithm”. ELSEVIER, Applied Soft Computing 8, pp.687–697, 2008.
[6]. Dervis Karaboga, Bahriye Basturk, “A powerful and efficient algorithm for numerical function optimization: Artificial bee colony algorithm”, Springer, 2007. [7]. Dauzère-Pérès, S. & Lasserre, J. B. A, “Modified shifting bottleneck procedure for Job
Shop scheduling”, International Journal of Production Research, 31(4), pp.923–932, 1993.
[8]. Đỗ Ngọc Nhung, “Nghiên cứu và xây dựng thuật toán bees giải bài toán Job Shop
scheduling“ (Luận văn thạc sỹ chuyên ngành khoa học máy tính), Trường Đại học Sài Gòn, 2025.
[9]. J. A. S. Gromicho et al., “Solving the job-shop scheduling problem optimally by dynamic
programming”, Computers & Operations Research, vol. 39, pp. 2968–2977, 2012. [10]. Laarhoven P. J. M. et al., “Job Shop scheduling by simulated annealing”, Openations Research, 1992.
[11]. Laguna M, Glover F, “Integrading target analysis and tabu search for improved
scheduling system”, Expert Systems with Application, 1993.
[12]. Meenambigai R, “Job Shop scheduling using bee colony optimization algorithm”, ICCIAMR, 2014.
[13]. Moraglio A et al., “Genetic local search for Job Shop scheduling problem”.
[14]. Nakano R, Yamada T, “Conventional genetic algorithm for Job Shop problem”, In proceedings of international conference on genetic algorithms, 1991.
[15]. Nowicki E, Smutnicki C, “A fast taboo search algorithm for the job shop problem”, Management Science, 1996.
[16]. Nguyễn Hữu Mùi, “Thuật toán và các bài toán lịch biểu” (Luận án tiến sĩ công nghệ thông tin), Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2013.
[17]. P. Brucker, B. Jurisch & B. Sievers, “A branch and bound algorithm for the Job Shop scheduling problem”, Discrete Applied Mathematics, vol. 49, pp. 107–127, 1994.
[18]. Pham D. T. et al., “Using the Bees Algorithm to schedule jobs for a machine”, Manufacturing Engineering Centre, Cardiff University, 2007.
[19]. Pham D.T. et al., “The bees algorithm - A novel tool for complex optimisation problems”. ELSEVIER, Proceedings of IPROMS 2006 Conference, Cardiff University, pp.454–461, (2006).
[20]. Phan Tấn Quốc, Nguyễn Đức Nghĩa, “Thuật toán bầy ong giải bài toán cây khung với chi phí định tuyến nhỏ nhất”. ICTFIT (Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia TpHCM), Tuyển tập công trình nghiên cứu Công nghệ thông tin & Truyền thông, Nhà xuất bản Khoa học Kỹ thuật, pp.73-81, 2012.
[21]. Phan Tấn Quốc, Nguyễn Đức Nghĩa, “Thuật toán bầy ong giải bài toán cây khung với
chi phí định tuyến nhỏ nhất”, Tạp chí Tin học và Điều khiển học, T.29, S3, 2013, pp.265-276, 2013.
[22]. Pinedo M, “Scheduling: Theory, Algorithms, and Systems”, Springer, 2016.
[23]. Xin-She Yang (2010). Nature-inspired metaheuristic algorithms. LUNIVER Press, pp.53–62.
[24]. Yamada T, Nakano R, “Job Shop scheduling by simulated annealing combined with deterministic local search”, Metaheuristics International Conference, 1995.
[25]. Yamamoto K, “Solving the Job Shop scheduling problem optimally by dynamic programming”, Academia.edu, 2022.
[26]. Yin B. Y, Li L, and Zhou H. X, “An efficient Job Shop scheduling algorithm based on artificial bee colony”, In Proceedings of the 8th World Congress on Intelligent Control and Automation, 2010.
[27]. Youssefi M. et al., “Bottom-up variants for the Job Shop scheduling problem”, Simulation and Modeling Methodologies, Technologies and Applications, 2024.
[28]. Zhang C. et al., “A very fast TS/SA algorithm for the Job Shop scheduling problem”, Computers and Operations Research, 2008.
[29]. https://www.eii.uva.es/elena/Elena%20Perez%20Vazquez_archivos/files_optimaJSS P/jobshop1.txt
[30]. https://github.com/thomasWeise/jsspInstancesAndResults/blob/master/data-raw/ results/all_results.txt