پديد آورنده :
ساجدي، حسين
عنوان :
مسئله كمينه سازي مجموع زمان هاي تكميل در زمان بندي ماشين هاي موازي با زمان هاي آماده سازي و كارهاي تقسيم پذير
مقطع تحصيلي :
كارشناسي ارشد
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده صنايع و سيستم ها
صفحه شمار :
يازده، 55ص.: مصور
استاد راهنما :
قاسم مصلحي
توصيفگر ها :
شاخه و كران , مدل رياضي
تاريخ نمايه سازي :
1394/09/03
استاد داور :
مهدي بيجاري، حميد ميرمحمدي
تاريخ ورود اطلاعات :
1396/10/05
رشته تحصيلي :
صنايع و سيستم ها
دانشكده :
مهندسي صنايع و سيستم ها
چكيده فارسي :
چكيده زمانبندي تخصيص منابع در طول زمان براي اجراي مجموعه اي از وظايف است مسئله تخصيص منابع در طول زمان براي اجرا مجموعهاي از وظايف در وضعيتهاي مختلف مطرح ميشود در تئوري زمان بندي معموال از منابع با عنوان ماشين و از وظايف با عنوان كار نام برده ميشود از جمله اهداف مهم زمانبندي ميتوان به بهره برداري كارا از منابع پاسخگويي سريع به تقاضا و انطباق دقيق زمانهاي تحويل با موعد تحويل تعيين شده اشاره نمود يكي از زمينههاي زمانبندي كارها زمانبندي كارهاي تقسيم پذير ميباشد كارهاي تقسيم پذير با توجه به ويژگيهاي ساختاري خود مي توانند به دو دسته كارهاي تقسيم پذير پيوسته و يا گسسته تقسيم شوند در دسته اول امكان شكست كار به هر صورت دلخواه و در هر اندازه اي از واحد زمان وجود دارد اما در دسته دوم هر كار از واحد هاي كاري تشكيل ميشود و زيركارهاي هر كار از نظر زماني مضرب صحيح از واحدهاي كاري مي باشد هر دو دسته ذكر شده در صنعت كاربرد هاي فراواني دارد و ميتوان آنها را با ويژگي هاي منحصر به فرد خود مورد بررسي قرار داد تقسيمپذيري نيز نوعي از ويژگي كارها مي باشد كه با توجه به انواع محيطهاي كارگاهي دسته بندي جديدي را در مسائل زمانبندي ايجاد مينمايد تقسيم پذيري در كارها به نوعي همان انقطاع در كارها ميباشد با اين تفاوت كه كارهاي تقسيم شده ميتوانند همزمان پردازش شوند در اين تحقيق مسئله زمانبندي كمينهسازي مجموع زمانها تكميل در زمانبندي ماشينهاي موازي با زمانها آمادهسازي وكارهاي تقسيمپذير مورد بررسي قرار گرفته است با توجه به مطالعات انجام شده براي مسئله در ابتدا با طراحي اصول غلبه مسئله و استفاده از آنها مدلهاي رياضي و الگوريتم شاخه و كران ارائه ميگردد با توجه به پيچيدگي مسئله الگوريتمهاي شاخه و كران و مدلهاي رياضي براي رسيدن به جواب بهينه در مسائل با ابعاد متوسط نيازمند صرف زمان بسيار زيادي هستند از اين رو در ادامه به منظور بهدست آوردن جوابهاي خوب براي ابعادي از مسائلي كه روش هاي بهينه قادر به حل آنها در زمان معقول نميباشند يك الگوريتم ابتكاري ارائه ميگردد كه مسئله را در دو مرحله شامل ايجاد جواب اوليه و بهبود آن حل مينمايد نتايج محاسباتي براي مسئله زمانبندي كمينهسازي مجموع زمانها تكميل در زمانبندي ماشينهاي موازي با زمانها آمادهسازي وكارهاي تقسيمپذير نشان داد كه الگوريتم شاخه وكران ارائه شده نسبت به دو مدل رياضي از كارايي بهتري برخوردار بوده و توانست مسائل با اندازه 75 واحد كاري به ازاي 8 ماشين و 3 كار را در محدوده زماني 6609 ثانيه حل نمايد الگوريتم ابتكاري ارائه شده نيز توانايي حل مسائل تا ابعاد 57 واحد كاري به ازاي 3 كار و 8 ماشين را با متوسط درصد خطاي 2 5 درصد دارد كلما كليدي زمانبندي ماشينهاي موازي تقسيمپذيري شاخه و كران مدل رياضي
چكيده انگليسي :
Minimizing Total Completion Time in Parallel Machines Scheduling Problem with Setup Times and Splitting Jobs Hossein Sajedi h sajedi@in iut ac ir Data of Submission 16 September 2015 Department of Industrial Engineering Isfahan University of technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor Ghasem Moslehi Moslehi@cc iut ac ir Abstract Scheduling is resource allocation through time to implement a series of tasks The allocation of resources over time to run a series of tasks arise in different positions In scheduling theory resources usually referred as a machines and tasks referred as jobs Some of the important objective of scheduling are efficient use of resources quick response to demand and adaption of delivery dates with pre specified due date One of fields of scheduling is splitting job scheduling Splitting jobs according to their structural characteristics can divided into two categories continuous or discrete splitting jobs In the first category it is possible to split jobs into any form and size but the second category consist of unit jobs and processing time of sub jubs is an integer multiple unit jobs processing time Both mentioned categories are applicable in many industrial case and they can be discussed with their own unique characteristics Splitting jobs is the same kind of interruption in job with a difference that splitting jobs can processed at the same time In this research minimizing total completion time in parallel machines scheduling problem with setup times and splitting jobs has been studied According to studies firstly some dominance rules were developed and used to propose mathematical models and branch and bound algorithms According to the complexity of the problem branch and bound algorithms and mathematical models need lots of time to achieve the optimal solution in medium size problems Hence in order to obtain good solutions for the size of the problems that optimal method cannot solve them in a reasonable time a heuristic algorithm was presented that solves problem in two phases create basic solution and improvement it The computational results for minimizing total completion time in parallel machines scheduling problem with setup times and splitting jobs indicated that performance of the proposed branch and bound algorithm is better than the mathematical models and can solves problem with 27 unit jobs over 8 machines and 9 jobs in the time limit 3600 seconds Heuristic algorithm also can solves problem whit average error less than 2 5 for instant of problems with 72 unit jobs over 8 machines and 9 jobs Keywords Scheduling Parallel Machine Splitting Branch and Bound Mathematical Model
استاد راهنما :
قاسم مصلحي
استاد داور :
مهدي بيجاري، حميد ميرمحمدي
