Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # NOM1 Prénom1 - NOM2 Prénom2
- using JuMP, GLPKMathProgInterface # On va utiliser JuMP et GLPK
- # Structures contenant les données d'un problème de bin-packing mono-dimensionnel
- struct objet1D
- taille::Int64 # Taille de l'objet
- nb::Int64 # Nombre d'objets de la même taille
- end
- struct donnees1D
- T::Int64 # Taille d'un bin
- nb::Int64 # Nombre de taille d'objets différents
- tab::Vector{objet1D} # Tableau des objets à insérer dans les bins
- end
- # Structures contenant les données d'un problème de bin-packing bi-dimensionnel
- struct objet2D
- l::Int64 # Largeur de la pièce
- h::Int64 # Hauteur de la pièce
- nb::Int64 # Nombre d'objets dans ce format
- end
- struct donnees2D
- L::Int64 # Largeur d'un bin
- H::Int64 # Hauteur d'un bin
- nb::Int64 # Nombre de types d'objet différents
- tab::Vector{objet2D} # Tableau des objets à insérer dans les bins
- end
- # Fonction prenant en entrant un nom de fichier et retournant les données du problème
- function parser_data1D(nomFichier::String)
- # Ouverture d'un fichier en lecture
- f = open(nomFichier,"r")
- # Lecture de la première ligne pour connaître la taille d'un bin et le nombre de tailles différentes pour les objets à ranger
- s::String = readline(f) # lecture d'une ligne et stockage dans une chaîne de caractères
- ligne::Vector{Int64} = parse.(Int64,split(s," ",keepempty = false)) # Segmentation de la ligne en plusieurs entiers, à stocker dans un tableau
- T::Int64 = ligne[1]
- nb::Int64 = ligne[2]
- # Allocation mémoire pour le tableau des objets
- tab = Vector{objet1D}(undef,nb)
- # Lecture des infos sur les objets (sur chaque ligne : taille + nombre)
- for i in 1:nb
- s = readline(f)
- ligne = parse.(Int64,split(s," ",keepempty = false))
- tab[i] = objet1D(ligne[1],ligne[2])
- end
- # Fermeture du fichier
- close(f)
- # Retour des donnees
- return donnees1D(T,nb,tab)
- end
- # Fonction prenant en entrant un fichier et retournant les données du problème
- function parser_data2D(nomFichier::String)
- # Ouverture d'un fichier en lecture
- f = open(nomFichier,"r")
- # Lecture de la première ligne pour connaître la largeur et la hauteur d'un bin et le nombre de types d'objets différents à ranger
- s::String = readline(f) # lecture d'une ligne et stockage dans une chaîne de caractères
- ligne::Vector{Int64} = parse.(Int64,split(s," ",keepempty = false)) # Segmentation de la ligne en plusieurs entiers, à stocker dans un tableau
- L::Int64 = ligne[1]
- H::Int64 = ligne[2]
- nb::Int64 = ligne[3]
- # Allocation mémoire pour le tableau des objets
- tab = Vector{objet2D}(undef,nb)
- # Lecture des infos sur les objets (sur chaque ligne : largeur + hauteur + nombre)
- for i in 1:nb
- s = readline(f)
- ligne = parse.(Int64,split(s," ",keepempty = false))
- tab[i] = objet2D(ligne[1],ligne[2],ligne[3])
- end
- # Fermeture du fichier
- close(f)
- # Retour des donnees
- return donnees2D(L,H,nb,tab)
- end
- #Heuristique Best-fit
- function best_fit(data::donnees1D)
- tab_bin = [0]
- sort!(data.tab, by = x -> x.taille, rev=true)
- for i in 1:data.nb
- for j in 1:data.tab[i].nb
- for k in 1:size(tab_bin,1)
- if (tab_bin[k] + data.tab[i].taille <= 30)
- tab_bin[k] += data.tab[i].taille
- sort!(tab_bin, rev=true)
- elseif (k == size(tab_bin, 1))
- push!(tab_bin, data.tab[i].taille)
- end
- end
- end
- end
- return size(tab_bin, 1)
- end
- function modelImplicite(solverSelected, data::donnees1D, tailleBin::Int64, nbBin::Int64)
- m = Model(solver = solverSelected)
- @variable(m, x[1:28,nbBin], Bin) #obj i rangé dans bin j
- @variable(m, y[1:nbBin], Bin) #si obj dans bin j
- @objective(m, Min, sum(y[j] for j in 1:nbBin))
- @constraint(m, obligRange, sum((x[i,j] for j in 1:nbBin) for i in 28) == 1)
- @constraint(m, limiteTaille, (sum(t[i]x[i,j] for i in 1:28)) <= (tailleBin * y[j] for j in 1:nbBin))
- return m
- end
- data = parser_data1D("A4.dat")
- tailleBin = data.T
- #nbObj = sum(data.tab[i,2] for i in 1:data.nb)
- nbBin = best_fit(data)
- m = modelImplicite(GLPKSolverMIP(),data, tailleBin, nbBin)
- status = solve(m)
- if status == :Optimal
- println("Problème résolu à l'optimalité")
- println("z = ",getobjectivevalue(m)) # affichage de la valeur optimale
- println("nbBin = ",getvalue(nbBin))
- elseif status == :Unbounded
- println("Problème non-borné")
- elseif status == :Infeasible
- println("Problème impossible")
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement