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
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 NPhard 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.
Keywords
Full Text:
PDFReferences
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.
Tseng, F. T., & Stafford, E. F. “New MILP models for the permutation flowshop problem.” Journal of the Operational Research Society, vol. 59(10), pp. 13731386, 2008.
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. 935939.
Yenisey, M. M., & Yagmahan, B. “Multiobjective permutation flow shop scheduling problem: Literature review, classification and current trends.” Omega, vol. 45, pp. 119135, 2014.
K. R Baker. Introduction to sequencing and scheduling. New York : wiley, 1974.
AHG Rinnoy and Kan. Machine Scheduling Problems: Classification, Complexity and Computations. The Hague: Martinus Nijhoff, 1976.
Yoshida and Hitomi, “Optimal two stage production scheduling with set up times separated.” AIIETransactions, vol. II, pp. 261263, 1979.
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.
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. 463470.
E.G, Coffiman. Computer and job Scheduling Theory. New York: Wiley, 1976.
S.French. Sequencing And Scheduling:An Introduction to the Mathematics of the job shop. Chichester, UK: Ellis Horwood, 1982.
Garey, M. R., Johnson and D. S. Computers and Intractability: A Guide to the Theory of NPcompleteness. San Francisco: W.H. Freeman and Company, 1979.
Lomnicki, Z.A. “A branchandbound algorithm for the exact solution of the threemachine scheduling problem.” Operational Research Quarterly, vol. 16, pp.89100, 1965.
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. 16751677.
Osman I H and Potts C N, "Simulated annealing for permutation flowshop scheduling." Omega, vol. 17, pp. 551557. 1989.
Widmer, M. and Hertz, A. “A new heuristic method for the flow shop sequencing problem.” European Journal of Operational Research, vol. 41(2), pp. 186193, 1989.
Taillard, E. “Some efficient heuristic methods for the flow shop sequencing problem.” European journal of Operational research, vol. 47(1), pp. 6574, 1990.
Glass, C. A., Gupta, J. N. D., Potts and C. N. “Twomachine Flow Shop Scheduling with Missing Operations: Special Cases and Approximation Algorithms Preprint OR75.” Faculty of Mathematical Studies, University of Southampton, U.K, 1995.
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. 26272630, 1998.
Sadjadi, S. J., Aryanezhaad, M. B., Ziaee, M. “The general flowshop scheduling problem: mathematical models.” J. of app. sci., vol. 8(17), pp. 30323037, 2008.
Reeves, C. R. “A genetic algorithm for flowshop sequencing.” Computers & operations research, vol. 22(1), pp. 513, 1995.
Murata, T., Ishibuchi, H., & Tanaka, H. “Genetic algorithms for flowshop scheduling problems.” Computers & Industrial Engineering, vol. 30(4), pp. 10611071, 1996.
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.
Holland, J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
Nowicki, E., & Smutnicki, C. “A fast tabu search algorithm for the permutation flowshop problem.” European Journal of Operational Research, vol.91(1), pp.160175, 1996.
BenDaya, M., & AlFawzan, M. “A tabu search approach for the flow shop scheduling problem.” European journal of operational research, vol. 109(1), pp. 8895, 1998.
Solimanpur, M., Vrat, P., Shankar, R. “A neurotabu search heuristic for the flow shop scheduling problem.” Comp. & Ope. Res., vol. 31, pp. 21512164, 2004.
Ignall, E., & Schrage, L. “Application of the branch and bound technique to some flowshop scheduling problems.” Operations research, vol. 13(3), pp. 400412, 1965.
Ladhari, T, Haouari, M, “A computational study of the PESP based on a tight lower bound.” Computers & Operations Research, vol. 32, pp. 18311847, 2005.
Refbacks
 There are currently no refbacks.

Comments on this article
by mr junior silva aleixo (20180315)
by Pedro Silva (20180322)
by Rafael Cardoso (20180326)
by jonas souza (20180402)
by weliton ghh silva gomes (20180410)