research centers


Search results: Found 7

Listing 1 - 7 of 7
Sort by

Article
Algorithms for Multicriteria Scheduling Problems
حل مسائل الجدولة ذات دوال هدف متعددة

Author: Tariq S. Abdul-Razaq and Karar F. Abdul-Razaq طارق صالح عبد الرزاق و كرار فتاح عبد الرزاق
Journal: basrah journal of science البصرة للعلوم ISSN: 18140343 Year: 2016 Volume: 34 Issue: 3 A Pages: 1-12
Publisher: Basrah University جامعة البصرة

Loading...
Loading...
Abstract

In this paper, we consider the multicriteria scheduling problem on single machine to minimize two criteria: maximum cost function, denoted by maximum late work (Vmax) and maximum earliness (Emax). We propose several algorithms based on types of objectives function to be optimized. The solutions of the proposed procedures are compared with that of the optimal solutions and Pareto optimal solutions for the smaller instance size, these algorithms dealing with hierarchical minimization problem as well as simultaneous minimization problem with and without weight. Computational results show the usefulness of these procedures.

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


Article
Solving Composite Multi objective Single Machine Scheduling Problem Using Branch and Bound and Local Search Algorithms

Author: Tariq S. Abdul – Razaq1
Journal: Al-Mustansiriyah Journal of Science مجلة علوم المستنصرية ISSN: 1814635X Year: 2017 Volume: 28 Issue: 3 Pages: 200-208
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

This paper present algorithm for solving a single machine scheduling problem to minimize the sum of total completion times, total tardiness, maximum tardiness, and maximum earliness. The single machine total tardiness problem is already NP-hard, so they consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithm with dominance rule and local search algorithms are proposed for the problem. For the Branch and bound algorithm results- show that using dominance rule improve the performance of the algorithm in both computation times and optimal values, but it needs longer times. Thus we tackle the problem of large sizes with local search algorithms descent method, simulated annealing and tabu search. The performance of these algorithms is evaluated on a large set of test problems and the results are compared. The computational results show that simulated annealing algorithm and Tabu search algorithm are better than descent method with preference to simulated annealing algorithm, and show that the three algorithms find optimal or near optimal solutions in reasonable times.


Article
Algorithms for Scheduling a Single Machine to Minimize Total Completion Time and Total Tardiness
خوارزميات تقليل وقت الاتمام الكلي والتأخير الكلي لجدولة ماكنة واحدة

Author: Tariq S. Abdul-Razaq and Faez H. Ali د.طارق صالح عبد الرزاق وفائز حسن علي
Journal: basrah journal of science البصرة للعلوم ISSN: 18140343 Year: 2016 Volume: 34 Issue: 2 A Pages: 113-132
Publisher: Basrah University جامعة البصرة

Loading...
Loading...
Abstract

In this paper we look at the problem where we have to schedule n jobs with processing times and due dates on a single machine. The objective is to find a schedule that minimize a function of the sum of completion time and sum of tardiness (i,e to minimize the multiple objective functions (Ci,Ti)). We propose two methods for solving this simultaneous minimization problem to find the set of all efficient solutions, (Pareto optimal solutions). This set of all efficient solutions is not easy to find, therefore, it could be preferable to have an approximation to that set in a reasonable amount of time. Therefore branch and bound (BAB) and local search methods are used.The Particle Swarm Optimization (PSO) method is applied as new local search method on a set of randomly generated problems to solve machine scheduling problem with multiple objective functions. Comparison studies are made between Branch and Bound Methods (BAB), PSO and Genetic Algorithm (GA) to show which one is the better method in applications. In addition, tuning the parameters of every method has been suggested in order to improve the application of every method. A new style of development steps has been proposed to achieve good convergence in application. Since our problem is NP-hard, we propose new heuristic method like PSO and GA to find approximation solutions especially when the number of jobs exceeds the ability of some exact methods like complete enumeration and BAB in solving such problems. Lastly, the proposed methods results are compared for this multi-objective scheduling problem. Computational experience is found that these local search algorithms solve problem to '2000 'jobs with reasonable time.

في هذا البحث سيتم مناقشة مسالة جدولة n من الاعمال لها اوقات تنفيذ والوقت المثالي لانجاز النتاج لماكنة واحدة. الهدف هو ايجاد جدولة تقلل قيمة دالة مجموع وقت الاتمام ومجموع وقت التأخير (لتقليل دالة متعددة الاهداف (Ci,Ti)). في هذا البحث نقترح طريقتين لحل مسالة التقليل ألآني لايجاد مجموعة كل الحلول الكفوءة (حلول باريتو المثالية). ان ايجاد مجموعة الحلول الكفوءة ليس بالامر الهين، لذلك، من الافضل ايجاد قيم تقريبية لمجموعة الحلول وفي اوقات معقولة. لذلك تم استخدام طريقة التقيد والتفرع (BAB) وطرق البحث المحلية.تم تطبيق طريقة امثلية السرب الجزيئي (PSO)، طريقة بحث محلية جديدة، على مسائل مولدة عشوائياً لحل مسائل مكائن الجدولة متعددة الاهداف. ولان مسألتنا هي من المسائل المعقدة، فاننا نقترح استخدام طرق تقريبية جديدة مثل (PSO) و(GA) لايجاد حلول تقريبية خصوصا عندما يتجاوز عدد الاعمال امكانية بعض الطرق الحل التام مثل حل التام مثل طريقة العد التام وطريقة (BAB). تم اجراء دراسة مقارنة بين طريقة التقيد والتفرع وطريقة امثلية السرب الجزيئي والخوارزمية الجينية لبيان اي منها الافضل عند التطبيق.


Article
New Improved Heuristic Method for Solving Travelling Salesman Problem

Authors: Faez Hassan Ali --- Sajad Majeed Jassim
Journal: Iraqi Journal of Science المجلة العراقية للعلوم ISSN: 00672904/23121637 Year: 2018 Volume: 59 Issue: 4C Pages: 2289-2300
Publisher: Baghdad University جامعة بغداد

Loading...
Loading...
Abstract

In this paper we will investigate some Heuristic methods to solve travelling salesman problem. The discussed methods are Minimizing Distance Method (MDM), Branch and Bound Method (BABM), Tree Type Heuristic Method (TTHM) and Greedy Method (GRM). The weak points of MDM are manipulated in this paper. The Improved MDM (IMDM) gives better results than classical MDM, and other discussed methods, while the GRM gives best time for 5≤ n ≤500, where n is the number of visited cities.


Article
Using Travelling Salesman Principle to Evaluate the Minimum Total Cost of the Iraqi Cities

Authors: Sajjad Majeed Jasim --- Faez Hassan Ali
Journal: Ibn Al-Haitham Journal For Pure And Applied Science مجلة ابن الهيثم للعلوم الصرفة والتطبيقية ISSN: P16094042/ E25213407 Year: 2019 Volume: 32 Issue: 3 Pages: 95-108
Publisher: Baghdad University جامعة بغداد

Loading...
Loading...
Abstract

The traveling salesman problem (TSP) is a well-known and important combinatorialoptimization problem. The goal is to find the shortest tour that visits each city in a given listexactly once and then returns to the starting city. In this paper we exploit the TSP to evaluatethe minimum total cost (distance or time) for Iraqi cities. So two main methods areinvestigated to solve this problem; these methods are; Dynamic Programming (DP) andBranch and Bound Technique (BABT). For the BABT, more than one lower and upperbounds are be derived to gain the best one. The results of BABT are completely identical toDP, with less time for number of cities (n), 5 ≤ n ≤ 25. These results proof the efficiency ofBABT compared with some good heuristic methods. We are suggesting some additionaltechniques to improve the computation time of BABT for n ≤ 80.


Article
Exact algorithm for minimizing the sum of total late work and maximum late work problem
خوارزمية مضبوطة لتصغير مسألة المجموع لعمل متأخر كلي وأعظم عمل متأخر

Authors: Adawiyah A. Mahmood Al-Nuaimy عدوية علي محمود النعيمي --- Tariq S. Abdul-Razaq طارق صالح عبد الرزاق
Journal: Diyala Journal For Pure Science مجلة ديالى للعلوم الصرفة ISSN: 83732222 25189255 Year: 2014 Volume: 10 Issue: 1 Pages: 39-50
Publisher: Diyala University جامعة ديالى

Loading...
Loading...
Abstract

This paper presents a branch and bound (BAB) algorithm for minimizing the sum of total late work and maximum late work problem within the single machine context. Late work is the amount of work executed after a given due date. Branch and bound (BAB) is proposed, two heuristic methods are used to find an upper bound. This BAB proposes a lower bound based on the decomposition property of the bi-criteria problem. Based on results of computational experiments, conclusions are formulated on the efficiency of the BAB algorithm.

إن هذا البحث يقدم خوارزمية التقيد والتفرع (Branch and bound(BAB)) لمسألة تصغير المجموع لعمل متأخر كلي وأعظم عمل متأخر(The sum of total late work and maximum late work) على ماكنة واحدة. العمل المتأخر هو مقدار العمل الذي ينفذ بعد وقت مثالي معطى. استخدمنا طريقتين تقريبيتين لإيجاد القيد الأعلى (Upper bound). في خوارزمية التقيد والتفرع يتم إيجاد قيد أدنى (Lower bound) يعتمد على تجزئة المسألة ثنائية المقاييس.


Article
Optimal Solution for Simultaneous Multicriteria Problem
حل أمثل لمسألة متعددة المقاييس تحدث في وقت واحد

Author: Adawiya A. Mahmood Al-Nuaimi عدوية علي محمود النعيمي
Journal: Diyala Journal For Pure Science مجلة ديالى للعلوم الصرفة ISSN: 83732222 25189255 Year: 2016 Volume: 12 Issue: 2 Pages: 18-27
Publisher: Diyala University جامعة ديالى

Loading...
Loading...
Abstract

This paper considers a branch and bound (BAB) algorithm for simultaneous multicriteria problem of minimizing the sum of the three criteria of total completion time, maximum tardiness and maximum late work within the single machine context.Late work is the amount of work executed after a given due date. Heuristic method was used to find an upper bound. This BAB proposes a lower bound based on the decomposition property of the multicriteria problem. Based on results of computational experiments, conclusions are presented on the efficiency of the BAB algorithm.

إن هذا البحث يقدم خوارزمية التفرع والتقيد ((Branch and bound(BAB) لمسألة متعددة المقاييس تحدث في وقت واحد لتقليل المجموع للمقاييس الثلاثة لوقت الإتمام الكلي (ΣCj) ، أعظم تأخير لا سالب (Tmax) وأعظم تأخير لوحدات عمل متأخر(Vmax) على ماكنة واحدة. العمل المتأخر هو مقدار العمل الذي يُنفذ بعد وقت مثالي معطى. استُخدمت طريقة تقريبية لإيجاد القيد الأعلى (Upper bound). في خوارزمية التفرع والتقيد يتم إيجاد قيد أدنى (Lower bound) يعتمد على تجزئة المسألة متعددة المقاييس. بالاعتماد على نتائج التجارب الحسابية قُدمت استنتاجات حول كفاءة خوارزمية التفرع والتقيد(BAB).

Listing 1 - 7 of 7
Sort by
Narrow your search

Resource type

article (7)


Language

English (7)


Year
From To Submit

2019 (1)

2018 (1)

2017 (1)

2016 (3)

2014 (1)