research centers


Search results: Found 2

Listing 1 - 2 of 2
Sort by

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
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.

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

Listing 1 - 2 of 2
Sort by
Narrow your search

Resource type

article (2)


Language

English (2)


Year
From To Submit

2016 (2)