A discrete Jaya algorithm for permutation flow-shop scheduling problem

Abstract: Jaya algorithm has recently been proposed, which is simple and efficient meta-heuristic optimization technique and has received a great attention in the world of optimization. It has been successfully applied to some thermal, design and manufacturing associated optimization problems. This paper aims to analyze the performance of Jaya algorithm for permutation flow-shop scheduling problem which is a well-known NP-hard optimization problem. The objective is to minimize the makespan. First, to make Jaya algorithm adaptive to the problem, a random priority is allocated to each job in a permutation sequence. Second, a job priority vector is converted into job permutation vector by means of Largest Order Value (LOV) rule. An exhaustive comparative study along with statistical analysis is performed by comparing the results with public benchmarks and other competitive heuristics. The key feature of Jaya algorithm of simultaneous movement towards the best solution and going away from the worst solution enables it to avoid being trapped in the local optima. Furthermore, the uniqueness of Jaya algorithm compared with any other evolutionary based optimization technique is that it is totally independent of specific parameters. This substantially reduces the computation effort and numerical complexity. Computational results reveal that Jaya algorithm is efficient in most cases and has considerable potential for permutation flow-shop scheduling problems.

How to cite this paper

 Mishra, A & Shrivastava, D. (2020). A discrete Jaya algorithm for permutation flow-shop scheduling problem.International Journal of Industrial Engineering Computations , 11(3), 415-428.

Refrences

Abhishek, K., Kumar, V. R., Datta, S., & Mahapatra, S. S. (2017). Application of JAYA algorithm for the optimization of machining performance characteristics during the turning of CFRP (epoxy) composites: comparison with TLBO, GA, and ICA. Engineering with Computers, 33(3), 457–475.
Baykasoǧlu, A., Hamzadayi, A., & Köse, S. Y. (2014). Testing the performance of teaching-learning based optimization (TLBO) algorithm on combinatorial problems: Flow shop and job shop scheduling cases. Information Sciences, 276, 204–218.
Buddala, R., & Mahapatra, S. S. (2017). Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems. Journal of Industrial Engineering International, 1–16.
Carlier, J. (1978). Ordonnancements a contraintes disjonctives. RAIRO-Operations Research.
Du, D.-C., Vinh, H.-H., Trung, V.-D., Hong Quyen, N.-T., & Trung, N.-T. (2017). Efficiency of Jaya algorithm for solving the optimization-based structural damage identification problem based on a hybrid objective function. Engineering Optimization, 273(September), 1–19.
Engin, O., & Güçlü, A. (2018). A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems. Applied Soft Computing, 72, 166–176.
Gao, K., Sadollah, A., Zhang, Y., & Su, R. (2016). Discrete Jaya Algorithm for Flexible Job Shop Scheduling Problem with New Job Insertion. 14th International Conference on Control, Automation, Robotics & Vision, 2016(61603169), 13–15.
Gao, K., Zhang, Y., Sadollah, A., Lentzakis, A., & Su, R. (2016). Jaya, harmony search and water cycle algorithms for solving large-scale real-life urban traffic light scheduling problem. Swarm and Evolutionary Computation, (May), 1–15.
Guo, J., Gao, K., Wang, C., Sang, H., Li, J., & Duan, P. (2017). Discrete Jaya algorithm for solving flexible job shop rescheduling problem. 2017 29th Chinese Control And Decision Conference (CCDC), 6010–6015.
Huang, C., Wang, L., Yeung, R. S. cheung, Zhang, Z., Chung, H. S. H., & Bensoussan, A. (2017). A Prediction Model Guided Jaya Algorithm for the PV System Maximum Power Point Tracking. IEEE Transactions on Sustainable Energy, 3029(c).
Kuo, I.-H., Horng, S.-J., Kao, T.-W., Lin, T.-L., Lee, C.-L., Terano, T., & Pan, Y. (2009). An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model. Expert Systems with Applications, 36(3), 7027–7032.
Lin, Q., Gao, L., Li, X., & Zhang, C. (2015). A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. Computers & Industrial Engineering, 85, 437–446.
Liu, B., Wang, L., & Jin, Y. H. (2008). An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers. Computers and Operations Research, 35(9), 2791–2806.
Madhushini, N., & Rajendran, C. (2011). Branch-and-bound algorithms for scheduling in an m-machine permutation flowshop with a single objective and with multiple objectives. European J. of Industrial Engineering, 5(4), 361.
Mishra, A., & Shrivastava, D. (2018). A TLBO and a Jaya heuristics for permutation flow shop scheduling to minimize the sum of inventory holding and batch delay costs. Computers & Industrial Engineering, 124(July), 509–522.
Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95.
Osman, I., & Potts, C. (1989). Simulated annealing for permutation flow-shop scheduling. Omega, 17(6), 551–557.
Pan, Q.-K., Tasgetiren, M. F., Suganthan, P. N., & Chua, T. J. (2011). A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 181(12), 2455–2468.
Qian, B., Wang, L., Hu, R., Wang, W. L., Huang, D. X., & Wang, X. (2008). A hybrid differential evolution method for permutation flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 38(7–8), 757–777.
Radhika, S., Ch, S. R., D, N. K., & K, K. P. (2016). Multi-Objective Optimization of Master Production Scheduling Problems using Jaya Algorithm. (December), 1729–1732.
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–438.
Rao, R. V., & More, K. C. (2017). Design optimization and analysis of selected thermal devices using self-adaptive Jaya algorithm. Energy Conversion and Management, 140, 24–35.
Rao, R. V., More, K. C., Taler, J., & Ocłoń, P. (2016). Dimensional optimization of a micro-channel heat sink using Jaya algorithm. Applied Thermal Engineering, 103, 572–582.
Rao, R. V., & Rai, D. P. (2017). Optimization of submerged arc welding process parameters using quasi-oppositional based Jaya algorithm. Journal of Mechanical Science and Technology, 31(5), 2513–2522.
Rao, R. V., Rai, D. P., & Balic, J. (2016). Surface Grinding Process Optimization Using Jaya Algorithm. https://doi.org/10.1007/978-81-322-2731-1_46
Rao, R. V., & Saroj, A. (2017). Economic optimization of shell-and-tube heat exchanger using Jaya algorithm with maintenance consideration. Applied Thermal Engineering, 116, 473–487.
Reeves, C. R., & Yamada, T. (1998). Genetic Algorithms, Path Relinking, and the Flowshop Sequencing Problem. Evolutionary Computation, 6(1), 45–60. https://doi.org/10.1162/evco.1998.6.1.45
Reza Hejazi, S., & Saghafian, S. (2005). Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895–2929.
Rinnooy Kan, A. H. G. (1976). Machine Scheduling Problems : Classification, complexity and computations. Springer US.
Ruiz, R., Pan, Q.-K., & Naderi, B. (2019). Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega, 83, 213–222.
Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049.
Singh, S. P., Prakash, T., Singh, V. P., & Babu, M. G. (2017). Analytic hierarchy process based automatic generation control of multi-area interconnected power system using Jaya algorithm. Engineering Applications of Artificial Intelligence, 60(December 2016), 35–44.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65–74.
Tseng, F. T., & Stafford, E. F. (2008). New MILP models for the permutation flowshop problem. Journal of the Operational Research Society, 59(10), 1373–1386.
Venkata Rao, R. (2016). Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 7, 19–34.
Venkata Rao, R. (2019). Introduction. In Jaya: An Advanced Optimization Algorithm and its Engineering Applications (pp. 1–8). https://doi.org/10.1007/978-3-319-78922-4_1
Wang, L., & Zheng, D. Z. (2003). An effective hybrid heuristic for flow shop scheduling. International Journal of Advanced Manufacturing Technology, 21(1), 38–44.
Zhang, W., Wang, Y., Yang, Y., & Gen, M. (2019). Hybrid multiobjective evolutionary algorithm based on differential evolution for flow shop scheduling problems. Computers & Industrial Engineering, 130, 661–670. https://doi.org/10.1016/J.CIE.2019.03.019
Zhang, Y., Yang, X., Cattani, C., Rao, R. V., Wang, S., & Phillips, P. (2016). Tea category identification using a novel fractional fourier entropy and Jaya algorithm. Entropy, 18(3), 1–17. https://doi.org/10.3390/e18030077
Zhao, F., Liu, H., Zhang, Y., Ma, W., & Zhang, C. (2018). A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem. Expert Systems with Applications, 91, 347–363.