research centers


Search results: Found 13

Listing 1 - 10 of 13 << page
of 2
>>
Sort by

Article
An efficient algorithm to solve 1// ∑Ci+∑Yi problem

Author: Haeder Younis Ghawi
Journal: Journal of Al-Qadisiyah for Computer Science and Mathematics مجلة القادسية لعلوم الحاسوب والرياضيات ISSN: 20740204 / 25213504 Year: 2011 Volume: 3 Issue: 2 Pages: 1-9
Publisher: Al-Qadisiyah University جامعة القادسية

Loading...
Loading...
Abstract

In the problem of scheduling a single machine to minimize the sum of completion time and total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the sum of total completion time and total late work ,where the late work for a job is the amount of processing of this job that is performed after its due date. Although dominance rules are derived for the special cases in which all processing times are equal and all due dates are equal. Algorithm H is presented for the general non preemptive sum of completion time and the total late work simultaneous problems


Article
Hybridize optimization Algorithms for the Single Machine Total Tardiness Problem

Authors: م.م. اسماعيل خليل علي --- م.م. هيثم غني احمد --- م. د. شاكر ناجي
Journal: Baghdad College of Economic sciences University مجلة كلية بغداد للعلوم الاقتصادية الجامعة ISSN: 2072778X Year: 2008 Issue: 17 Pages: 321-340
Publisher: Baghdad College of Economic Sciences كلية بغداد للعلوم الاقتصادية

Loading...
Loading...
Abstract

Various optimization heuristics are investigated and applied in a number of areas in the field of single machine scheduling problems. We present efficient heuristic optimization algorithms (Genetic Algorithm and Simulated Annealing) for single machine scheduling problems with and without release times. The increasingly important issue of parallelization is considered with an example implementation being provided in the case of single machine problem is shown. The results show that these algorithms were able to produce high quality optimization, especially for wjTj.


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
MULTIPLE OBJECTIVE FUNCTION ON A SINGLE MACHINE SCHEDULING PROBLEM
دالة هدف مركبة في مسالة جدولة الماكنة الواحدة

Loading...
Loading...
Abstract

We consider a single machine scheduling problem to minimize a multiple objective function; sum of earliness, tardiness and completion time. As this problem is complete NP-hard we propose a branch and bound algorithm to obtain an optimal solution. The implementation of optimizing algorithms dose seen to be promising but it need longer time. Thus we tackle the problem with local search methods: descent method, simulated annealing and threshold acceptance. The performance of these heuristic methods is evaluated on a large set of test problems, and the results are also compared with these obtained by genetic algorithm and hybrid method which is combining the simulated annealing with the genetic algorithm. The best results are obtained with the hybrid method. We solved the problem optimality with up to 35 jobs and approximately with up to 150000 jobs.

الخلاصـــة في هذا البحث درسنا مسالة جدولة الماكنة الواحدة لتصغير دالة هدف مركبة "مجموع التبكير والتـأخيرالاسالب وزمن إتمام النتاجات على الماكنه الواحده" . أن هذه المسألة من نوع NP-hard لذا اقترحنا طريقة التفرع والتقيد لايجاد الحل الامثل علماً ان الحل الأمثل يتطلب وقت أطول. وقد استخدمنا طرق البحث المحلي لايجاد الحلول التقريبية حسبت النتائج لهذه الطرق وقورنت النتائج مع الحل الامثل وكذالك مع الخوارزمية الجينية وطريقة التهجين المقترحه التي هجنا فيها simulated annealing مع الخوارزمية الجينية. افضل النتائج اعطتها طريقة التهجين. وجدنا الحل امثليا للمسألة لغاية 35 نتاج. وتقريبياً لغاية 150000 نتاج.


Article
Approximation methods for total completion time with set-up times
الطرق التقريبية لوقت الانتهاء لمجموع مع انشاء مرات

Author: Adawiyah A. Mahmood عدوية علي محمود
Journal: Journal of Research Diyala humanity مجلة ديالى للبحوث الانسانية ISSN: 1998104x Year: 2008 Issue: 32 Pages: 296-304
Publisher: Diyala University جامعة ديالى

Loading...
Loading...
Abstract

This research considers the problem of scheduling jobs on a single machine to minimize the objective function , the sum of completion time .The jobs partitioned into families , and a set-up time is necessary for scheduling the first job and when there is a switch in processing jobs from one family to jobs of another family . To solve this problem some known approximation methods are modified , namely the tree type heuristic (TTH) and tow local search methods descend method (DM) and simulated annealing method (SAM) . The performance of approximation methods can be tested on a large class of test problems.

: تناولنا في هذا البحث مسألة جدولة النتاجات على ماكنة واحدة لتصغير دالة الهدف وهي مجموع أوقات الإتمام (The sum of completion time ). لقد قسمت النتاجات إلىF من العوائل وهناك وقت إعداد ضروري للماكنة عند جدولة أول نتاج وعند جدولة نتاج من عائلة تختلف عن عائلة النتاج الذي يسبقه . لحل هذه المسألة قمنا بتطوير بعض الطرائق التقريبية (Approximation methods) المعروفة وهي طريقة ( TTHM) ( Tree type heuristic method ) وطريقتين من البحث المحلي ( Local Search ) وهما (DM) (Descent method ) و ( SAM) ( Simulated annealing method ) .يمكن تطبيق هذه الطرائق التقريبية على عدد كبير من مسائل الاختبار .


Article
MemeticAlgorithmand Genetic Algorithm for the Single Machine Scheduling Problem with Linear Earliness and Quadratic Tardiness Costs

Authors: Hussam A.A. Mohammed --- Adil S. Hassan --- Mohammed H. Saloomi --- Ghassan A. Khtan
Journal: journal of kerbala university مجلة جامعة كربلاء ISSN: 18130410 Year: 2012 Volume: 1 Issue: المؤتمر العلمي الاول للتربية للعلوم الصرفة Pages: 107-113
Publisher: Kerbala University جامعة كربلاء

Loading...
Loading...
Abstract

The Single Machine Scheduling (SMS) problem with Multiple Objective Function (MOF) is one of the most representative problems in the scheduling area. In this paper, we consider the SMS problem with linear earliness and quadratic tardiness costs, and no machine idle time. The chosen method is based on memetic algorithm and genetic algorithm.For this purpose, Genetic Algorithms (GA) are a population-based Meta heuristics. They have been successfully applied to many optimization problems. A Memetic Algorithm (MA) is an extension of the traditional genetic algorithm. And we introduce two types of crossover. The methods were tested and various experimental results show that MA performs better than the GA for big jobs but GA was better with small jobs.

مسألة جدولة الماكنةِ الوحيدةِ (SMS) مع دالة متعددة الأهداف واحدة من أكثر المسائل النموذجية في نطاقِ الجدولة. في هذه البحث، نَعتبرُ مسألة جدولة الماكنةِ الوحيدةِ بالتبكيرِ الخطيِّ وكلفِ التأخرِ من الدرجة الثانيةِ، ولاوجودلفترةَ توقف على ماكنةِ. إنّ الطريقةَ المُختَاَرةَ مستندة على خوارزميةِ ميميتيك وخوارزمية وراثية.لهذا الغرضِ، خوارزميات وراثية(GA) مع قاعدة مجتمع متعدد التنقيب. نحن قُدّمنا إلى العديد مِنْ مسائل تحقيقِ الأمثلية بنجاح. خوارزمية ميميتيك (MA) امتداد لخوارزميةِ الوراثيةِ التقليديةِ. كذلك نُقدّمُإثنانمِنْأنواعِالانتقالِ. الطرقكَانتْنَتائِجَتجريبيةَمُجرّبةَومُخْتَلِفةَ تبين بأنّMAيُؤدّيأفضلمِنْGAللأعمال الكبيرةِلكنGAكَانتْأفضلَبالأعمال الصغيرةِ


Article
Branch and Bound Method to Minimized Three Criteria

Author: Mohammed K.Al-Zuwaini & Kadhem M. Hashem& Jafar S.Aneed
Journal: Journal of Education for Pure Science مجلة التربية للعلوم الصرفة ISSN: 20736592 Year: 2014 Volume: 4 Issue: 1 Pages: 37-48
Publisher: Thi-Qar University جامعة ذي قار

Loading...
Loading...
Abstract

This paper addresses the problem of minimizing the sum of total completion times, maximum earliness and maximum tardiness on a single machine with unequal release date. A branch and bound algorithm with forward approach, in order to find the exact (optimal) solution for itwith two lower bounds (LB_1,LB_2) and four upper bounds〖(UB〗_1,UB_2,UB_3,UB_4) that introduced in this paper. Ten special cases are suggested and proved that yield optimal solution. In general, this problem is strongly NP-hard, and solved it with up to 30 jobs.

في هذا البحث تم اعتماد مسألة تزغير المجموع لوقت الاكتمال وتكبير وقت التبكير وتكبير وقت التأخير لمسألة الجدوله لماكنه واحدة وفي اوقات تسليم غير متساويه . أستخدمة طريقة التفرع والتقيد الاماميه لايجاد وقت الحل الامثل لهذه المسألة وبحدين للقيد الادنى LB_1,LB_2 وبأربعة قيود عليا 〖(UB〗_1,UB_2,UB_3,UB_4) . تم تطبيق الحلول على عشرة حالات خاصه في ايجاد الحل الامثل بشكل عام هذه المسألة هي NP-hard قويه والحل يمكن الحصول عليه لغاية 30 عمل .


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
Branch and Bound Method to Minimize Three Objective Functions with Unequal Release Dates

Authors: Araibi Sami M --- Al-Zuwaini Mohammed K
Journal: Journal of Univesity of Thi-Qar مجلة جامعة ذي قار العلمية ISSN: 66291818 Year: 2014 Volume: 9 Issue: 2 Pages: 1-18
Publisher: Thi-Qar University جامعة ذي قار

Loading...
Loading...
Abstract

In this paper, a single machine scheduling problem is considered to minimize Multiple Objectives Function (MOF). The aim in this study is to find the optimal solution for the sum of the number of tardy jobs (∑_(j=1)^n▒U_j ), maximum tardiness (T_max) and makespan (C_max) with unequal release dates. Ten special cases are derived and proved that yield optimal solutions. A Branch and Bound algorithm is proposed with two lower bounds (LB_1, LB_2) and two upper bounds (UB_1, UB_2) that introduced in this paper, in order to find the exact (optimal) solution for it with two dominance rules which helped in reducing the number of branches in the search tree. Results of extensive computational tests show the proposed (BAB) algorithm is effective in solving problem up to (40) jobs at a time less than or equal to (30) minutes. In general, this problem is strongly NP-hard, and to the best of our knowledge this problem was not studied before.

في هذا البحث, درسنا مسألة جدولة الماكنة الواحدة لتصغير دالة متعددة الاهداف (MOF). هدفنا في هذه الدراسة هو ايجاد الحل الامثل لمجموع عدد النتاجات المتأخرة ( ∑_(j=1)^n▒U_j ) وأكبر زمن تأخير ( T_max) وأكبر زمن ﺇتمام ( C_max) مع وقت تحضير للنتاجات غير متساوي. تم اشتقاق وبرهان عشرة حالات خاصة تعطي الحلول المثلى. كذلك اقترحنا خوارزمية التفرع والتقيد مع اثنين من القيود الدنيا (LB_1, LB_2) واثنين من القيود العليا (UB_1, UB_2) قُدمت في هذا البحث من اجل ايجاد الحل الامثل للمسألة قيد الدراسة مع قاعدتين للهيمنة تساعدان في تقليص عدد التفرعات في شجرة البحث. نتائج الاختبارات الحسابية أثبتت بأن خوارزمية التفرع والتقيد المقترحة فعالة في حل المسائل لغاية (40) نتاج في وقت أقل او يساوي (30) دقيقة. بشكل عام هذه المسألة من نوع strongly NP-hard, وحسب معرفتنا ان هذه المسألة لم تُدرس من قبل.


Article
Ant Colony Method to Minimize Single Machine Scheduling Problem

Author: Sami .M Araibi
Journal: JOURNAL OF THI-QAR SCIENCE مجلة علوم ذي قار ISSN: 19918690 Year: 2017 Volume: 6 Issue: 3 Pages: 52-57
Publisher: Thi-Qar University جامعة ذي قار

Loading...
Loading...
Abstract

The study deal with a single machine scheduling problem where the objective is to find the sequence which it give the optimal or efficient solution for the objective function the sum of discounted weighted completion time and number of tardy jobs. The optimal solution was found for some special cases. Ant colony optimization (ACO) using to found an approximate solution. Results of extensive computational tests show that proposed (ACO) is effective in solving problems up to (1000) jobs at a time less than or equal to (10) minutes.

Listing 1 - 10 of 13 << page
of 2
>>
Sort by
Narrow your search

Resource type

article (13)


Language

English (13)


Year
From To Submit

2017 (3)

2016 (3)

2014 (2)

2012 (1)

2011 (1)

More...