11622

10671

كارشناسي ارشد

سيستم هاي اقتصادي و اجتماعي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده صنايع و سيستم ها

1395

دوازده،67ص.: مصور،جدول،نمودار

ص.ع.به فارسي و انگليسي

محمد سعيد صباغ

ناصر ملاوردي، حميد ميرمحمدي

1395/08/04

مهندسي صنايع و سيستم ها

ID10671

چكيده مسئئله تخصئيص سئه بعدي كمينه كردن هزينه تخصئيص اعساي سه مجموعه n عسوي مثل مجموعههاي اساتيد دانشجويان و پروژهها به يكديگر اسئت به طوري كه هر عسئو در هر مجموعه دقيق به يك عسو از اعساي دو مجموعه ديگر تخصيص داده شود برخالف مسئله تخصئيص دو بعدي مسئئله تخصئيص سئه بعدي از مسئايل NP Hard است كه كمتر به آن پرداخته شده است مسئله تخصيص سه بعدي خود به دودسئته محوري و مسئطح تقسئيم ميشود و نوع محوري آن در اين تحقيق مورد مطالعه قرار گرفته است در اين پژوهش الگوريتم حذف مسئتطيل همزاد منفي كه در سئال 9512 براي مسئله تخصيص دو بعدي ارايه شده است براي سه بعد گسترش داده ميشود و دستهاي از مسئايل تخصئيص سئه بعدي كه ميتوان با به كار بردن اين روش به جواب بهينه رسئيد شناسايي ميشوند مفهوم مكعب مستطيل در سه بعد و چند راه ابتكاري براي شناسايي مكعبهاي مستطيل ارايه ميشود سپس نتايج اين الگوريتم با نتايج بدست آمده توسط الگوريتم هاي ديگر مقايسئه ميشود روش اجرا شده در مسايلي كه داراي فاصله همزاد صفر هستند عملكرد قابل قبولي دارد و در ساير موارد نيز ميتوان آن را به عنوان يك حد پايين مناسب براي مسئله تخصيص در نظر گرفت كلمات كليدي 5 مسئله تخصيص سه بعدي 2 مكعب مستطيل همزاد منفي 9 مسئله اوليه 4 مسئله همزاد

Extension of negative dual rectangle cancellation algorithm as a heuristic method for axial three dimensional assignment problem Mohammad Amani mohammad amani@in iut ac ir Date of Submission 30 5 2016 Department of Industrial and System Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Mohammad S Sabbagh sabbagh@cc iut ac irAbstractThree dimensional assignment problem is to minimize the assignment cost of members ofthree n member sets to each other so that every member in every set is exactly allocated toa member from two other sets Unlike two dimensional assignment problem three dimensional assignment problem has been shown to be NP Hard and is less studied Three dimensional assignment problems are classified into two groups axial and planar This studyinvestigates the former that is axial In this research negative dual rectangle cancellationalgorithm is introduced for two dimensional assignment problems is extended for three dimensional ones Then a class of three dimensional problems that can be solved tooptimality is identified Concept of rectangular cubes in three dimensions and identificationmethods of these cubes are presented At the end numeric result are presented The proposedalgorithm shows an acceptable performance in the all assignment problems with zero dualitygap Also algorithm finds an appropriate lowerbound Keywords Three dimensional assignment problem Negative dual rectangle cube Primal model Dual model

محمد سعيد صباغ

ناصر ملاوردي، حميد ميرمحمدي