Application of an Efficient Genetic Algorithm for Solving n×m Flow Shop Scheduling Problem Comparing it with Branch and Bound Algorithm and Tabu Search Algorithm
Keywords:
Flow shop scheduling, Efficient genetic algorithm (EGA), Makespan, Branch and Bound algorithm, C code, Tabu search algorithm.Abstract
Emergence of advance manufacturing systems such as CAD/CAM, FMS and CIM etc. has increased the importance of the flow shop scheduling. Flow shop scheduling problem is considered NP-hard for m machines and n jobs. In this paper, we develop an efficient genetic algorithm (EGA) for solving n flow shop scheduling problem with makespan as the criterion. The objective of this proposed EGA is to obtain a sequence of jobs and the minimization of the total completion time and waiting time. For finding optimal solution, this EGA is very effective. In large scale problems, the result of the proposed algorithm shows that the efficient genetic algorithm gives high performance comparing with Branch and Bound algorithm and Tabu search algorithm.
References
[1] Stafford, E. F., Tseng, F. T., Gupta, J. N. D. “Comparative evaluation of MILP flowshop models.” J.of the Ope. Res. Soc., vol. 56, pp. 88–101, 2005.
[2] Tseng, F. T., & Stafford, E. F. “New MILP models for the permutation flowshop problem.” Journal of the Operational Research Society, vol. 59(10), pp. 1373-1386, 2008.
[3] Mashhadi, M. M., Stafford, E. F., & Tseng, F. T. “Development of a new model for the flowshop problem.” in Industrial Engineering and Engineering Management, 2007 IEEE International Conference on IEEE, Dec. 2007, pp. 935-939.
[4] Yenisey, M. M., & Yagmahan, B. “Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends.” Omega, vol. 45, pp. 119-135, 2014.
[5] K. R Baker. Introduction to sequencing and scheduling. New York : wiley, 1974.
[6] AHG Rinnoy and Kan. Machine Scheduling Problems: Classification, Complexity and Computations. The Hague: Martinus Nijhoff, 1976.
[7] Yoshida and Hitomi, “Optimal two stage production scheduling with set up times separated.” AIIETransactions, vol. II, pp. 261-263, 1979.
[8] Ahmad Pour Darvish and Heydari, “On flow shop scheduling problem with processing of jobs in a string of disjoint job blocks: fixed order jobs and arbitrary order jobs.” JISSOR, vol. XXIV, pp. 1- 4, 2003.
[9] Singh, T.P., K, Rajindra & Gupta Deepak. “Optimal three stage production schedule the processing time and set up times associated with probabilities including job block criteria.” in Proceeding of National Conference FACM, 2005, pp. 463-470.
[10] E.G, Coffiman. Computer and job Scheduling Theory. New York: Wiley, 1976.
[11] S.French. Sequencing And Scheduling:An Introduction to the Mathematics of the job shop. Chichester, UK: Ellis Horwood, 1982.
[12] Garey, M. R., Johnson and D. S. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W.H. Freeman and Company, 1979.
[13] Lomnicki, Z.A. “A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem.” Operational Research Quarterly, vol. 16, pp.89-100, 1965.
[14] Gupta, D., Singla, P. and Bala, S. “Application of Branch And Bound Technique for n* 3 Flow Shop Scheduling with Breakdown Interval.” International Journal for Engineering Research and Application, vol. 2, pp. 1675-1677.
[15] Osman I H and Potts C N, "Simulated annealing for permutation flow-shop scheduling." Omega, vol. 17, pp. 551-557. 1989.
[16] Widmer, M. and Hertz, A. “A new heuristic method for the flow shop sequencing problem.” European Journal of Operational Research, vol. 41(2), pp. 186-193, 1989.
[17] Taillard, E. “Some efficient heuristic methods for the flow shop sequencing problem.” European journal of Operational research, vol. 47(1), pp. 65-74, 1990.
[18] Glass, C. A., Gupta, J. N. D., Potts and C. N. “Two-machine Flow Shop Scheduling with Missing Operations: Special Cases and Approximation Algorithms Preprint OR75.” Faculty of Mathematical Studies, University of Southampton, U.K, 1995.
[19] Leisten, R., and Kolbe, M. “A note on scheduling jobs with missing operations in permutation flow shops.” International journal of production research, vol. 36(9), pp. 2627-2630, 1998.
[20] Sadjadi, S. J., Aryanezhaad, M. B., Ziaee, M. “The general flowshop scheduling problem: mathematical models.” J. of app. sci., vol. 8(17), pp. 3032-3037, 2008.
[21] Reeves, C. R. “A genetic algorithm for flowshop sequencing.” Computers & operations research, vol. 22(1), pp. 5-13, 1995.
[22] Murata, T., Ishibuchi, H., & Tanaka, H. “Genetic algorithms for flowshop scheduling problems.” Computers & Industrial Engineering, vol. 30(4), pp. 1061-1071, 1996.
[23] Etiler, O., Toklu, B., Atak, M., Wilson, J. “A genetic algorithm for flow shop scheduling problems.” J. of the Ope. Res. Soc., vol. 55, pp. 830–835, 2004.
[24] Holland, J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
[25] Nowicki, E., & Smutnicki, C. “A fast tabu search algorithm for the permutation flow-shop problem.” European Journal of Operational Research, vol.91(1), pp.160-175, 1996.
[26] Ben-Daya, M., & Al-Fawzan, M. “A tabu search approach for the flow shop scheduling problem.” European journal of operational research, vol. 109(1), pp. 88-95, 1998.
[27] Solimanpur, M., Vrat, P., Shankar, R. “A neuro-tabu search heuristic for the flow shop scheduling problem.” Comp. & Ope. Res., vol. 31, pp. 2151-2164, 2004.
[28] Ignall, E., & Schrage, L. “Application of the branch and bound technique to some flow-shop scheduling problems.” Operations research, vol. 13(3), pp. 400-412, 1965.
[29] Ladhari, T, Haouari, M, “A computational study of the PESP based on a tight lower bound.” Computers & Operations Research, vol. 32, pp. 1831-1847, 2005.
[2] Tseng, F. T., & Stafford, E. F. “New MILP models for the permutation flowshop problem.” Journal of the Operational Research Society, vol. 59(10), pp. 1373-1386, 2008.
[3] Mashhadi, M. M., Stafford, E. F., & Tseng, F. T. “Development of a new model for the flowshop problem.” in Industrial Engineering and Engineering Management, 2007 IEEE International Conference on IEEE, Dec. 2007, pp. 935-939.
[4] Yenisey, M. M., & Yagmahan, B. “Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends.” Omega, vol. 45, pp. 119-135, 2014.
[5] K. R Baker. Introduction to sequencing and scheduling. New York : wiley, 1974.
[6] AHG Rinnoy and Kan. Machine Scheduling Problems: Classification, Complexity and Computations. The Hague: Martinus Nijhoff, 1976.
[7] Yoshida and Hitomi, “Optimal two stage production scheduling with set up times separated.” AIIETransactions, vol. II, pp. 261-263, 1979.
[8] Ahmad Pour Darvish and Heydari, “On flow shop scheduling problem with processing of jobs in a string of disjoint job blocks: fixed order jobs and arbitrary order jobs.” JISSOR, vol. XXIV, pp. 1- 4, 2003.
[9] Singh, T.P., K, Rajindra & Gupta Deepak. “Optimal three stage production schedule the processing time and set up times associated with probabilities including job block criteria.” in Proceeding of National Conference FACM, 2005, pp. 463-470.
[10] E.G, Coffiman. Computer and job Scheduling Theory. New York: Wiley, 1976.
[11] S.French. Sequencing And Scheduling:An Introduction to the Mathematics of the job shop. Chichester, UK: Ellis Horwood, 1982.
[12] Garey, M. R., Johnson and D. S. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W.H. Freeman and Company, 1979.
[13] Lomnicki, Z.A. “A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem.” Operational Research Quarterly, vol. 16, pp.89-100, 1965.
[14] Gupta, D., Singla, P. and Bala, S. “Application of Branch And Bound Technique for n* 3 Flow Shop Scheduling with Breakdown Interval.” International Journal for Engineering Research and Application, vol. 2, pp. 1675-1677.
[15] Osman I H and Potts C N, "Simulated annealing for permutation flow-shop scheduling." Omega, vol. 17, pp. 551-557. 1989.
[16] Widmer, M. and Hertz, A. “A new heuristic method for the flow shop sequencing problem.” European Journal of Operational Research, vol. 41(2), pp. 186-193, 1989.
[17] Taillard, E. “Some efficient heuristic methods for the flow shop sequencing problem.” European journal of Operational research, vol. 47(1), pp. 65-74, 1990.
[18] Glass, C. A., Gupta, J. N. D., Potts and C. N. “Two-machine Flow Shop Scheduling with Missing Operations: Special Cases and Approximation Algorithms Preprint OR75.” Faculty of Mathematical Studies, University of Southampton, U.K, 1995.
[19] Leisten, R., and Kolbe, M. “A note on scheduling jobs with missing operations in permutation flow shops.” International journal of production research, vol. 36(9), pp. 2627-2630, 1998.
[20] Sadjadi, S. J., Aryanezhaad, M. B., Ziaee, M. “The general flowshop scheduling problem: mathematical models.” J. of app. sci., vol. 8(17), pp. 3032-3037, 2008.
[21] Reeves, C. R. “A genetic algorithm for flowshop sequencing.” Computers & operations research, vol. 22(1), pp. 5-13, 1995.
[22] Murata, T., Ishibuchi, H., & Tanaka, H. “Genetic algorithms for flowshop scheduling problems.” Computers & Industrial Engineering, vol. 30(4), pp. 1061-1071, 1996.
[23] Etiler, O., Toklu, B., Atak, M., Wilson, J. “A genetic algorithm for flow shop scheduling problems.” J. of the Ope. Res. Soc., vol. 55, pp. 830–835, 2004.
[24] Holland, J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
[25] Nowicki, E., & Smutnicki, C. “A fast tabu search algorithm for the permutation flow-shop problem.” European Journal of Operational Research, vol.91(1), pp.160-175, 1996.
[26] Ben-Daya, M., & Al-Fawzan, M. “A tabu search approach for the flow shop scheduling problem.” European journal of operational research, vol. 109(1), pp. 88-95, 1998.
[27] Solimanpur, M., Vrat, P., Shankar, R. “A neuro-tabu search heuristic for the flow shop scheduling problem.” Comp. & Ope. Res., vol. 31, pp. 2151-2164, 2004.
[28] Ignall, E., & Schrage, L. “Application of the branch and bound technique to some flow-shop scheduling problems.” Operations research, vol. 13(3), pp. 400-412, 1965.
[29] Ladhari, T, Haouari, M, “A computational study of the PESP based on a tight lower bound.” Computers & Operations Research, vol. 32, pp. 1831-1847, 2005.
Downloads
Published
2018-03-11
How to Cite
Ahmed, M. H., Ema, R. R., Islam, T., & M Pir, R. (2018). Application of an Efficient Genetic Algorithm for Solving n×m Flow Shop Scheduling Problem Comparing it with Branch and Bound Algorithm and Tabu Search Algorithm. American Scientific Research Journal for Engineering, Technology, and Sciences, 41(1), 12–25. Retrieved from https://asrjetsjournal.org/index.php/American_Scientific_Journal/article/view/3900
Issue
Section
Articles
License
Authors who submit papers with this journal agree to the following terms.
