الجدوله لمقاييس متعددة الاداء == Scheduling with Multiple Performance Measures
Author name:
علي عباس نعمان المالكي
Supervisor name:
طارق صالح عبد الرزاق
General topic:
Mathematics
Specific topic:
Mathematics
Degree:
Master
University:
Mustansiriyah University - College Of Education For Pure Sciences - Department Of Mathematics
Language:
English
University location:
Baghdad
First pages:
27T1169 - p.pdf
Abstract:
في هذه الرسالة تصغير دالة لمعياريين او ثلاثة والحاصلة من جدولة n من الاعمال على ماكنة واحدة . تم التركيزفي هذه الدراسة والاخذ بنظر الاعتبار على حالة التاخير اللاسالب والعمل المتاخر ووقت الاتمام الكلي . ونوقشت المسائل التالية : 1 . تصغير الدالة (Tmax+Vmax) . 2 .تصغيرالدالة ذات ثلاث معايير والتي تاخذ الصيغة Lex(Tmax+Vmax ,Σ■(n@i)Ci) وLex(Σ■(n@i)Ci , Tmax+Vmax ) . . (■(n@i)Ti + ■(n@i)Vi) تصغير الدالة .3 للمسالة الاولى اقترحنا خوارزمية التفرع والتقييد لايجاد الحل الامثل كذلك برهنا بعض الحالات الخاصة التي تؤدي الى الحل الامثل .كذلك اقترحنا خوارزمية (A) المطورة من خوارزمية لولر لحل المسالة وهذا قادنا الى ملاحظة مشجعه وهي ان اغلب النتائج الحسابية تؤدي الى الحل الامثل. كما واجرينا تجارب حسابية لطريقة التفرع والتقييد على مجموعة كبيرة لمسائل اختبارية. .للمسالة الثانية والتي هي تعميم للمسالة الاولى قمنا باستخدمنا قاعدة (SPT) وكذلك الخوارزمية (A) المطورة لايجاد افضل الحلول . للمسالة الثالثة اقترحنا خوارزمية التفرع والتقييد مع قيدين سفلي وقيد علوي الذي هو اصغر ثلاث قيود تقريبيه مقترحة لايجاد الحل كذلك برهنا بعض الحالات الخاصة واستخدمنا قواعد الهيمنة مع خوارزمية التفرع والتقييد لتحسين النتائج الحسابية لهذه المسالة. | This thesis intends, to minimize a function of two and three cost criteria for scheduling n jobs on a single machine. The study focuses on the case where Tardiness, late work and total Completion times are considered. The following problems are discussed 1. Minimizing a function of two criteria (Tmax+Vmax). 2.Minimizing a function of three criteria of the forms Lex(Tmax+Vmax,Σ■(n@i=1)Ci) and Lex(Σ■(n@i=1)Ci , Tmax+Vmax ). 3. Minimizing a function of two criteria (■(n@i=1)Ti + ■(n@i=1)Vi). For the first problem 1// Tmax+Vmax , a branch and bound algorithm are proposed to find optimal solution . Also, we proved some special cases for this problem which lead to optimal solution. An improved algorithm (A) for Lawler algorithm has been constructed for solving this problem, which leads to an interesting observation that the algorithm (A) will yield optimal solutions in all instances of the test problems. Also computational experience for the (BAB) algorithm is presented. For the second problem which is a generalization of the first problem we use either the SPT rule or modified algorithm (A) to find the best solutions. For the third problem we proposed a (BAB) algorithm with two lower bounds and upper bound which is the minimum of three heuristic methods .We proved some special cases which lead to the optimal solution . We used dominance rules with BAB algorithm to enhance the computational results for this problem
