Friday , March 29 2024

Flexible Job-shop Scheduling Problems Resolution Inspired from Particle Swarm Optimization

Hela BOUKEF
LARA, École Nationale d’Ingénieurs de Tunis
BP 37, Le Belvédère 1002 Tunis, Tunisie

Mohamed BENREJEB
LARA, École Nationale d’Ingénieurs de Tunis
BP 37, Le Belvédère 1002 Tunis, Tunisie
LAGIS, École Centrale de Lille, Cité scientifique
BP 48, 59651 Villeneuve d’Ascq Cedex, France

Pierre BORNE
LAGIS, École Centrale de Lille, Cité scientifique
BP 48, 59651 Villeneuve d’Ascq Cedex, France

Abstract: A new algorithm inspired from particle swarm optimization method is successfully implemented for flexible job-shop work-shop optimization problems. Its efficiency for solving combinatory problems is comparable to the genetic algorithms one taking into account the Makespan criterion.

Keywords: Particle Optimization Method (SPO), Flexible Job-Shop Problem (FJSP), Makespan.

Hela Boukef graduated from “Institut Supérieur de Gestion de Tunis” in 2003 and obtained the Master of automatic and signal treatment in 2006 at the “Ecole Nationale d’Ingénieur de Tunis”. She is currently preparing the Ph.D. degree in automatic and computer science within the framework of LAGIS-EC-Lille and LARA-ENIT cooperation. Her research is related to optimization methods for discrete events systems, computer science and operational research.

Mohamed Benrejeb has obtained the Diploma of “Ingénieur IDN” (French “Grande Ecole”) in 1973, the Master degree of Automatic Control in 1974, the PhD in Automatic Control of the University of Lille in 1976 and the DSc of the same University in 1980. He is currently a full Professor at the Ecole Nationale d’Ingénieurs de Tunis and an invited Professor at the Ecole Centrale de Lille. His research interests are in the area of analysis and synthesis of complex systems based on classical and non conventional approaches.

Pierre Borne received the Master degree of Physics in 1967, the Masters of Electronics, of Mechanics and of Applied Mathematics in 1968. The same year he obtained the Diploma of “Ingénieur IDN” (French “Grande Ecole”). He obtained the PhD in Automatic Control of the University of Lille in 1970 and the DSc of the same University in 1976. He became Doctor Honoris Causa of the Moscow Institute of Electronics and Mathematics (Russia) in 1999, of the University of Waterloo (Canada) in 2006 and of the Polytechnic University of Bucarest (Romania). He is author or co-author of about 200 Journal articles and book chapters, and of 34 plenary lectures and of more than 250 communications in international conferences. He has been the supervisor of 68 PhD thesis and is author of 20 books. He is Fellow of IEEE and has been President of the IEEE/SMC society in 2000 and 2001. He is presently Professor “de classe exceptionnelle” at the Ecole Centrale de Lille and director of the French pluriformations national group of research in Automatic Control.

>>Full text
CITE THIS PAPER AS:
Hela BOUKEF, Mohamed BENREJEB, Pierre BORNE, Flexible Job-shop Scheduling Problems Resolution Inspired from Particle Swarm Optimization, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (3), pp. 241-252, 2008.

1. Introduction

The importance of scheduling has increased in recent years due to the growing consumer demand for variety, reduced product life cycles, changing markets with global competition and rapid development of new processes and technologies [Hu and al, 06].

Scheduling problems are part of strong combinatory optimization problems. Many applications, varying from metallurgy, chemistry, agro-food [Tangour, 06], [Tangour, 06] or pharmaceutical industries [Boukef and al, 06], [Boukef and al, 07] can be treated by using heuristics and metaheuristics for their resolution.

Among the used metaheuristics, simulated annealing [Kirkpatrick, 83], tabu search [Glover, 89], genetic algorithms [Holland, 75] and ant colony [Colorni and al, 91] proved their performances.

But nowadays, a new optimization method is being used and is given satisfying results. This method proposed by Kennedy and Eberhart [Kennedy and Eberhart, 95] is the Particle Swarm Optimization method.

In fact, in 1995, J. Kennedy and R. Eberhart, motivated by bird flocking observation, proposed a new algorithm for representing social behaviour of artificial agents and, then created the Particle Swarm Optimization (PSO). Since 2000, PSO has been growing rapidly [Liao and al, 07] and has been applied successfully to continuous nonlinear functions, neural networks [Van de Bergh and Engelbrecht, 00], etc.

The PSO functioning makes it classified among iterative methods (progressive approach of finding optimal solution) and stochastic ones. Its aim is to improve existing states by moving partially at random and partially according to some defined rules in order to reach the global solution [Clerc, 99].

Most of the research on PSO took into account continuous optimization problems but the studies on discrete ones and particularly on flow-shop [Lian and al, 06], [Lian and al, 06], [Lian and al, 07] and job-shop [Sha and Hsu, 06], [Xia and Wu, 05] scheduling problems are very few.

The principal scope took into account in these types of scheduling problems is the Makespan minimization, even if some authors are interested in total tardiness [Tasgetiren and al, 04].

The problem treated in this paper is dealing with flexible job-shop work-shop scheduling with Makespan optimization objective.

First, flexible job-shop problems are introduced. Next, particle swarm optimization method is presented and a new algorithm inspired from it is proposed for flexible job-shop scheduling problems. Three examples are, then, treated. The two first ones deal with mono-operation flexible job-shop problem and the third with multi-operation flexible job-shop problem. In the last part, a comparison between the obtained results and those issued from genetic algorithm method is proposed, proving, thus, the performance of this new method.

6. Conclusion

The results obtained by applying our algorithm inspired from particle swarm optimization method on flexible job-shop scheduling problems and illustrated with Gantt diagrams, show the effectiveness of this method which leads to a charge balance of operations on selected machines and a minimization of Makespan.

Comparing this method with genetic algorithms one allows us to validate the use of the PSO in the discrete case.

REFERENCES

  1. Boukef, H., Tangour F. and Benrejeb M., Sur la formulation d’un problème d’ordonnancement de type flow-shop d’ateliers de production en industries pharmaceutiques, Journées Tunisiennes d’Electrotechnique et d’Automatique, JTEA’06, Hammamet, 2006.
  2. Boukef, H., Benrejeb M. and Borne P., A proposed genetic algorithm coding for flow-shop scheduling problems, International Journal of Computers, Communications and Control, IJCCC, vol. 2, no. 3, 2007, pp. 229-240.
  3. Clerc, M., The swarm and the queen: towards a deterministic and adaptive Particle swarm optimization, IEEE Congress on Evolutionary Computation, vol. 3, 1999, pp. 1951-1957.
  4. Colorni, A., Dorigo M., Maniezzo V. and Trubian M., Distributed optimization by ant colonies , First European Conference on Artificial Life, Paris, 1991, pp. 134-142.
  5. Deroussi, L., Gourgand M., Kemmoe S. and Quilliot A., Discrete particle swarm optimization for the permutation flow-shop problem, 2006.
  6. Filip, F.G., Neagu G. and Donciulescu D.A., Job-Shop scheduling optimization in real- time production control, Elsevier Science Publishers, North Holland, 1983, pp. 395-403.
  7. Glover, F., Tabu search, part II, ORSA, Journal of Computing, vol. 2, 1989, pp. 24-32.
  8. Ho N. B., Tay J. C. and Lai E. M., An effective architecture for learning and evolving flexible job-shop schedules, European Journal of Operational Research, vol. 179, 2006, pp. 316–333.
  9. Holland, J.H., Adaptation in natural and artificial systems , University of Michigan Press, Michigan, 1975.
  10. Kennedy, J. and Eberhart R.C., Particle swarm optimization, IEEE International Conference on Neural Networks, Piscataway, 1995, pp. 1942-1948.
  11. Kirkpatrick, S., and Vecchi M.P., Optimization by simulated annealing, Science, vol. 220, 1983, pp. 671-680.
  12. Lian, Z., Jiao B. and Gu X., A similar particle swarm optimization algorithm for job-shop scheduling to minimize Makespan, Applied Mathematics and Computation, vol. 183, 2006, pp. 1008–1017.
  13. Lian, Z., Gu X. and Jiao B., A similar particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan, Applied Mathematics and Computation, no. 175, 2006, pp. 773–785.
  14. Lian, Z., Gu X. and Jiao B., A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan , Chaos, Solitons and Fractals, 2006, pp. 1-11.
  15. Liao, C. J., Tseng C. T. and Luarn P., A discrete version of particle swarm optimization for flow-shop scheduling problems, Computers & Operations Research, vol. 34, 2007, pp. 3099–3111.
  16. Liouane, N., Saad I. and Borne P., Ant system and fuzzy controller for multi-objective optimization of the flexible job-shop scheduling problems, Studies in Informatics and Control, vol. 16, no. 2, 2007, pp. 217-226.
  17. Mesghouni, K., Hammadi S. and Borne P., Production job-shop scheduling using genetic algorithms, Systems, Man and Cybernetics, IEEE International Conference, 1996.
  18. Mesghouni, K., Hammadi S. and Borne P., On modelling genetic algorithm for flexible job-shop scheduling problems, Studies in Informatics and Control, vol. 7, no. 1, 1998, pp. 37-47.
  19. Saad, I., Boukef H. et Borne P., The comparative of criteria aggregative approach for the multi-objective optimization flexible job-shop scheduling problems, Fourth Conference on Management and Control of Production and Logistics, MCPL, Sibiu, 2007.
  20. Saad, I., Hammadi S., Benrejeb M.and Borne P., Choquet integral for criteria aggregation in the flexible job-shop scheduling problems, IMACS Intenational Journal, Mathematics and Computers in Simulation, MATCOM, Elsiver, vol. 76, 2008, pp. 447-462.
  21. Sha, D. Y. and Hsu C. Y., A hybrid particle swarm optimization for job shop scheduling problem, Computers and Industrial Engineering, vol. 51, 2006, pp. 791–808.
  22. Shelokar, P.S., Siarry P., Jayaraman V. K. and Kulkarni B. D., A Particle swarm and ant colony algorithms hybridized for improved continuous optimization, Applied Mathematics and Computation, vol. 188, 2007, pp.129-142.
  23. Shi, X.H., Lianga Y.C., Leeb H.P., Lub C. and Wang Q.X., Particle swarm optimization-based algorithms for TSP and generalized TSP, Information Processing Letters, vol. 103, 2007, pp. 169-176.
  24. Tangour, F. and Saad I., Multi-objective optimization scheduling problems by pareto-optimality in agro-alimentary workshop, International Journal of Computers Communication & Control, IJCCC, vol. 1, no. 3, 2006, pp. 71-83.
  25. Tangour, F. and Borne P., Ordonnancement des opérations dans un atelier de production agroalimentaire en minimisant le coût, Revue e-Sta, vol. 3, no. 1, 2006.
  26. Tasgetiren, M., Sevkli M., Liang Y. C. and Gencyilmaz G., Particle Swarm Optimization Algorithm for Single Machine Total Weighted Tardiness Problem, IEEE, Digital Object Identifier, vol. 2, 2004, pp. 1412-1419.
  27. Van den Bergh, F. and Engelbrecht A.P., Cooperative learning in neural network using particle swarm optimizers, South African Computer Journal, vol. 26, 2000, pp. 84-90.
  28. Xia, W. and Wu Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers and Industrial Engineering, vol. 48, 2005, pp. 409-425.