دانلود مقاله ISI انگلیسی شماره 19084 + ترجمه فارسی
عنوان فارسی مقاله

رويكرد موازی عامل گرا برای مسئله ی زمان بندی كار فروشگاه با الگوريتم های ژنتيكی

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی
19084 2010 9 صفحه PDF 16 صفحه WORD
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
An agent-based parallel approach for the job shop scheduling problem with genetic algorithms
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Mathematical and Computer Modelling, Volume 52, Issues 11–12, December 2010, Pages 1957–1965

فهرست مطالب ترجمه فارسی
چكيده
كلمات كليدي
1- مقدمه
2- رويكرد عامل گرا براي مسئله ي زمان بندي كار فروشگاه
1.2 معماري عامل گرا
شكل 1- لايه هاي معماري عامل گراي مطروحه
شكل 2- معماري عامل گراي مطروحه براي مسئله ي زمان بندي كار فروشگاه. 
2.2 جمعيت اوليه
3.2 الگوريتم ژنتيكي موازي
شكل 3- فرايند زمان بندي MA و Ai
جدول 1- مثالي از مسئله ي زمان بندي كار فروشگاه 4 x 4
1.3.2 سياست مهاجرت
2.3.2 بازنمايي كروموزوم
شكل 4- مثال PMX
شكل 5- مثال جهش
3.3.2 تابع برازندگي
4.3.2 انتخاب
5.3.2 اپراتور كراس اور 
6.3.2 اپراتور جهش
7.3.2 مكانيسم ترميم
3- اجرا و نتايج آزمايشگاهي
شكل 6- PaGA درمقايسه با SaGA بهترين راه حل را مي يابد. مسئله ي تست: LA26. نتايج ميانگين هاي بهترين راه حل ها ظرف 10 اجرا هستند. 
شكل 7- PaGA بهترين راه حل را درمقايسه با SaGA مي يابد. مسئله ي تست: LA16. نتايج ميانگين هاي بهترين راه حل ها ظرف 10 اجرا هستند. 
شكل 8- PaGA بهترين راه حل را درمقايسه با SaGA مي يابد. مسئله ي تست: LA32. نتايج ميانگين هاي بهترين راه حل ها ظرف 10 اجرا هستند. 
جدول 2- مقايسه هاي بين طول هاي زمان بندي يافت شده با PaGA و SaGA روي نمونه هاي FT
جدول 3- مقايسه هاي بين طول هاي زمان بندي يافت شده با PaGA و SaGA روي نمونه هاي ORB
جدول 4- مقايسه هاي بين طول هاي زمان بندي يافت شده با PaGA و SaGA روي نمونه هاي LA
جدول 5- مقايسه هاي بين طول هاي زمان بندي يافت شده با PaGA و SaGA روي نمونه هاي LA
4- نتيجه گيري
کلمات کلیدی
مشکل زمان بندی تولید کارگاهی - الگوریتم های ژنتیکی موازی - عوامل - سیستم های چند عامله
ترجمه چکیده
مسئله ی زمان بندي كار فروشگاه يكي از مهمترين و پيچيده ترين مسائل در زمان بندي ماشيني است. اين مسئله با عنوان ان- پي سخت توصيف مي شود. پيچيدگي بالاي مسئله، يافتن راه حل بهينه را در زمان منطقي در غالب موارد سخت مي سازد. بنابراين جستجوي راه حل هاي ي تقريبي در زمان چندجمله اي بجاي راه حل هاي دقيق با هزينه ي بالا براي نمونه هاي دشوار مسئله ترجيح داده مي شود. روش هاي متا اكتشافي همچون الگوريتم هاي ژنتيكي براي يافتن راه حل هاي بهينه يا نزديك بهينه براي مسئله ي زمان بندي فروشگاه بسيار استفاده مي شوند. موازي سازي الگوريتم هاي ژنتيكي يكي از بهترين رويكردهايي است كه مي توان براي ارتقاي عملكرد اين الگوريتم ها بكاربرد. در اين مقاله رويكرد موازي عامل گرا را براي مسئله اي مطرح مي كنيم كه درآن خلق جمعيت اوليه و موازي سازي الگوريتم ژنتيكي به روش عامل گرا انجام مي شوند. نمونه هاي مبنا (محك) براي بررسي عملكرد رويكرد مطروحه استفاده مي شوند. نتايج نشان مي دهند كه اين رويكرد، راندمان را اصلاح مي كند.
ترجمه مقدمه
مسئله ي زمان بندي كار فروشگاه يكي از مهمترين مسائل در زمان بندي ماشيني است و در صنعت كارخانه داري ازنظر اصلاح بهره برداري از ماشين و كاهش سيكل زماني توليد كار مهمي بشمارمي آيد. اين مسئله به شرح ذيل تشريح مي شود. مجموعه اي از n كار و مجموعه اي از m ماشين تعيين مي شوند. هر كار شامل توالي mi عملياتي هستند كه بايد با ترتيب معين پردازش شوند. Oij عمليات j ام كار i است كه بايد روي ماشين Mk براي دوره ي زمان پردازش tik پردازش شود. Mk و tik براي هر عمليات Oij ازقبل تعيين مي شوند و حق شفعه مجاز نيست. هر ماشين مي تواند صرفاً يك كار را پردازش كند و هر كاري صرفاً توسط يك ماشين در يك زمان پردازش مي شود. مدت زماني كه عمليات همه ي كارها انجام مي شوند به زمان کامل شدن پردازش منسوب مي شود. زمان بندي، توالي اجراي همه ي عمليات را براي همه ي كارها روي ماشين ها تعيين مي كند. هدف، يافتن زمان بندي بهينه است. زمان بندي بهينه، زمان كمينه سازي پردازش كامل است. مسائل زمان بندي كار فروشگاه بعلت انفجار عاملي به عنوان عضوي از رده ي بزرگ مسائل عددي رام نشدني معروف به ان- پي سخت لحاظ مي شوند. پيچيدگي بالاي مسئله آن را سخت مي كند و دربرخي موارد، يافتن راه حل بهينه را در زمان منطقي غيرممكن مي سازد. بنابراين جستجوي راه حل هاي تقريبي در زمان چندجمله اي بجاي راه حل هاي دقيق با هزينه ي بالا براي نمونه هاي دشوار مسئله ترجيح داده مي شود. مسئله ي زمان بندي كار فروشگاه اصولاً با استفاده از روش شاخه و كران، قوانين اكتشافي و شيوه ي تغییرسمت دادن گلوگاه تيمارشده است. در ساليان اخير، روش هاي متا اكتشافي براي اين مسئله بطور گسترده استفاده شده اند. اين روش ها همچون جستجوي تابو، آنيلينگ شبيه سازي شده، الگوريتم هاي ژنتيكي، شبكه هاي عصبي و بهينه سازي كلوني مورچه براي حل مسائل پيچيده با هزينه هاي بالا كاملاً مناسب هستند. خلاصه اي از تكنيك هاي زمان بندي كار در [1] يافت مي شود. الگوريتم هاي ژنتيكي درمقايسه با ساير روش هاي متا اكتشافي براي يافتن بهترين راه حل ها يا نزديك به بهترين ها براي مسائل متعدد بهينه سازي به طور گسترده استفاده مي شوند. بسياري از رويكردهاي مبني بر الگوريتم ژنتيكي براي مسائل زمان بندي كار فروشگاه مطرح شده اند. مولفين در [26,27] رويكردي را معرفي مي كنند كه از تعادل بار ماشين ها به عنوان يك پارامتر مهم در تخصيص كار استفاده مي كند. مزيت اين رويكردها آن است كه بهره برداري از ماشين را درعين كمينه سازي زمان کامل شدن پردازش بيشينه مي سازند. Ombuki و Ventresca الگوريتم ژنتيكي جستار داخلي را مطرح كردند كه از استراتژي بازنمايي راه حل كارآمد استفاده مي كند و در آن از چك كردن محدوديت ها و مكانيسم تعمير اجتناب مي شود. اپراتور شبه جهشي جديد در فاز جستار داخلي براي اصلاح كيفيت راه حل استفاده مي شود. آنها همچنين استراتژي هيبريد را با استفاده از الگوريتم ژنتيكي تقويت شده با جستار تابو براي مسئله ايجادكردند. لين و همكاران مدل هيبريد شامل الگوريتم هاي ژنتيكي دانه درشت متصل به توپولوژي سَبك دانه ريز را معرفي كردند. روش آنها از همگرايي نابهنگام جلوگيري مي كند و نتايج عالي را درمورد مسائل زمان بندي كار فروشگاه مبنا ايجادكرد. روش هاي متا اكتشافي همچون شبكه هاي عصبي، آنيلينگ شبيه سازي شده و جستار داخلي با الگوريتم هاي ژنتيكي براي ارائه ي راندمان بالا در يافتن راه حل هايي براي مسئله استفاده شدند. چن و همكاران خلاصه ي آموزشي از تحقيقات اخير را درمورد كاركردهاي متعدد هيبريد الگوريتم هاي ژنتيكي مطروحه تاكنون براي مسئله ي زمان بندي كار فروشگاه ارائه كردند. وانگ و ژنگ با تركيب الگوريتم هاي ژنتيكي و آنيلينگ شبيه سازي شده يك چهارچوب بهينه سازي هيبريد با اجراي آسان، موازي و كلي را ايجادكردند و آن را براي مسائل زمان بندي كار فروشگاه مبنا اعمال كردند. برخي مسائل زمان بندي كار فروشگاه مبنا براساس طرح رمزگذاري موثر و برخي اپراتورهاي بهينه سازي ويژه با استراتژي بهينه سازي هيبريد كاملاً حل مي شوند. مولفين در [17] الگوريتم ژنتيكي هيبريد را مطرح كردند. زمان بندي ها در رويكرد آنها با استفاده از قانون حق تقدم ساخته مي شوند كه اولويت ها ازطريق الگوريتم ژنتيكي تعيين مي شوند. زمان بندي ها با استفاده از روشي ساخته مي شوند كه زمان بندي هاي فعال پارامتري شده را ايجادمي كند. اكتشافي جستار داخلي پس از كسب يك زمان بندي براي اصلاح راه حل اعمال مي شود. يك روش هيبريد در [19] براي كسب راه حل بهينه ي نزديك بهينه در ميزان زمان منطقي مطرح مي شود. اين روش از رويكرد شبكه ي عصبي براي ايجاد راه حل هاي امكانپذير اوليه و سپس الگوريتم آنيلينگ شبيه سازي براي بهبود كيفيت و راندمان راه حل هاي اوليه براي ايجاد راه حل بهينه يا نزديك بهينه استفاده كرد. چن و همكاران الگوريتم ژنتيكي عامل گرا را مطرح كردند كه خلق جمعيت اوليه را سرعت مي بخشد. پردازش انتخاب، كراس اور و جهش در اين رويكرد با يك روش هوشمند كنترل مي شوند. در اين مقاله، الگوريتم ژنتيكي موازي عامل گرا را براي مسئله ي زمان بندي كار فروشگاه مطرح مي كنيم. جمعيت اوليه در رويكرد ما با روش عامل گرا با استفاده از روش مطروحه در [31] حل مي شود و سپس روش عامل گرا براي موازي سازي الگوريتم ژنتيكي استفاده مي شود. الباقي مقاله به شرح ذيل مرتب شده است. در بخش 2 جزئيات معماري عامل گراي مطروحه و الگوريتم ژنتيكي موازي را ارائه مي كنيم. در بخش 3 اجرا و نتايج آزمايشي رويكرد مطروحه را بحث مي كنيم. نتيجه گيري در بخش 4 ارائه شده است.
پیش نمایش مقاله
پیش نمایش مقاله رويكرد موازی عامل گرا برای مسئله ی زمان بندی كار فروشگاه با الگوريتم های ژنتيكی

چکیده انگلیسی

The job shop scheduling problem is one of the most important and complicated problems in machine scheduling. This problem is characterized as NP-hard. The high complexity of the problem makes it hard to find the optimal solution within reasonable time in most cases. Hence searching for approximate solutions in polynomial time instead of exact solutions at high cost is preferred for difficult instances of the problem. Meta-heuristic methods such as genetic algorithms are widely applied to find optimal or near-optimal solutions for the job shop scheduling problem. Parallelizing the genetic algorithms is one of the best approaches that can be used to enhance the performance of these algorithms. In this paper, we propose an agent-based parallel approach for the problem in which creating the initial population and parallelizing the genetic algorithm are carried out in an agent-based manner. Benchmark instances are used to investigate the performance of the proposed approach. The results show that this approach improves the efficiency.

مقدمه انگلیسی

The job shop scheduling problem is one of the most important problems in machine scheduling, and it is an important task for the manufacturing industry in terms of improving machine utilization and reducing product cycle-times. This problem can be described as follows. A set of nn jobs {Ji}1≤i≤n{Ji}1≤i≤n and a set of mm machines {Mr}1≤r≤m{Mr}1≤r≤m are given. Each job consists of a sequence of mimi operations Oi1,Oi2,…,OimiOi1,Oi2,…,Oimi that must be processed in a specified order. OijOij is the jjth operation of job ii that must be processed on machine MkMk for a processing time period tiktik. For each operation OijOij, MkMk and tiktik are predefined and preemption is not allowed. Each machine can process only one job and each job can be processed by only one machine at a time. The duration in which all operations for all jobs are completed is referred to as the makespan. A schedule determines the execution sequence of all operations for all jobs on machines. The objective is to find the optimal schedule. The optimal schedule is the schedule that minimizes the makespan. Due to factorial explosion of possible solutions, job shop scheduling problems are considered to be a member of a large class of intractable numerical problems known as NP-hard [1]. The high complexity of the problem makes it hard and in some cases impossible to find the optimal solution within reasonable time. Hence, searching for approximate solutions in polynomial time instead of exact solutions at high cost is preferred for difficult instances of the problem. Historically, the job shop scheduling problem has been primarily treated using the branch and bound method [2], [3] and [4], heuristic rules [5], [6] and [7] and the shifting bottleneck procedure [8]. In recent years, meta-heuristic methods have been widely applied to this problem. These methods, such as taboo search [9], [10] and [11], simulated annealing [12], [13], [14] and [15], genetic algorithms [16], [17], [18], [19] and [20], neural networks [21] and ant colony optimization [22], [23], [24] and [25], are well suited to solving complex problems with high costs. A survey of job shop scheduling techniques can be found in [1]. Compared with other meta-heuristic methods, genetic algorithms are widely used to find the best or near-best solutions for various optimization problems. Many genetic algorithm-based approaches have been proposed for job shop scheduling problems. In [26] and [27], the authors introduce an approach that uses load balancing of machines as an important parameter in job assignment. An advantage of these approaches is that they maximize machine utilization while minimizing the makespan. Ombuki and Ventresca [28] proposed a local search genetic algorithm that uses an efficient solution representation strategy in which both checking of the constraints and repair mechanism can be avoided. In their approach, at the local search phase a new mutation-like operator is used to improve the solution quality. They also developed a hybrid strategy using the genetic algorithm reinforced with a taboo search for the problem. Lin et al. [29] introduced a hybrid model consisting of coarse-grain genetic algorithms connected in a fine-grain style topology. Their method can avoid premature convergence, and it produced excellent results on standard benchmark job shop scheduling problems. Meta-heuristic methods such as neural networks, simulated annealing and local search were used with genetic algorithms to provide high performance in finding solutions for the problem [17], [19] and [20]. Chen et al. [30] gave a tutorial survey of recent works on various hybrid approaches of the genetic algorithms proposed so far for the job shop scheduling problem. Wang and Zheng [20], by combining simulated annealing and genetic algorithms, developed a general, parallel and easily implemented hybrid optimization framework, and applied it to the job shop scheduling problem. Based on an effective encoding scheme and some specific optimization operators, some benchmark job shop scheduling problems are well solved by the hybrid optimization strategy. In [17], the authors proposed a hybrid genetic algorithm. In their approach, the schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained, a local search heuristic is applied to improve the solution. In [19], a hybrid method is proposed to obtain a near-optimal solution within a reasonable amount of time. This method uses a neural network approach to generate initial feasible solutions and then a simulated annealing algorithm to improve the quality and performance of the initial solutions in order to produce the optimal/near-optimal solution. Chen et al. [31] proposed an agent-based genetic algorithm that accelerates the creation of the initial population. In this approach, the processing of selection, crossover and mutation can be controlled in an intelligent way. In this paper, we propose an agent-based parallel genetic algorithm for the job shop scheduling problem. In our approach, the initial population is created in an agent-based way by using the method proposed in [31], and then an agent-based method is used to parallelize the genetic algorithm. The reminder of this paper is organized as follow. In Section 2, we give the details of our proposed agent-based architecture and parallel genetic algorithm. In Section 3, we discuss the implementation and experimental results of the proposed approach. Our conclusion is given in Section 4.

نتیجه گیری انگلیسی

The job shop scheduling problem is an important and complicated problem in machine scheduling. In this paper, we have proposed an agent-based parallel genetic algorithm for this problem. Use of software agents accelerated the creation of the initial population of genetic algorithm. To enhance the performance of our genetic algorithm, we parallelized it using an agent-based method. We compared the performance of our parallel agent-based approach with that of a serial agent-based method. The results showed that the parallel method improves the quality of the solutions obtained. Future work will concentrate on improving the performance of our method and applying it to similar problems.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.