research centers


Search results: Found 5

Listing 1 - 5 of 5
Sort by

Article
Single Machine Scheduling To Minimize a Function of Square Completion Time and Maximum Tardiness Simultaneously

Author: Tariq Salih Abdul-Razaq
Journal: Al-Mustansiriyah Journal of Science مجلة علوم المستنصرية ISSN: 1814635X Year: 2010 Volume: 21 Issue: 5 Pages: 375-390
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

In this study, to minimize a function of two cost criteria for scheduling n jobs on a single machine , the problem is discussed :“ Minimizing a function of total square completion time and maximum tardiness simultaneously”.For this problem we proposed some algorithms to find exact(optimal) solution for hierarchical case and efficient (pareto optimal) solutions for simultaneous case, Also we proposed branch and bound algorithm to find exact solution for sum of total square completion time and maximum tardiness, and present algorithm B to find exact solution in a fast way with respect to (BAB) method. We present computational experience for the (BAB) method and algorithm(B) on a large set of test problems.

في هذه الدراسة ولتصغير دالة الكلفة لمعيارين والحاصلة من جدولة n من الاعمال على ماكنة واحدة درست المسألة: تصغير الدالة F( ∑Ci2 , Tmax) حيث ان Tmax هي regular measure في هذه المسألة اقترحنا بعض الخوارزميات لايجاد الحل الامثل في حالة الـ (hierarchical ) والحلول الكفوءة في حالة الـ (simultaneous ) . وكذلك اقترحنا خوارزمية للـ (BAB) لايجاد الحل الامثل للمسألة (P4) . وقدمنا ايضاً حوارزمية B لايجاد الحل الامثل للمسألة (P4) ولكن بطريقة اسرع من خوارزمية(BAB) . وقدمنا حسابات الاختبارات لخوارزميات BAB و B والتي تم تنفيذها على مجموعة كبيرة من المسائل.

Keywords


Article
Single Machine with Multicriteria Problems

Author: Tariq Salih Abdul-Razaq
Journal: Al-Mustansiriyah Journal of Science مجلة علوم المستنصرية ISSN: 1814635X Year: 2010 Volume: 21 Issue: 6 Pages: 291-303
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

The problem domain chosen for this research is the single machine scheduling problem, and the performance measures investigated are maximum weighted tardiness and total weighted completion time. Hence, the following two bicriteria scheduling problems of n jobs on a single machine are discussed:a)Minimizing total completion times subject to the maximum weighted tardiness is optimal.b)Minimizing the sum of total weighted completion times and the maximum weighted tardiness. For the first problem, an algorithm is proposed which gives optimal solution for this hierarchical bicriteria problem. Also the optimality proof for this algorithm is given. For the second problem which is known as NP-hard. We derive a good lower bound based on objective splitting, in order to design a branch and bound (BAB) algorithm for its solution. The NP-hardness of this second simultaneous optimization problem suggests that it is not always possible to find an optimal solution quickly. Therefore, instead of searching for an optimal solution with enormous computational effort, we may use a local search to generate approximate solutions that are close to the optimum with considerably less computational time. We develop, local search heuristics methods that aim to find near optimal solutions for this problem. We then adopted some of these local search methods such as descent method (DM),simulated annealing (SA) method, tree type heuristic (TTH) method and genetic algorithm (GA). We present computational experiments for the exact and local search methods on a large set of test problems, it seems thata)The BAB algorithm is efficient for small size problems.b)The performance of these local search methods on large size problems are very effective, and the performance of (SA) method is the best and within reasonable search time.

مجال المسألة التي اُختيرت لهذا البحث تخص مشكلة جدولة الماكنة الواحدة و المقاييس التي بُحثت هي أعظم غرامة للتأخير مع أخذ الوزن بنظر الاعتبار و المجموع الوزني لأوقات الإتمام. لذا ناقشنا في هذه الرسالة مسألتين ثنائية المعايير لجدولة (n) من الأعمال على ماكنة واحدة:1. تصغير مجموع أوقات الإتمام بشرط أن أعظم تأخير وزني يكون أمثل.a. تصغيرحاصل جمع المجموع الوزني لأوقات الإتمام وأعظم تأخير موزون. فيما يخص المسألة الاولى اقترحنا خوارزمية والتي أعطت حل أمثل لهذه المسألة وهي مسألة ثنائية المعايير متتابعة. وتم برهنة الامثلية لهذه الخوارزمية. فيما يخص المسالة الثانية والتي عُرفَت بأنها NP-hard . تم اشتقاق قيد أدنى (LB) جيد ويعتمد على تجزئة الهدف، لكي نتمكن من تصميم خوارزمية التفرع والتقيد ( BAB) التي تستخدم لإيجاد الحل الأمثل لهذه المسألة. ونتيجةً لصعوبة الامثلية لأكثر من هدف سويةً لذلك يقترح بأنه ليس بالامكان دائماً ايجاد حل امثل لهذه المسألة وبطريقة سريعة. لذلك وبدلاً من البحث عن الحل الامثل وبذل مجهود حسابي كبير، و كبديل يمكن استخدام طرائق الحل المحلية (Local search methods) لتوليد حلول تقريبية وهي قريبة من الحل الامثل وفي زمن حسابي أقل. طورنا طرائق الحل المحلية والتي تهدف الى ايجاد حل قريب من الحل الامثل لهذه المسألة. وبعد ذلك تم تطبيق بعض هذه الطرائق مثل Descent method (DM), simulated annealing (SA), tree type heuristic method (TTHM) and genetic algorithm (GA). كذلك قدمنا اختبارات حسابية للطرائق الحل المضبوطة والمحلية على مجموعة كبيرة من المسائل الاختبارية وكانت النتائج:•أن خوارزمية التفرع والتقيد ((BAB كفوءة للمسائل ذات الحجم الصغير من الأعمال..2أداء طرق الحل المحلية كفوءة للمسائل ذات الحجم الكبير من الاعمال, وعند اختبار كفاءة هذه الطرائق التقريبية على مجموعة كبيرة من المسائل الاختبارية, كانت النتائج تشير إلى أن أداء طريقة (SA) هي الافضل مع وقت حسابي معقول.

Keywords


Article
Exact and Approximation Approaches for Solving Multiple Objective Function

Author: Tariq Salih Abdul-Razaq
Journal: Al-Mustansiriyah Journal of Science مجلة علوم المستنصرية ISSN: 1814635X Year: 2016 Volume: 27 Issue: 3 Pages: 89-97
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

In this paper we consider the problem of multi-criteria scheduling n jobs on a single machine to minimize the sum of the total flow times, maximum earliness and maximum tardiness (i.e. to minimize the Multiple Objective Function (MOF) defined by ∑_j▒C_j +E_max+T_max).The main contribution is a Branch and Bound (BAB) algorithm to find optimal solution. The BAB method uses dominance rules to reduce the number of sequences that must be considered. Since this problem is NP-hard, we propose Tree Type Heuristic (TTH) Method and Variable Neighborhood Descent (VND) algorithm to solve the problem efficiently. Also we introduce some special cases of the problem to find optimal solution.We discuss and modify algorithms to find optimal and near optimal solutions to our scheduling problem. The exact algorithms produce optimal solutions, but its running time cannot be bounded from above by a polynomial in the size of an instance for NP-hard problem. Approximation algorithms produce solutions in relatively little computation time, but their solutions need not be optimal. Computational results show that the approximate algorithms (TTH and VND) are able to solve instances of our problem for large sizes.

في هذا البحث درسنا مسألة دالة متعددة الأهداف لجدولة n من الاعمال على ماكنة واحدة لتصغير المجموع زمن الانسياب الكلي واكبر تبكير واكبر تأخير (ما معناه تصغير دالة متعددة الأهداف المعرفة بالصيغة ∑_j▒C_j +E_max+T_max). كانت مساهمتنا الرئيسية هي خوارزمية التفرع والتقييد BAB لإيجاد الحل الأمثل. طريقة BAB استخدمت قواعد الهيمنة لتقليل عدد المتسلسلات التي يجب ان تؤخذ بعين الاعتبار. بما ان مسألتنا من نوع NP-hard، اقترحنا طريقة TTH وخوارزمية VND لحل المسألة بكفاءة. كذلك قدمنا بعض الحالات الخاصة لمسألتنا لإيجاد الحل الأمثل لها.ناقشنا وطورنا خوارزميات لإيجاد الحلول المثلى والحلول القريبة من المثلى لجدولة مسألتنا. خوارزمية BAB تعطينا حلول مثلى، ولكنها تحتاج لوقت لا يمكن تحديده من الأعلى بواسطة متعددة الحدود في حجم الحالة لمسألة NP-hard. خوارزميات التقريب تعطينا الحلول بوقت حسابي اقل نسبياً، ولكن حلولها لا يلزم ان تكون مثلى. النتائج الحسابية أظهرت قدرة الخوارزميات التقريبية (TTH وVND) على حل حالات للمسألة ولحجوم كبيرة.

Keywords


Article
Multi-Objective Variable Neighborhood Search Algorithms
دوال متعددة لمتغيرات بحث الجوار للخوارزميات

Authors: Tariq Salih Abdul-Razaq --- Hussam Abid Ali Mohammed
Journal: journal of kerbala university مجلة جامعة كربلاء ISSN: 18130410 Year: 2016 Volume: 14 Issue: 1 Pages: 1-17
Publisher: Kerbala University جامعة كربلاء

Loading...
Loading...
Abstract

The Multi-Objective Single Machine Scheduling (MOSMS) Problem is one of the most representative problems in the scheduling area. In this paper, we compare five multi-objective algorithms based on Variable Neighborhood Search (VNS) heuristic. The algorithms are applied to solve the MOSMS problem. In this problem, we consider minimizing the total completion times and minimizing the sum of maximum earliness/tardiness. We introduce two intensification procedures to improve a Multi-Objective Variable Neighborhood Search (MOVNS) algorithms proposed in the literature. The performance of the algorithms is tested on a set of instances of the problem. The computational results show that the proposed algorithms outperform the original MOVNS algorithms in terms of efficiency solutions.

مسألة جدولة الدوال المتعددة الاهداف هي واحدة من المسائل الأكثر تمثيلا في مجال الجدولة. في هذا البحث، قارنا خمس خوارزميات لدوال متعددة بالاعتماد على أساس بحث متغيرات الجوار. تم تطبيق الخوارزميات لحل مسالة جدولة الماكنة الواحدة ذات دوال هدف متعددة. وفي هذه المسألة هدفنا هو تصغير من إجمالي وقت الاتمام ومجموع أكبر التبكير/التأخر. قدمنا طريقتي تكثيف لتحسين دوال متعددة لمتغيرات بحث الجوار للخوارزميات والمقترحة من قبل الباحثين. تم اختبار أداء الخوارزميات على مجموعة من الحالات للمسألة. وأظهرت النتائج الحسابية أن الخوارزميات المقترحة تفوق على الخوارزميات الأصلية من حيث كفاءة الحلول.


Article
Single Machine Scheduling To Minimize a Function of Square Completion Time and Maximum Earliness Simultaneously

Loading...
Loading...
Abstract

In this study, to minimize a function of two cost criteria for scheduling n jobs on a single machine , the problem is discussed :“ Minimizing a function of total square completion time and maximum Earliness simultaneously”.For this problem we proposed some algorithms to find exact(optimal) solution for hierarchical case and efficient (pareto optimal) solutions for simultaneous case. Also we proposed branch and bound algorithm to find exact solution for sum of total square completion time and maximum Earliness ,and present algorithm D to find exact solution in a fast way with respect to (BAB) method. We present computational experience for the (BAB) method and algorithm(D) on a large set of test problems

في هذه الدراسة ولتصغير دالة الكلفة لمعيارين والحاصلة من جدولة n من الاعمال على ماكنة واحدة درست المسألة: تصغير الدالة F( ∑Ci2 , Emax) حيث ان Emax هي irregular measure في هذه المسألة اقترحنا بعض الخوارزميات لايجاد الحل الامثل في حالة الـ (hierarchical ) والحلول الكفوءة في حالة الـ (simultaneous ) . وكذلك اقترحنا خوارزمية للـ (BAB) لايجاد الحل الامثل للمسألة (P4) . وقدمنا ايضاً خوارزمية D لايجاد الحل الامثل للمسألة (P4) ولكن بطريقة اسرع من خوارزمية(BAB) . وقدمنا حسابات الاختبارات لخوارزميات BAB و D والتي تم تنفيذها على مجموعة كبيرة من المسائل.

Keywords

Listing 1 - 5 of 5
Sort by
Narrow your search

Resource type

article (5)


Language

English (4)

Arabic and English (1)


Year
From To Submit

2016 (2)

2010 (3)