Probleme d'ordonnancement

Signaler
Messages postés
18
Date d'inscription
vendredi 24 février 2006
Statut
Membre
Dernière intervention
2 janvier 2008
-
Messages postés
170
Date d'inscription
jeudi 11 décembre 2003
Statut
Membre
Dernière intervention
24 janvier 2009
-
    Bonjour,
j'ai un fichier donnees_init que j'ai transféré dans un tableau donnees_init
Nom    M1      M2       M3    M4     M5
O11    1.50    9.50    3.12    4.91    4.50
O21    3.00    4.50    1.75    4.70    4.50
O31    4.50    7.00    1.75    4.50    3.75
O12    1.50    4.50    4.50    3.25    6.37
O22    1.50    8.25    4.91    4.50    3.75
O32    4.50    4.50    1.75    2.00    4.50
O13    1.50    4.50    4.91    3.25    3.00
O23    4.50    9.50    1.75    4.50    3.75
Oij représente la ième opération d'un produit j. Le passage des opérations Oij sur les machines doit se faire dans l'ordre, par exemple sur la machine 1, O12 doit passer obligatoirement avant O22, ...
J'ai défini deux structures :
Public Type position
       nom As String
       mach As Variant
       td_eff As Double
       tf_eff As Double
End Type

Public Type individu
        liste(nbre_op - 1) As position
        cmax As Double
        vit(nbre_op - 1) As Double
End Type

Le but est de creer une population d'individus respectant les contraintes d'ordre.

Voici ce que j'ai commencé à faire

Private Sub cmdcreer_Click()
Dim disp_mach(1 To nbre_mach) As Variant
Dim m, n, op, pr, op1, pr1 As Integer
Dim i, j, k As Integer
Dim nom1 As String
Dim nom2 As String
Dim nom3 As String
Dim nom4 As String
Dim pop1(nbre_pop) As individu
Dim pop2(nbre_pop) As individu
Dim pop3(nbre_pop) As individu
Dim tab_int(1) As Variant
Dim tab_int1(1) As Variant
Dim c1, c2, c3, c4, c5, c6, c As Integer
Dim tab_max(nbre_mach - 1) As Integer
Dim t1(nbre_job - 1) As Integer
'Dim tab_m1(nbre_mach - 1) As Integer
'Dim tab_m2(nbre_mach - 1) As Integer
'Dim tab_m3(nbre_mach - 1) As Integer
'Dim tab_m4(nbre_mach - 1) As Integer
'Dim tab_m5(nbre_mach - 1) As Integer

''''' Creation aléatoire de la population initiale '''''''''

For p = 0 To nbre_pop - 1

    For k = 1 To nbre_mach
        disp_mach(k) = 0
    Next k

    For i = 0 To nbre_op - 1
        For j = 0 To i
            rep = 0
            Randomize Timer
            n = Int((nbre_op * Rnd) + 1)
            m = Int((nbre_mach * Rnd) + 1)
            nom1 = donnees_init(n - 1, 0)
            nom2 = Left(nom1, 2)
            pr = Val(Right(nom1, 1))
            op = Val(Right(nom2, 1))

            For l = 0 To i
                nom3 = population_init(p).liste(l).nom
                nom4 = Left(nom3, 2)
                pr1 = Val(Right(nom3, 1))
                op1 = Val(Right(nom2, 1))
                If nom1 = nom3 Then
                    rep = 1
                End If
                If pr1 = pr Then
                    If op1 < op Then
                        m1 = Int((nbre_mach * Rnd) + 1)
                        If m1 = m And m1 < 5 Then
                            m1 = m1 + 1
                            m = m1
                        End If
                    End If
                End If
            Next l
            If rep = 0 Then
                Exit For
            End If
        Next j
        population_init(p).liste(i).nom = nom1
        population_init(p).liste(i).mach = m
        population_init(p).liste(i).td_eff = disp_mach(m)
        population_init(p).liste(i).tf_eff = population_init(p).liste(i).td_eff + donnees_init(j, m)
        disp_mach(m) = population_init(p).liste(i).tf_eff
    Next i
Next p

'''''''''' Determination du Cmax ''''''''''

For i = 0 To nbre_pop - 1
    Max = population_init(i).liste(0).tf_eff
    max1 = 0
    max2 = 0
    max3 = 0
    max4 = 0
    max5 = 0
   
    For j = 0 To nbre_op - 1
        If population_init(i).liste(j).mach = 1 Then
            c1 = population_init(i).liste(j).tf_eff
            If c1 > max1 Then
                max1 = c1
            End If
        ElseIf population_init(i).liste(j).mach = 2 Then
                c2 = population_init(i).liste(j).tf_eff
                If c2 > max2 Then
                    max2 = c2
                End If
           
        ElseIf population_init(i).liste(j).mach = 3 Then
                c3 = population_init(i).liste(j).tf_eff
                If c3 > max3 Then
                    max3 = c3
                End If
           
        ElseIf population_init(i).liste(j).mach = 4 Then
                c4 = population_init(i).liste(j).tf_eff
                If c4 > max4 Then
                    max4 = c4
                End If
           
        ElseIf population_init(i).liste(j).mach = 5 Then
                c5 = population_init(i).liste(j).tf_eff
                If c5 > max5 Then
                    max5 = c5
                End If
        End If
      
    Next j
   
tab_max(0) = max1
tab_max(1) = max2
tab_max(2) = max3
tab_max(3) = max4
tab_max(4) = max5
tab_max(5) = max6

c = 0
For k = 0 To nbre_mach - 1
    If tab_max(k) > c Then
        c = tab_max(k)
    End If
Next k

population_init(i).cmax = c

Next i

''''' Enregistrement de la population initiale ''''''''''
f2 = FreeFile
Open App.Path + "\population initiale.txt" For Output As #f2
For i = 0 To nbre_pop - 1
    Print #f2, "individu"; i
    For j = 0 To nbre_op - 1
    Print #f2, population_init(i).liste(j).nom, population_init(i).liste(j).mach, population_init(i).liste(j).td_eff, population_init(i).liste(j).tf_eff
    Next j
    Print #f2, "Cmax "; population_init(i).cmax
    Print #f2, " "
Next i
Close f2

End Sub

Je ne suis pas trés convaincue de mon raisonnement, un peu d'aide serait la bienvenue.
Merci

1 réponse

Messages postés
170
Date d'inscription
jeudi 11 décembre 2003
Statut
Membre
Dernière intervention
24 janvier 2009

Hello,

c'est un cas typique de problème qui se résolvent très naturellement avec les algorithmes génétiques.
Je te conseille la lecture attentive de cet article, qui contient tout ce qu'il fait pour faire une implémentation simple de cette méthode:
http://sis.univ-tln.fr/~tollari/TER/AlgoGen1/

Bon codage;

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/