A Scatter Search Approach for Optimization of Makespan and Total Flow Time in Flow Shop Scheduling
Keywords:
Optimization, flow time, makespan, Scatter Search, Meta- heuristic, Scheduling, Flow shopAbstract
In many real-world scheduling problems several criteria must be considered simultaneously for evaluating the quality of the solution or schedule. Traditionally, these problems have been tackled as single-objective optimization problems after combining the multiple criteria into a single scalar value. A number of multi objective meta-heuristics have been proposed in recent years to obtain sets of compromised solutions for multi objective optimization problems. Most of these techniques have been successfully tested in both benchmark and real-world multi objective problems. This paper proposes a new heuristic i.e, Scatter search for minimizing the make span and total flow time to a flow shop problem. Scatter Search (SS) is applied to this problem as it is able to provide a wide exploration of the search space through intensification and diversification. In addition it has a unifying principle for joining solutions and they exploit adaptive memory principle to avoid generating or incorporating duplicate solutions at various stages of the problem. This paper initially addresses the general method of finding the make span and the total flow time. Scatter search algorithm is presented and applied to the given manufacturing environment and the corresponding steps are presented. The proposed scatter search algorithm is applied to a number of multi machine and multi job combination using proper coding and the results of the experimental investigation are presented.
Downloads
References
Glover F, Laguna M, Marti R. (2000), “Fundamentals of scatter search and path relinking”. Control and Cybernetics. 29(3): 653–684.
Widmer M, Hertz A. (1989), “A new heuristic method for the flow shop sequencing problem”. European Journal of Operational Research 41:186–93.
Pinedo M. (1995), “Scheduling: theory, algorithm, and system”. Englewood Cliffs, NJ: Prentice-Hall,
Johnson SM. (1954), “Optimal two- and three-stage production schedules with setup times included”. Naval Research Logistics Quarterly; 1(1):61–8.
Lomnicki ZA. (1965), “A branch and bound algorithm for the exact solution of the three-machine scheduling problem”. Operational Research Quarterly; 16(1):89–100.
Osman IH, Potts CN (1989). “Simulated annealing for permutation flow-shop scheduling”. OMEGA, International Journal of Management Science; 17:551–7.
Palmer DS (1965). “Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum”. Operational Research Quarterly; 16(1):101–7
Campbell HG, Dudek RA, Smith ML. (1970) “A heuristic algorithm for the n-job, m-machine sequencing problem”. Management Science 16(B): 630–7.
Gupta JND. (1971) “A functional heuristic algorithm for the flow shop scheduling problem”. Operational Research Quarterly; 22(1):39–47.
Dannenbring DG. (1977), “An evaluation of flow shop sequencing heuristics”. Management Science 23(11): 1174–82.
Rock H, Schmidt G. (1982), “Machine aggregation heuristics in shop scheduling”. Methods of Operations Research; 45: 303–14.
Nawaz, M., Enscore, J.E.E., Ham, I. (1983), “A heuristic algorithm for the m-machine, n-job flow shop sequencing problem”. OMEGA: International Journal of Management Science 11 (1), 91–95.
cTurner S, Booth D. (1987), “Comparison of heuristics for flow shop sequencing”.OMEGA : International Journal of Management Science; 15:75–8.
Taillard E. (1990), “Some efficient heuristic methods for the flow shop sequencing problem”. European Journal of Operational Research; 47:65–74.
Ho J C, Chang Y L. (1990), “A new heuristic for the n-job, m-machine flow shop problem”. European Journal of Operational Research; 52:194–206.
Ogbu FA, Smith DK. (1990), “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flow shop problem”. Computers and Operations Research; 17:243–53.¬
Nowicki E, Smutnicki C. (1996), “A fast tabu search algorithm for the permutation flow shop problem”. European Journal of Operational Research; 91:160–175.
Ben-Daya M, Al-Fawzan M. (1998), “A tabu search approach for the flow shop scheduling problem”. European Journal of Operational Research 109:88–95.
Goldberg DE. (1989.), “Genetic algorithms in search, optimization and machine learning. Reading”. MA: Addison-Wesley.
Holland JH. (1975), “Adaptation in natural and artificial systems”. Ann Arbor: The University of Michigan Press.
Van Laarhoven PJM, Aarts EHL. (1987), “Simulated annealing: theory and applications”. Dordrecht: D. Reidel Publ. Co.,
Metropolis N, Rosenbluth A,Rosenbluth M,Teller A,Teller E(1953),“Equation of state calculation by fast computing machine”. Journal of Chemical Physics; 21:1087–92.
Glover, F. and M. Laguna. (1997), “Tabu Search”. Kluwer Academic Publishers.
Eugeniusz Nowicki, Czeslaw Smutnicki (2006),”Some aspects of scatter search in the flow-shop problem”,European Journal of Operational Research 169 ,654–666
Stutzle, T., (1998). “Applying iterated local search to the permutation flow shop problem”. Technical Report, AIDA-98-04,FG Intellektik,TU Darmstadt.
Ruben Ruiz, Concepcion Maroto (2005), “A comprehensive review and evaluation of permutation flowshop heuristics”,European Journal of Operational Research, 165, 479–494
Taillard E. (1993), “Benchmarks for basic scheduling problems”. European Journal of Operational Research. 64,278–285.
Chen, C.-L., Vempati, V.S., Aljaber, N., 1995. “An application of genetic algorithms for flow shop problems”. European Journal of Operational Research 80, 389–396.
Reeves, C., Yamada, T., 1998. “Genetic algorithms, path relinking, and the flowshop sequencing problem”. Evolutionary Computation 6 (1), 45–60.
Murata, T., Ishibuchi, H., Tanaka, H., 1996. “Genetic algorithms for flowshop scheduling problems”. Computers and Industrial Engineering 30 (4), 1061–1071.
Ponnambalam, S.G.,Aravindan, P., Chandrasekaran, S., 2001.”Constructive and improvement flow shop scheduling heuristics:An extensive evaluation”. Production Planning and Control, 12 (4), 335–344.
Reza hejazi.S and. Saghafian. S (15 July 2005),”Flowshop-scheduling problems with makespan criterion: a review”, International Journal of Production Research,Vol. 43, No. 14, , 2895–2929.
Rajendran C. and Ziegler H. (2004) ‘Ant-colony algorithms for permutation flow shop scheduling to minimize makespan/total flow time of jobs’, European Journal of Operational Research, Vol. 155,pp.426-438.
Rajendran C. and Ziegler H. (1997) ‘An efficient heuristic for scheduling in a flow shop to minimize total weighted flow time of jobs’, European Journal of Operational Research, 103,pp.129–138..
vVaradharajan T.K. and Chandrasekharan Rajendran (2005) “A multi-objective simulated-annealing algorithm for scheduling in flow shops to minimize the makespan and total flowtime of jobs.” European journal of operational research, Vol. 167, no. 3 pp. 772-795.
Rajendran C.and Ziegler H. (1997), “A heuristic for scheduling to minimize the sum of weighted flow time of jobs in a flow shop with sequence-dependent setup times of jobs”, Computers & Industrial Engineering,Vol. 33, Issues 1-2, Pp. 281-284.
Chandrasekharan Rajendran (1991), “A Flow shop Scheduling Algorithm to Minimize Total Flow time”, Journal of Operations Research Society of Japan, Vol. 34, No. 1, pp 28 - 46.
Chandrasekharan Rajendran and Hans Ziegler,(2004), “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs”. European Journal of Operational Research,Vol. 155, Issue 2, 2004, Pp. 426-438.
Rajendran C. (1992) Two-stage flow shop scheduling problem with bi criteria. Journal of the Operational Research Society, 43, pp.871–884.
nRajendran C. (1995) ‘Heuristics for scheduling in flow shop with multiple objectives.’ European Journal of Operational Research 82, pp.540–555.
Tasgetiren, M. Fatih & Liang, Yun-Chia & Sevkli, Mehmet & Gencyilmaz, Gunes, (2007),"A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, Elsevier, vol. 127(3), pp.1930-1947.
Noorul haq A., and Saravanan M., Vivekraj A.R. and Prasad T. (2007) ‘A scatter search algorithm for general flow shop scheduling problem’, International journal of Advanced manufacturing Technology, 31,731-736.
vNoorul haq A. and Saravanan M. (2007) ‘A Scatter Search Approach for minimizing Earliness and Tardiness Penalties in single machine scheduling around large restrictive Common Due Windows’, International journal of Applied Management and Technology, vol.5,No.2,pp. 76-91.
Saravanan M and Noorul haq A. (2007) ‘Evaluation of Scatter Search Approach for Scheduling Optimization of Flexible Manufacturing Systems’, International journal of Advanced manufacturing Technology. - Published in online (August 3, 2007).
Saravanan M and Noorul haq A. Vivekraj A.R. and Prasad T. (2007) ‘Performance Evaluation of Scatter Search Method for Permutation Flow-Shop Sequencing Problems’, International journal of Advanced manufacturing Technology. - Published in online (June15, 2007).
Noorul haq A. and Saravanan M. (2007) ‘Evaluation of Scatter Search Approach for Minimizing Earliness and Tardiness Penalties in Single Machine Scheduling’, Accepted for Publication in International journal of manufacturing Science and Technology.
Saravanan M and Noorul haq A, ‘A Scatter Search Method to Minimize Makespan of Cell Scheduling Problem’, Accepted for publication in International Journal of Agile Systems and Management.
Saravanan M and Noorul haq A, ‘A Scatter Search Algorithm for Scheduling Optimisation of Job Shop Problems’, Accepted for publication in International Journal of Product Development.
