Author name:
عدوية علي محمود النعيمي
Supervisor name:
طارق صالح عبد الرزاق
Abstract:
هذه الاطروحة مخصصة لمسائل جدولة متعددة المقاييس وعرضت بستة فصول.الفصلين الاول والثاني هي مقدمة وفيها مختلف المفاهيم لصيغ مسائل متعددة المقاييس وناقشنا طرائق الحل المعروفة لمسائل الجدولة وتحتوي الفصول الثلاثة البحث الاساسي على مختلف المقاييس لمسالة جدولة ماكنة واحدة.هذه الاطروحة تقدم نماذج رياضياتية وخوارزميات لايجاد الحلول الكفوءة، المثلى والتقريبية لمسائل جدولة متعددة المقاييس.استخدمنا تقنيات التفرع والتقيد لتصغير المقياسين : مجموع الاجزاء للاعمال المتاخرة (∑Vj) واعظم جزء لعمل متاخر (Vmax). هذه المسالة رمز لها 1//F(∑Vj,Vmax)، واقترحت خوارزمية كفوءة (ADA) لايجاد مجموعة حلول كفوءة لها. قدمت ايضا خوارزمية التفرع والتقيد (BAB) لايجاد حل امثل لمسالة تصغير الدالة الخطية ∑Vj+Vmax. الصعوبة للمسالة الاخيرة تقترح بانه ليس بالامكان دائما ايجاد حل امثل بسرعة. لذلك استخدمت خوارزميات بحث محلية (local search algorithms) وهي descent method (DM), simulated annealing (SA) algorithm and genetic algorithm (GA) لايجاد حلول قريبة من الحل الامثل وبزمن حسابي اقل.اقترحت خوارزمية كفوءة لايجاد الحلول الكفوءة لمسالة الماكنة الواحدة مع اوقات تحضير التي رمز لها 1/rj/F(Tmax,Vmax). قدمت ايضا خوارزمية التفرع والتقيد (BAB) لايجاد حل امثل لمسالة تصغير الدالة الخطية Tmax+Vmax مع اوقات تحضير. استخدمت لهذه المسالة ايضا خوارزميات بحث محلية (local search algorithms) لايجاد حلول تقريبية.درست مسائل جدولة متعددة المقاييس على ماكنة واحدة لايجاد مجموعة حلول كفوءة للمسائل العامة 1//F(∑Cj, Tmax, Vmax)، 1//F(∑Cj, ∑Vj, Vmax)، 1//F(∑Cj, ∑Vj, Tmax)، 1//F(∑C2j, Tmax, Vmax)، 1//F(∑Cj, Tmax+Vmax). اقترحـت الخوارزمية الكفؤة (ADA1) لحل هذه المسائل. اقترحـت ايضا خوارزميتيــن لايجاد افضــل حـل ممكن لكـل من المسالتيـن الهرميتيـن 1//Lex(Vmax,∑Cj,Tmax) و1//Lex(Vmax,Tmax,∑Cj).الخوارزميات الكفوءة المقترحة هي عامة ويمكن استخدامها لايجاد مجموعة الحلول الكفوءة الفعلية (strict Pareto optimal) لمسائل جدولة متعددة المقاييس. نتائجنا التجريبية تشير الى ان الخوارزميات المقترحة تجد الحلول الكفوءة بشكل فعال في معظم الحالات وايضا، نتائجنا الحسابية تبين بان الخوارزمية (GA) فعالة اكثر للمسائل 1//∑Vj+Vmax و1/rj/Tmax+Vmax. اخيرا، قدمت استنتاجاتنا مع بعض المقترحات لبحوث مستقبلية. | This thesis is devoted to multicriteria scheduling problems. It is presented in six chapters.The first two chapters are introductory in which we give various aspects of multicriteria problem formulation and we discuss the well known methods of solution for machine scheduling problem.The next three chapters contain original research on various multicriteria single machine scheduling.This thesis presents the mathematical models and algorithms for generating efficient, optimal and approximation solutions for multicriteria scheduling problems.We use branch and bound techniques for minimizing the two criteria : the total late work (∑Vj) and the maximum late work (Vmax), this problem is denoted by 1//F(∑Vj,Vmax). An efficient algorithm (ADA) is proposed to find efficient solutions set. A branch and bound (BAB) algorithm is also presented to find optimal solution for the problem of minimizing a linear function ∑Vj+Vmax. The NP - hardness of the last problem suggests that it is not always possible to find an optimal solution quickly. Therefore, local search algorithms (descent method (DM), simulated annealing (SA) algorithm and genetic algorithm (GA)) are used to find approximation solutions that are close to the optimum with less computational time.An efficient algorithm is proposed, to find efficient solutions for one machine problem with release dates denoted by 1/rj/F(Tmax,Vmax). A branch and bound (BAB) algorithm is also presented to find optimal solution for the problem of minimizing a linear function Tmax+Vmax with release dates. For this problem also local search algorithms are used to find approximation solutions.The multicriteria scheduling problems are studied on a single machine to find efficient solutions set for the general problems 1//F(∑Cj,Tmax,Vmax), 1//F(∑Cj,∑Vj,Vmax), 1//F(∑Cj, ∑Vj, Tmax), 1//F(∑C2j, Tmax,Vmax) and 1//F(∑Cj,Tmax+Vmax). An efficient algorithm (ADA1) is proposed for solving these problems. Also two algorithms are proposed to find the best possible solution for each of the two hierarchical problems 1//Lex(Vmax, ∑Cj,Tmax) and 1//Lex(Vmax, Tmax, ∑Cj).The proposed efficient algorithms are general and can be used to enumerate the set of strict Pareto optimal for the multicriteria scheduling problems. Our experimental results indicate that the proposed algorithms find efficient solutions optimality in most cases. Also, our computational results show that the genetic algorithm (GA) is more effective for the problems 1//(∑Vj+Vmax) and 1/rj/(Tmax+Vmax). Finally, our conclusions together with some suggestions for future researches are given
