Mémoires de Fin d’Etudes
Etablissement
Université de M’Sila - Mohamed Boudiaf
Affiliation
Institut d’Informatique
Auteur
MEHENNI, Tahar
Directeur de thèse
Mr Hocine BELOUADAH
Filière
Informatique:Programmation et Systéme
Diplôme
Magister
Titre
UTILISATION DES METAHEURISTIQUES POUR RESOUDRE UN PROBLEME D’ORDONNANCEMENT SUR MACHINE A CONTRAINTE DE RESSOURCE NON RENOUVELABLE
Mots clés
Mots clefs : ressource, métaheuristique, voisinage, branch-and-bound, relaxation lagrangienne, swapping, insertion, recherche locale, k-first strategy, recherche tabou Keywords : resource, metaheuristic, neighboorhood, branch-and-bound, Lagrangian relaxation, swapping, insertion, local search, k-first strategy, tabu search دیل، الإدراج، بحمحلي، استراتيجية قائمة الأوائل، البحث بالعزل.
Résumé
L’objet de cette thèse est la résolution des problèmes d’ordonnancement sur machine en présence d’une ressource non renouvelable (ou consommable). Chaque tâche nécessite une quantité de ressource pour qu’elle soit exécutée. Le problème consiste à trouver un ordonnancement qui minimise la somme pondérée des dates de fin d’exécution des tâches en satisfaisant la contrainte de ressource. Nous proposons deux métaheuristiques afin de résoudre ce problème. La première consiste à utiliser une recherche locale basée sur un voisinage obtenu par les techniques de séparation et évaluation. Deux bornes inférieures sont proposées pour permettre une évaluation de cette méthode. La seconde métaheuristique considérée est la recherche tabou qui utilise une liste taboue dynamique ainsi qu’une nouvelle technique de diversification basée sur l’utilisation d’une mémoire à long terme contenant les premières meilleures solutions non retenues lors de la recherche. Deux voisinages sont proposés pour évaluer l’efficacité de cette méthode. Enfin, nous effectuons une étude comparative des deux métaheuristiques utilisées afin de montrer leur efficacité dans la résolution de notre problème. This thesis addresses the single machine scheduling problem with non-renewable (consumable) resource constraints where the objective is to minimize the sum of weighted completion times. A job can be processed if a sufficient quantity of resource is available. We developed two metaheuristics to resolve this problem. The first one is a local search method, which is based on a truncated branch-andbound algorithm to find the neighbourhood. Two lower bounds are proposed in order to evaluate the best one embedded in the branch-and-bound search. The second metaheuristic is a tabu search using a dynamic tabu list and a new diversification strategy, called “k-first strategy”, which is based on a list of the kfirst best solutions not chosen in the neighbourhood search. The tabu search is evaluated with two structures of the neighbourhood. Finally we present computational experiments in order to show the efficiency of the proposed metaheuristics. تتمثل هذه المذآرة في طرح وحل مشكل جدولة إنجاز أشغال على ماآنة مفردة مع وجود مصدر غير قابل للتجدید (مستهلك) من أجل تصغير دالة إنهاء المواقيت المثقلة، حيث لا یمكن لأي شغل أن ینجز إلا بوجود آمية آافية متاحة من المصدر. من أجل حل هذا المشكل استخدمنا اثنين من الطرق التقریبية التي تدخل ضمن ما یسمى بالطرق الموجهة. الأولى هي طریقة البحث المحلي على أساس التفریع والحصر لإیجاد الجوار، وقد تم اقتراح برنامجين لحساب الحد الأدنى، یرتكز الأول على قاعدة سميث أما الثاني فيستعمل إرخاء لاقرانج، آما تم إجراء تقویم عليهما لأجل اختيار الأفضل الذي یعطي أحسن الحلول. أما الطریقة الثانية المقترحة فتسمى طریقة البحث مع العزل حيث تم استعمال قائمة دیناميكية للحلول المعزولة، آما اقترحنا تقنية جدیدة للتنویع ترتكز على إیجاد قائمة بأولى الحلول القریبة من الحل المتوفر والتي لم یتم اختبارها في عملية البحث. وقد تم تقویم هذه الطریقة باستعمال نوعين من الجوار هما الجوار بالتبدیل والجوار بالإدراج. وأخيرا تم إجراء اختبارات على الطریقتين المقترحتين لأجل اختيار التي تعطي أحسن الحلول للمشكل قيد الدراسة.
Date de soutenance
23/09/2006
Pagination
106
Format
pdf
Statut
Traitée