Volume 1 Issue 1 pp. 1-10 July, 2010


A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems,


 Mohammad Kazem Sayadi, Reza Ramezanian and Nader Ghaffari-Nasab


During the past two decades, there have been increasing interests on permutation flow shop with different types of objective functions such as minimizing the makespan, the weighted mean flow-time etc. The permutation flow shop is formulated as a mixed integer programming and it is classified as NP-Hard problem. Therefore, a direct solution is not available and meta-heuristic approaches need to be used to find the near-optimal solutions. In this paper, we present a new discrete firefly meta-heuristic to minimize the makespan for the permutation flow shop scheduling problem. The results of implementation of the proposed method are compared with other existing ant colony optimization technique. The preliminary results indicate that the new proposed method performs better than the ant colony for some well known benchmark problems.


DOI: 10.5267/j.ijiec.2010.01.001

Keywords: Meta-heuristic, Firefly meta-heuristic, Ant colony, Permutation flow shop, Scheduling, Combinatorial optimization, Mixed integer programming

References

Demirkol, E., Mehta, S., & Uzsoy, R. (1998). Benchmarks for shop scheduling problems, European Journal of Operational Research, 109, 137–141.

Dong, X., Huang, H., & Chen, P. (2009). An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion, Computers & Operations Research, 36, 1664 -1669.

Farahmand Rad, S., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops, Omega, 37, 331 – 345

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

Johnson, S., 1954. Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61.

Lian, Z., Gu, X., & Jiao, B. (2006). A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan, Applied Mathematics and Computation, 175, 773–785.

Lukasik, S., & Zak, S. (2009). Firefly algorithm for continuous constrained optimization task, ICCCI 2009, Lecture Notes in Artificial Intelligence (Eds. N. T. Ngugen, R. Kowalczyk, S. M. Chen), 5796, 97-100.

Naderi, B. & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem, Computers & Operations Research, 37, 754 – 768.

Pinedo, M. (2002). Scheduling: Theory, Algorithms and Systems, 2nd ed. Prentice-Hall, Englewood Cliffs, NJ.

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.

Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479–494.

Ruiz, R., & Stutzle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 2033–2049.

Tasgetiren, M. F., Liang, Y-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research, 177, 1930–1947.

Turner, S., & Booth, D. (1987). Comparison of heuristics for flow shop sequencing, Omega, 15 (1), 75–78.

Vallada, E. & Ruiz, R. (2009). Cooperative metaheuristics for the permutation flowshop scheduling problem, European Journal of Operational Research, 193- 365–376.

Vallada, E., & Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem, Omega , 38 , 57 -67.

Yang, X-S. (2008). Nature-Inspired Metaheuristic Algorithm. Luniver Press.

Yang, X-S. (2009). Firefly algorithms for multimodal optimization, in: Stochastic Algorithms: Foundations and Applications, SAGA, Lecture Notes in Computer Sciences, 5792, 169-178.

Ying, K.-C., & Lin, S.-W. (2007). Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems, International Journal of Advanced Manufacturing Technology, 33, 793–802.