Development of a Bees Algorithm for the Job Shop Scheduling Problem
Main Article Content
Abstract
The Job Shop Scheduling Problem (JSSP) is a combinatorial optimization problem classified as NP-hard.
It has important implications in both theory and applications, particularly in production management, job planning, transportation, and service systems. Over the past decades, JSSP has attracted considerable research attention, with many approaches proposed, including exact algorithms, heuristics, and metaheuristics. In this paper, we propose a new algorithm, called BeeJSS, which is based on the basic Bees Algorithm, to solve the JSSP. We evaluate the effectiveness of BeeJSS on the standard Lawrence benchmark dataset. Experimental results indicate that BeeJSS performs comparably to several metaheuristic algorithms currently known
Keywords
bees algorithm, heuristic algorithm, job shop scheduling, lawrence benchmark dataset, metaheuristic algorithm
Article Details
References
[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