A well-known combinatorial optimization problem known as the Flexible Job Shop Scheduling Problem (FJSP) often arises in engineering The complexity of the problem is complicated by the number of calculations required to find the optimal answer. In this work, we propose to use a parallel version of the Cuckoo Optimization Algorithm (COA) to solve the FJSP. Because parrots often lay their eggs in other birds’ nests, COA is a meta-heuristic optimization strategy. To increase speed, the proposed parallelized COA algorithm uses OpenMP to divide the computing workload among multiple processors. Benchmark examples taken from the literature are used to evaluate the performance of the proposed algorithm. The results show that, in terms of solution quality and computation time, the proposed method outperforms the current state-of-the-art methods
Research Article
Flexible Job shop Scheduling with the Parallelized Cuckoo Search Optimisation algorithm
https://doi.org/10.21203/rs.3.rs-3302650/v1
This work is licensed under a CC BY 4.0 License
Version 1
posted
You are reading this latest preprint version
Flexible job shop scheduling problem
Cuckoo Optimization Algorithm
Parallel computing
Combinatorial optimization
Meta-heuristic optimization
The flexible job shop scheduling problem (FJSP) is a variant of the traditional job shop scheduling problem where many tasks can be handled on a limited number of machines, where some activities can be completed in a specific order. For this reason, FJSP is a challenging combinatorial optimization problem that has received much research in the literature. Several accurate and approximate methods have been proposed to solve the FJSP. However, because of the high computational complexity, the exact control methods are not suitable for dealing with large data sets. Therefore, heuristic methods are selected for dealing with large data sets. The objective of the FJSP is to establish a practical and optimal schedule for each project that minimizes the total completion time or duration. Finding the best answer takes a lot of work because the problem is known to be NP-hard.
The importance of parallel computing to solve complex optimization issues. Using multiple processors or computers at once to solve a problem is called parallel computing. The quality of the solution increases, while using this method reduces the computation time. Consequently, there has been an increased interest in comparable meta-inferential optimization methods in recent years.
Popular statistical methods for solving combinatorial optimization problems include meta-estimation optimization algorithms. These algorithms solve optimization challenges by taking inspiration from social and environmental factors. The Cuckoos’ Optimization Algorithm (COA), which takes its cue from cuckoos’ propensity to rob nests, is one such scheme. Many combinatorial optimization problems have been solved using COA, especially job shop scheduling problems.
In a well-known optimization problem known as the flowshop job scheduling problem, a set of devices has to be scheduled. The goal is to reduce the makespan or time spent on all tasks. It is well known that the problem is NP-hard, which means that it is mathematically impossible to find exact solutions for large problem cases. Therefore, to address this issue, many people use meta-heuristics, which are heuristic optimization techniques. Optimization techniques known as meta-heuristics are used to determine near-optimal solutions. Several instructors have used meta-heuristic approaches to solve the flow shop task scheduling problem. Popular meta-heuristic algorithms include simulated annealing, particle swarm optimization, genetic algorithms, and ant colony optimization.
The paper by Ronghua Chen et. al. in 2020 [1] suggests a self-learning genetic algorithm (SLGA), in which reinforcement learning (RL) is used to intelligently alter the essential parameters of the genetic algorithm (GA), which is adopted as the fundamental optimisation approach.
In another paper by Dai Min et. al. in 2019 [2] The simple job shop scheduling problem of transport constraint is presented to a multi-objective optimization model with the objective of minimizing energy consumption and minimizing makespan and subsequently developing a genetic optimization strategy to solve the problem role. Finally, several experiments are conducted to evaluate the effectiveness of the proposed model and algorithm.
“An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times” by Jun-qing Li et. al in 2020 [3]. In this version, each solution is represented by the two-dimensional vector of the proposed algorithm. As a result, many locally-focused search engines are developed for utility projects. The method incorporates SA-based statistics to improve identification. Meanwhile, 30 models with different dimensions were fabricated and subjected to simulation testing to evaluate the efficiency of the proposed IJaya algorithm
“A Two-Level Particle Set Optimization Algorithm for the Flexible Job Shop Scheduling Problem” For the flexible job shop scheduling problem, this research proposes a method for flexibly mapping jobs to machines is controlled at a high level and sequencing activities to devices are controlled at a low level. For benchmark problems, the method is compared with current state-of-the-art solutions to the simple factory scheduling problem [4].
In “A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility”, to solve the proposed FJSPW, a hybrid artificial bee colony algorithm (HABCA) is presented [5]. To increase the HABCA's speed and exploitation potential, efficient encoding, decoding, crossover, and mutation operators are devised. Additionally, a novel efficient local search technique is created. To find the ideal combination of important HABCA parameters, the Taguchi method of Design of Experiments is utilised.
In “A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem” [6], A flexible job shop scheduling problem has been proposed which aims to minimize the maximum completion time or makespan, is considered in this study. Variable Neighborhood Search (VNS) based on Evolutionary Algorithms is proposed to balance between Intensification and Diversification to improve Searchability and solve such NP Hard Problem VNS algorithm has shown good local searchability by adopting methods over search local search programs.
Framework:
The proposed approach consists of the following steps based on original COA [7]:
Psuedo Code for the proposed methodology:
The COA is parallelized using OpenMP, which enables data interchange and communication across many processes. To parallelize COA, the iterations were performed in two parts. Total number of iterations suppose are taken to be 100. For the first 50 iterations, five threads were run with each thread performing 10 iterations. The resultant best cuckoos of each thread along with some randomly generated population was again fed into 5 threads for 10 iterations each. The best solution obtained is the one with the least cost out of the previous result.
Mathematical model:
The objective function for a parallelized cuckoo search algorithm for the Flexible Job Shop Scheduling Problem (FJSP) can be formulated as follows:
Minimize the makespan, i.e., the time taken to complete all the jobs, subject to the constraint that each job is processed on exactly one machine at a time.
Mathematically, if we represent the problem as a set of jobs J = {j1, j2, ..., jn} and a set of m machines M = {m1, m2, ..., mm}, and let Sij be the processing time of job j on machine i, then the objective function can be written as:
minimize max { Cj | j ∈ J }
subject to:
∑j ∈ J Sij × xij = Ci ∀ i ∈ M,
∑i ∈ M xij = 1 ∀ j ∈ J,
∑j ∈ J xi(k,j) = ∑j ∈ J xi(j,k) ∀ k ∈ M,
∑j ∈ J {Cj − Sij} × xij ≤ Tmax ∀ i ∈ M,
xij ∈ {0, 1} ∀ i ∈ M, ∀ j ∈ J,
where xij is a binary variable that takes the value 1 if job j is processed on machine i and 0 otherwise, and Ci is the completion time of job j, given by:
Ci = max {Ck + Sij | j ∈ J, k ∈ M, xik = 1, k ≠ i}
The first constraint ensures that each job is processed on exactly one machine at a time, the second constraint ensures that each machine processes exactly one job at a time, and the third constraint ensures that the completion times of all jobs are synchronized. The fourth constraint imposes a time limit Tmax on the makespan.
The cuckoo search algorithm can be used to search for the optimal solution by iteratively improving a set of candidate solutions. The parallelization of the algorithm can be achieved by dividing the search space into multiple subspaces and assigning each subspace to a different processor or thread for concurrent exploration.
The objective function is evaluated in each processor or thread to determine the fitness of the candidate solutions. The best solutions from each processor or thread are then combined to generate a new set of candidate solutions for the next iteration.
Experimental Results:
The proposed algorithm is tested on benchmark instances from the literature. The experiments are conducted on a computer with an Intel Core i7 processor and 16 GB RAM. The parameters of the algorithm are set as follows: population size = 50, number of iterations = 500, discovery rate = 0.25, abandonment rate = 0.25, and local search probability = 0.25. The proposed algorithm is compared with state-of-the-art algorithms.
PCOA results:
Example
Kacem sample data 1 has been used here:
|
4 5 3 5 1 2 2 5 3 4 4 1 5 2 5 1 5 2 4 3 5 4 7 5 5 5 1 4 2 5 3 5 4 4 5 5 3 5 1 2 2 5 3 4 4 7 5 8 5 1 5 2 6 3 9 4 8 5 5 5 1 4 2 5 3 4 4 54 5 5 4 5 1 9 2 8 3 6 4 7 5 9 5 1 6 2 1 3 2 4 5 5 4 5 1 2 2 5 3 4 4 2 5 4 5 1 4 2 5 3 2 4 1 5 5 2 5 1 1 2 5 3 2 4 4 5 12 5 1 5 2 1 3 2 4 1 5 2 |
The two numbers in the first line represent the number of jobs and the number of available machines respectively.
Then blocks of lines corresponding to the number of jobs follow with each block beginning with the number of operations.
Next up, each line gives the data for the operation where the first number indicates the number of route choices for that particular operation and next up on the same line, we have the machine numbers and the processing times for each of the route choices.
Number of iterations used: 500
Number of particles: 20
The result obtained after running the Parallel Cuckoo Optimisation Algorithm on the kacem data sample 1 is as follows:
|
Best Solution: Makespan:11 time taken = 0.280016 |
To test the performance of the proposed PCOA algorithm for preparing the FJSP, the algorithm was implemented in C and run on a computer with 2.83 GHz and 8 GB of RAM. The experimental results were compared with those obtained by other authors using a wide range of problem cases. These include:
• Kacem data: • Kacem data et al. [8] problems include tasks and activities that can be performed on a diverse number of devices.
• Fdata: 20 problems from Fattahi et al. [9], which are divided into small and large/large flexible business shop design problems. The problems involve tasks, devices, and functions.
• BRdata: 10 problems from Brandimarte [10] with different functions, devices and operations.
The results of the experiments are reported and compared with those of other algorithms. To account for the inherent nondeterministic nature of the proposed algorithms, we performed 30 independent runs for each sample from Kacem data, Fdata, and BRdata This served as an overall performance comparison.
We conducted preliminary tests of the proposed PCOA on three Kacem datasets, and our numerical results are presented below for PSO+SA [11], AL+CGA [8], PVNS [12]:
Table 1 Comparison of Results on Kacem Data
We conducted testing of the proposed PCOA on FData datasets, and our computational results are presented below for PCOA and AIA [13]
Table 2 Comparison of Results on FData
The results obtained for BRData has been shown below:
Table 3 Results on BRData
The simulation tests and comparison study depicted in the aforementioned Tables 1, 2, and 3 provide convincing proof that the suggested PCOA is a capable, quick, and resilient solution for addressing the FJSP with a makespan standard.
The discussions above suggest that effective scheduling technologies are crucial for improving the exploitation of resources in manufacturing operations. The Cuckoo Search (CS) algorithm technique among many evolutionary metaheuristic algorithms including GA, PSO, and ACO has shown considerable potential in scheduling optimization. CS is effective at exploring the search space because it can perform both local and global searches. CS has been used in a variety of ways to solve scheduling issues, but despite this, scheduling optimisation, a popular engineering optimisation topic, is yet to effectively access upon its potential.
The makespan criterion was primarily minimised in earlier works using the CS algorithm. This work, however, focuses on parallelizing the CS algorithm because it has produced successful results. Future research can focus on minimising makespan as well as other crucial objective functions including total flow time, mean flow time, total tardiness, and number of tardy jobs. Additionally, scheduling issues with setup and transportation times, equipment failure, pre-emptions, etc., may offer still another potential area of study. These difficult issues may encourage additional study in the near future.
Conflict of Interest
The authors of this paper declare that they have no conflicts of interest that could have influenced the design, administration, analysis, or reporting of the study This study was conducted with the highest level of scientific integrity and impartiality. No financial, personal, or professional relationships with individuals or organizations influenced the information or conclusions presented in this paper.
- B. Y. S. L. S. W. Ronghua Chen, “A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem,” Computers & Industrial Engineering, p. 106778, 2020.
- T. D. G. A. S. M. A. Dai Min, “Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints,” Robotics and Computer-Integrated Manufacturing, pp. 143–157, 2019.
- J.-w. D. C.-y. L. Y.-y. H. J. T. B. Z. C.-g. W. Jun-qing Li, “An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times,” Knowledge-Based Systems, p. 106032, 2020.
- R. B. I. &. J. A. Zarrouk, “A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem,” Swarm Intelligence, vol. 13, p. 145–168, 2019.
- R. C. Q. D. &. X. G. Guiliang Gong, “A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility,” International Journal of Production Research, vol. 58, no. 14, pp. 4406–4420, 2020.
- G. Z. L. S. X. e. a. Zhang, “A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem.,” Cluster Computing, vol. 22, p. 11561–11572, 2019.
- R. Rajabioun, “Cuckoo Optimization Algorithm,” Applied Soft Computing, vol. 11, no. 8, pp. 5508–5518, 2011.
- I. S. H. a. P. B. Kacem, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 32, no. 1, pp. 1–13, 2002.
- P. S. M. M. &. J. F. Fattahi, “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,” Journal of intelligent manufacturing, vol. 18, pp. 331–342, 2007.
- P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations research, vol. 41, no. 3, pp. 157–183, 1993.
- Z. W. Weijun Xia, “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computers & Industrial Engineering, vol. 48, no. 2, pp. 409–425, 2005.
- M. A. M. Z. M. Yazdani, “Flexible job-shop scheduling with parallel variable neighborhood search algorithm,” Expert Systems with Applications, vol. 37, no. 1, p. 678–687, 2010.
- M. Z. I. M. M. Y. A. Bagheri, “An artificial immune algorithm for the flexible job-shop scheduling problem,” Future Generation Computer Systems, vol. 26, no. 4, p. 533–541, 2010.