Volume 2 Issue 4 pp. 749-764 Fall, 2011


An improved sheep flock heredity algorithm for job shop scheduling and flow shop scheduling problems


Chandramouli Anandaraman


Job Shop Scheduling Problem (JSSP) and Flow Shop Scheduling Problem (FSSP) are strong NP-complete combinatorial optimization problems among class of typical production scheduling problems. An improved Sheep Flock Heredity Algorithm (ISFHA) is proposed in this paper to find a schedule of operations that can minimize makespan. In ISFHA, the pairwise mutation operation is replaced by a single point mutation process with a probabilistic property which guarantees the feasibility of the solutions in the local search domain. A Robust-Replace (R-R) heuristic is introduced in place of chromosomal crossover to enhance the global search and to improve the convergence. The R-R heuristic is found to enhance the exploring potential of the algorithm and enrich the diversity of neighborhoods. Experimental results reveal the effectiveness of the proposed algorithm, whose optimization performance is markedly superior to that of genetic algorithms and is comparable to the best results reported in the literature.


DOI: 10.5267/j.ijiec.2010.06.007

Keywords: Job shop scheduling, Flow shop scheduling, Sheep flock heredity algorithm Makespan
References

Araújo, D.C. & Nagano, M.S. (2011). A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem. International Journal of Industrial Engineering Computations, 2, 155-166.

Arun Vikram, M. S. & Chandramouli, A. (2011). An efficient evolutionary approach to compute optimal schedules for the Job Shop Scheduling Problem. Proceedings of National Conference on Innovations in Mechanical Engineering, 1, 218-224.

Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley.

Beasley, J.E. (1990). OR-library: Distributing test problems by electronic mail, Journal of Operations Research Society, 41(11), 1069–1072.

Beyer, H.G., Schwefel, H.P. & Wegener, I. (2002). How to analyze evolutionary algorithms. Technical Report No. CI-139/02, University of Dortmund.

Chandrasekaran, M., Asokan, P., Kumanan, S., Balamurugan, T., & Nickolas, S. (2005). Solving job shop scheduling problems using artificial immune system. International Journal of Advanced Manufacturing Technology, 31(5-6), 580-593.

Cheng, R., Gen, M. & Tsujimura, Y. (1996). A tutorial survey of jobshop scheduling problems using genetic algorithms – I. Representation. Computers and Industrial Engineering, 30, 983–997.

Fink, A., & Vob, S. (2003) Solving the continuous flow shop scheduling problem by metaheuristic. European Journal of Operational Research, 151, 400–414.

Fisher, H. & Thompson, G. L. (1963). Industrial scheduling. Englewood Cliffs, NJ: Prentice-Hall.

French, S. (1982). Sequencing and scheduling: An introduction to the mathematics of the job shop. Chichester, West Sussex, E. Horwood.

Garey, M., Johnson, D., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117–129.

Giffler, B., & Thompson, G. L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8(4), 487–503.

Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison Wesley.

Goncalves, J.F., Mendes, J.J.D.M. & Resende, M.G.C. (2005). A hybrid genetic algorithm for the jobshop scheduling problem. European Journal of Operational Research, 167, 77–95.

Grefenstette, J.J. (1988). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, 16(1), 122–128.

Kuo, I.H., Horng, S.H., Kao, T.W., Lin, T.L., Lee, C.L., Terano, T., & Pan, Y. (2009). An efficient flow-shop scheduling algorithm based on hybrid particle swarm optimization model. Expert Systems with Applications, 36, 7027-7032.

Koichi Nara, Tomomi Takeyama & Hyunchul Kim. (1999). A New Evolutionary Algorithm Based on Sheep Flocks Heredity Model and Its Application to Scheduling Problem. IEEE Transactions, VI, 503-508.

Lawrence, S. (1984). Resource constraint project scheduling: An experimental investigation of heuristic scheduling techniques. Graduate School of Ind. Admin.. Carnegie Mellon University, Tech. Rep.

Leung, Y., Gao, Y. & Xu, Z.B. (1997). Degree of population diversity – a perspective on premature convergence in genetic algorithms and its markov-chain analysis. IEEE Transactions on Neural Networks, 8(5), 1165–1176.

Lin, T.L., Horng, S.J. Kao, T.W., Chen, Y.H., Run, R.S., Chen, R.J., Lai, J.L. & Kuo, I.H. (2010), An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications, 37, 2629–2636.

Rees, J. & Koehler, G. J., (2006). Learning genetic algorithm parameters using hidden Markov models. European Journal of Operational Research, 175 (2), 806–820.

Rudolph, G. (1994). Convergence properties of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5(1), 96– 101.

Rui Zhang & Cheng Wu. (2010). A hybrid immune simulated annealing algorithm for the job shop scheduling problem. Applied Soft Computing, 10, 79–89.

Sayadi, M.K., Ramezanian, R. & Ghaffari-Nasab, N. (2010). A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 1, 1-10.

Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problems. European Journal of Operational Research, 47, 65–74.

Wang, L., Zhang, L., & Zheng, D. Z. (2006). An effective genetic algorithm for flow shop scheduling with limited buffers. Computers & Operations Research, 33, 2960–2971.

Wang, L. & Tang, D.B. (2011). An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem. Expert Systems with Applications, 38, 7243–7250.

Wang, L., Pan, Q.K. & Tasgetiren, F. M. (2011). A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Computers and Industrial Engineering, 66(1), 76-83.

Wiers, V. C. S. (1997). A review of the applicability of OR and AI scheduling techniques in practice. Omega- International Journal of Management Science, 25(2), 145-153.

Yang, R. & Donglas, I. (1998). Simple genetic algorithm with local turning-efficient global optimizing technique. Journal of Optimization Theory and Applications, 98(2), 449–465.

Zhang, C., Ning, J. & Ouyang, D. (2010). A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Computers and Industrial Engineering, 58, 1-11.