Share
مسائل جدولة الماكنة باستخدام الطرائق التامة وطرائق البحث المحلي == Single Machine Scheduling Proble ms By Using Exact and Local Search Methods
Author name:
زينب محروز علي
Supervisor name:
طارق صالح عبد الرزاق
General topic:
Mathematics
Specific topic:
Mathematics
Degree:
Master
University:
Mustansiriyah University - College Of Science - Department Of Mathematics
Language:
English
University location:
Baghdad
First pages:
27T1145 - p.pdf
Abstract:
في هذه الرسالة العمل الرئيسي هو تصغير دالة لثلاثة معايير والحاصلة من جدولة n من الاعمال على ماكنة واحدة.ولقد درست المسائل التالية : - 1 - تصغير الدالة لمجموع اوقات الاتمام , مجموع التاخير اللا سالب واكبر تاخير لا سالب.2 - تصغير الدالة لمجموع اوقات الاتمام , مجموع التبكير واكبر تبكير.في المسالة الاولى والمسائل الخاصة منها , اقترحنا بعض الخوارزميات لايجاد افضل حلول ممكنة في حالة المسائل الهرمية.واستخدمت طريقة التفرع والتقيد للمسالة 1//(∑Ci +∑Ti +Tmax).ايضا اقترحنا مع المقارنة خوارزميتان احدهما تعتمد على خوارزمية التفرع والتقيد لايجاد مجموع الحلول الكفؤة (غير المهيمن عليها) للمسالة 1//(∑Ci ,∑Ti ,Tmax) .وفي المسالة المتعددة الاهداف الثانية 1//(∑Ci ,∑Ei ,Emax) والمسائل الخاصة منها , اقترحنا في دراستنا بعض الخوارزميات لايجاد افضل حلول ممكنة في حالة المسائل الهرمية. وايضا طرائق البحث المحلية استخدمت للمسالة 1//(∑Ci +∑Ei +Emax) لايجاد حلول قريبة من الحل الامثل باستخدام خوارزمية مقترحة (AEP) والطرائق المحلية هي (Descent (D) and Simulated Annealing (SA) algorithms).وفي الفصل الاخير من هذه الرسالة , تم دراسة العلاقة بين المسالتين المتعددة الاهداف الاولى والثانية ثم استخدمنا طريقة العد التام لمقارنة الحلول الكفؤة لاهداف المسالتين. وايضا اخذنا بنظر الاعتبار المسالة (ETP) لتصغير دالة لخمسة معايير كلفة والحاصلة من جدولة n من الاعمال على ماكنة واحدة. النتائج الحسابية للمسالتين تعتمد كثيرا على سلوك المعيار الواحد للمسالة على ماكنة واحدة.ايداء كل الخوارزميات المقترحة تم اختيارها على مجموعة من الحالات لمسالة التاخير ومسالة التبكير. النتائج الحسابية تبين ان الخوارزميات المقترحة لحل مسالة الجدولة متعددة الاهداف وعندما يكون عدد الاهداف k=3 تعطي النتائج الاصلية والتي حصل عليها الباحثين عندما k=2. النتيجة الرئيسية في هذه الرسالة هي اذا كان بالامكان ايجاد مجموعة الحلول الكفؤة لمسالة جدولة متعددة الاهداف ولk من المعايير فانه يمكن ايجاد الحلول الكفؤة لمسالة متعددة الاهداف وبعدد اقل من المعايير من k في المسالة الاصلية. | In this thesis, the main work is to minimize a function of three cost criteria for scheduling n jobs on a single machine. The following problems are discussed : 1 - Minimizing a function of total completion times, total tardiness and maximum tardiness.2 - Minimizing a function of total completion times, total earliness and maximum earliness.In the first problem and its special cases problems, we propose some algorithms to find best possible solutions for hierarchical cases. A branch and bound (BAB) algorithm is applied for the 1//∑Ci+∑Ti+Tmax problem. Also we propose and compare two multiobjective algorithms one of them is based on (BAB) algorithm to find the set of efficient (non dominated) solutions for the 1//(∑Ci,∑Ti ,Tmax) problem.For the second multicriteria problem 1//(∑Ci,∑Ei ,Emax) and its special cases problems, we propose some algorithms to find the best possible solutions for the hierarchical cases. Also Local search methods is used for the 1//∑Ci+ ∑Ei +Emax problem to find near optimum solutions by using the proposed algorithm (AEP), and local search (Descent and Simulated Annealing ) methods. The last chapter, we study the relation between the first and second multicriteria problems and then we use CEM to compare the efficient solutions for the two objectives of the two problems. Also we consider the problem (ETP) to minimize a function of five cost criteria for scheduling n jobs on a single machine. The results for the two problems are largely based on the behavior of the single criterion problem on the single machine. The performance of all the proposed algorithms is tested on a set of instances of the tardiness problem and the earliness problem. The computational results show that the proposed algorithms for solving multicriteria scheduling problem (MSP) with (k=3) criterion yields the original results given by the researcher for (MSP) with (k=2). The main result of this thesis is that if we can find the set of efficient solutions for (MSP) with k criterion, then we can find the efficient solutions for (MSP) with the same criteria and with number of criteria is less than k in the original problem.
