A Proposed Genetic Algorithm Coding for Flow-Shop Scheduling Problems

  • Hela Boukef Ecole Nationale d’Ingénieurs de Tunis Unité de recherche LARA-Automatique BP 37, Le Belvédère, 1002 Tunis, Tunisie 2Ecole Centrale de Lille, Cité scientifique Laboratoire d’Automatique, Genie Informatique et Signal BP 48, 59651 Villeneuve d’Ascq Cedex, France
  • Mohamed Benrejeb Ecole Nationale d’Ingénieurs de Tunis Unité de recherche LARA-Automatique BP 37, Le Belvédère, 1002 Tunis, Tunisie
  • Pierre Borne Ecole Centrale de Lille, Cité scientifique Laboratoire d’Automatique, Genie Informatique et Signal BP 48, 59651 Villeneuve d’Ascq Cedex, France

Abstract

A new genetic algorithm coding is proposed in this paper to solve flowshop scheduling problems. To show the efficiency of the considered approach, two examples, in pharmaceutical and agro-food industries are considered with minimization of different costs related to each problem as a scope. Multi-objective optimization is thus, used and its performances proved.

References

[1] P. Baptiste and C. Le Pape " A constraint-Based Branch and Bound Algorithm for Preemptive Job- Shop Scheduling ". 5th IEE, International Symposium on Assembly and Task Planning, Besançon, 1996.

[2] H. Boukef, F. Tangour et M. Benrejeb " 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.

[3] J.L. Bouquard, J.C. Billaut, M.A. Kubzin and V.A. Strusevich " Two-machine flow-shop scheduling problems with no-wait jobs ". Operations Research Letters, vol.33, pp. 255-262, 2004.
http://dx.doi.org/10.1016/j.orl.2004.06.003

[4] J. Breït " A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint ". Computers and Operations Research, vol.33, pp. 2143–2153, 2005.
http://dx.doi.org/10.1016/j.cor.2005.01.004

[5] Y. Collette et P. Siarry " Optimisation Multiobjectif ". Editions Eyrolles, Paris, 2002.

[6] A. Colorni, M. Dorigo, V. Maniezzo and M. Trubian " Distributed optimization by ant colonies ". First European Conference on Artificial Life, Paris, pp. 134-142, 1991.

[7] C. Esswein, J.C. Billau, and V.A. Strusevich " Two-machine shop scheduling: Compromise between flexibility and makespan value ". European Journal of Operational Research, vol.167, pp. 796–809, 2004.
http://dx.doi.org/10.1016/j.ejor.2004.01.029

[8] F.G. Filip, G. Neagu, and D. A. Donciulescu " Job-shop scheduling optimization in real-time production control ". Computers in Industry, vol. 4, pp. 395-403, 1983.
http://dx.doi.org/10.1016/0166-3615(83)90006-4

[9] E. Gargouri, S. Hammadi and P. Borne " A distributed scheduling for agro food manufacturing problems ". Journal of IEEE Transactions on Systems, Man and Cybernetics, vol.33, 2003.

[10] F. Glover " Tabu search, part II ". ORSA, Journal of Computing, vol.2, pp. 24-32, 1989.

[11] G.E. Goldberg " Algorithmes génétiques ". Editions Addison-wesley, France, 1994.

[12] J.K. Hao, P. Galinier et M. Habib " Métaheuristiques pour l'optimisation combinatoire et l'affectation sous contraintes ". Revue d'Intelligence Artificielle, pp. 2-39, 1999.

[13] J.H. Holland " Adaptation in natural and artificial systems ". PhD, Michigan Press Univ., Ann Arbor, MI, 1975.

[14] I. Kacem, S. Hammadi and P. Borne " Flexible job-shop scheduling problems: formulation, lowerbounds, encodings, and controlled evolutionary approach ". Computational Intelligence in Control, Idea Group Publishing, 2003.

[15] P.J. Kalczynski and J. Kamburowski " On no-wait and no-idle flow shops with makespan criterion". European Journal of Operational Research, vol.178, pp. 677–685, 2006.
http://dx.doi.org/10.1016/j.ejor.2006.01.036

[16] S. Kirkpatrick and M.P. Vecchi " Optimization by simulated annealing ". Science, vol.220, pp. 671-680, 1983.
http://dx.doi.org/10.1126/science.220.4598.671

[17] T. Loukil, J. Teghem and D. Tuyttens " Solving multi-objective production scheduling problems using metaheuristics ". European Journal of Operational Research, vol.161, pp. 42–61, 2003.
http://dx.doi.org/10.1016/j.ejor.2003.08.029

[18] E. Lutton " Etat de l'art des algorithmes génétiques ", INRIA, pp.137-140, 1994.

[19] M.H. Mabed, M. Rahoual, E.G. Talbi and C. Dhaenens " Algorithmes génétiques multicritères pour les problèmes de flow-shop ". 3ème Conférence Francophone de MOdélisation et de SIMulation, MOSIM'01, Troyes, pp. 843-849, 2001.

[20] K. Mesghouni, S. Hammadi and P. Borne " On modeling genetic algorithm for flexible job-shop scheduling problem ". Studies in Informatics and Control Journal, vol.7, pp. 37-47, 1998.

[21] A. Oulamara " Makespan minimization in a no-wait flow shop problem with two batching machines". Computers and Operations Research, vol.34, pp. 1033–1050, 2005.
http://dx.doi.org/10.1016/j.cor.2005.05.028

[22] I. Saad, S. Hammadi, P. Borne and M. Benrejeb " Aggregative Approach for the Multiobjective Optimization Flexible Job-Shop Scheduling Problems ". The IEEE International Conference on Service Systems and Service Management, IEEE-ICSSSM'06, pp. 889-894, Troyes, 2006.
http://dx.doi.org/10.1109/icsssm.2006.320738

[23] M. Sakarovitch " Graphes et Programmation Linéaire ". Edition Hermann, Paris, 1984.

[24] F. Tangour, S. Hammadi, P. Borne and M. Benrejeb " Ordonnancement dynamique dans un atelier de production agroalimentaire ". Séminaire d'Automatique-Industrie, SAI'06, Matmata, 2006.

[25] F. Tangour and I. Saad " Multiobjective optimization scheduling problems by Pareto-optimality in agro-alimentary workshop ". International Journal of Computers, Communications & Control, IJCCC, vol. I, no. 3, pp. 71-83, 2006.
http://dx.doi.org/10.15837/ijccc.2006.3.2296

[26] J. Yuan, A. Soukhal, Y. Chen and L. Lu " A note on the complexity of flow shop scheduling with transportation constraints ". European Journal of Operational Research, vol. 178, pp. 918–925, 2006.
http://dx.doi.org/10.1016/j.ejor.2005.08.034
Published
2007-09-01
How to Cite
BOUKEF, Hela; BENREJEB, Mohamed; BORNE, Pierre. A Proposed Genetic Algorithm Coding for Flow-Shop Scheduling Problems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 2, n. 3, p. 229-240, sep. 2007. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2356>. Date accessed: 29 sep. 2020. doi: https://doi.org/10.15837/ijccc.2007.3.2356.

Keywords

genetic algorithm, operations coding, flow-shop problems, multiobjective optimization, pharmaceutical industries, agro-food industries