6 نتیجه برای Job Shop Scheduling
، ،
جلد 20، شماره 2 - ( 6-1388 )
چکیده
مساله زمانبندی کار کارگاهی سنتی یک مساله NP-Complete از نوع قوی است و به همین دلیل در تحقیقات صورت گرفته، الگوریتمهای فراابتکاری زیادی برای حل آن ارایه شده است، اما تنها در تعداد معدودی از آنها الگوریتم بهینهسازی دسته ذرات (PSO) مورد توجه قرار گرفته است که یکی از دلایل آن میتواند جدید بودن این روش باشد. در الگوریتم ارایه شده در این مقاله ابتدا بمنظور حفظ موجه بودن جوابها در هر تکرار الگوریتم شیوه نمایش بر مبنای فهرست اولویت برای جوابها انتخاب شده است. همچنین برای ایجاد رابطه یک به یک بین جواب مساله که ماهیت گسسته دارد و جواب مورد پذیرش الگوریتم که اعداد پیوسته هستند و همچنین حفظ قانونی بودن جوابها در هر تکرار، یک شیوه جدید بر اساس تبدیل مبنای اعداد و با استفاده از نمایش اعداد در مبنای فاکتوریل توسعه داده شده است. با توجه به تکاملی بودن PSO، بمنظور شروع از جوابهای نسبتا خوب از یک الگوریتم ابتکاری جستجوی تصادفی حریصانه به عنوان مولد جوابهای اولیه استفاده شده است. هر جواب بدست آمده توسط PSO بوسیله یک الگوریتم جستجوی محلی بهبود داده میشود. برای فرار از دام بهینههای محلی یک رابطه جدید بهنگام سازی سرعت در الگوریتم PSO توسعه داده شده است. به همین منظور و همچنین برای بهبود نهایی جواب بدست آمده توسط PSO از یک الگوریتم آنیلینگ شبیهسازی شده استفاده شده است. الگوریتم بر روی تعدادی از مسایل نمونه آزمایش شده و نتایج حاصل بیانگر دقت و کارایی جوابها نسبت به سایر الگوریتمهای موجود برای حل مساله مورد بحث است.
، ،
جلد 21، شماره 4 - ( 11-1389 )
چکیده
بابک یوسفی یگانه ، نرگس خانلرزاده، ، علی رحیمی فرد، ،
جلد 22، شماره 4 - ( 12-1390 )
چکیده
مسئله زمانبندی کارِ کارگاهی منعطف Flexible Job Shop)) ، حالت توسعه یافته زمانبندی کارِ کارگاهی Job Shop)) است که در آن هر عملیات میتواند توسط بیش از یک ماشین از میان مجموعه ماشینهای موجود انجام شود. این مسئله در زمره مسائل NP-hard طبقه بندی میشود و برای حل آن با دو زیر مساله مواجه هستیم. نخست اینکه، نحوه تخصیص هر فعالیت به ماشینی از میان ماشینهای موجود که قادر به پردازش فعالیت مورد نظر است تعیین شود و سپس توالی فعالیتهای تخصیص یافته مشخص گردد. واضح است که دستیابی به پاسخ بهینه، حتی در ابعاد کوچک دشوار و بسیار زمانبر است در این مقاله یک الگوریتم ممتیک جهت کمینه کردن حداکثر زمان تکمیل و بدست آوردن جواب بهینه مسائل کوچک و بهترین جواب مسایل متوسط و بزرگ ارائه می شود.در این مقاله همچنین به منظور بهبود جواب های حاصل از الگوریتم ممتیک و کاهش حداکثر زمان تکمیل فرض ایجاد وقفه در انجام کارها را نیز در نظر میگیریم.
آقای علی نمازی، حمیدرضا گلمکانی،
جلد 23، شماره 4 - ( 12-1391 )
چکیده
در حوزه زمانبندی عملیات، یکی از فرضیات رایج، فرض در دسترس بودن ماشینها در افق برنامهریزی است. واضح است که در عمل، ممکن است یک ماشین، به دلایل مختلف، نظیر وقوع خرابی و یا لزوم انجام فعالیتهای نگهداری و تعمیراتِ پیشگیرانه، موقتا در دسترس نباشد. در این تحقیق مساله زمانبندی کارِ کارگاهیِ چند مسیره2 با لحاظِ محدودیت در دسترس نبودنِ ماشینها در دورههایِ زمانیِ از قبل مشخص شده، و با هدفِ کاهش زمانِ انجام کارها مورد بررسی قرار میگیرد. ابتدا مدلِ برنامهریری غیرخطیِ صفر و یک برای مسئله مذکور ارائه میگردد. از آنجا که بدلیل پیچیدگی این مسئله، حل دقیق آن از روشهای معمول میسر نیست، یک الگوریتم ابتکاری، بر مبنای الگوریتم سیستم ایمنی مصنوعی، نیز ارائه خواهد شد. همچنین جهت ارزیابی عملکرد الگوریتم پیشنهادی، 30 مسئله در ابعاد کوچک، متوسط و بزرگ طراحی و توسط الگوریتم مذکور حل و نتایج آن ارائه شده است. از نقطه نظرِ زمان مورد نیاز برای تولید جواب و مقدار بدست آمده برای تابع هدف، نتایج حاکی از عملکرد مطلوب الگوریتم پیشنهادی است.
احمد جعفرزاده افشاری، محمدرضا امین ناصری،
جلد 24، شماره 1 - ( 3-1392 )
چکیده
افزودن پیچیدگیها و انعطاف پذیریهای موجود در سامانه های تولید واقعی به مفروضات مدلهای کلاسیک زمان بندی، گرچه منجر به افزایش قابل توجه پیچیدگی مسائل می گردد، اما به دلیل بهبود چشمگیری که در عملکرد این سامانه ها ایجاد می کند، از دو جنبه نظری و کاربردی حائز اهمیت است. در این پژوهش سه فرض اصلی مساله زمان بندی استقرار کارگاهی مورد بازنگری قرار گرفته که حاصل آن مدلی است با سه نوع انعطاف و قابل انطباق با بسیاری از محیطهای تولید واقعی؛ انعطاف در توالی، انعطاف در ماشین و انعطاف در زمان عملیات. پس از تعریف مساله و بیان آن در قالب یک مدل ریاضی، یک روش حل کارا مبتنی بر جستجوگر محلی ژنتیک برای آن توسعه داده شده است. به این منظور ابتدا عملگرها و رویه های ویژه ای، منطبق با مختصات مساله، شامل ایجاد جمعیت اولیه، تقاطع و جهش برای الگوریتم ژنتیک طراحی شده اند. سپس یک تابع جستجوگر محلی بدیع با هدف ارتقا توان جستجوی الگوریتم ژنتیک توسعه یافته و با آن تلفیق شده است. در بخش نتایج عددی، کارآمدی الگوریتم پیشنهادی در یافتن جوابهای بهینه و نزدیک به بهینه با حل تعدادی مساله نمونه که با افزودن قابلیت انعطاف در زمان عملیات به مسائل موجود در ادبیات به دست آمده اند، نشان داده شده است.
مجید وفایی جهان، مسعود نصرت آبادی، محمدرضا اکبرزاده توتونچی،
جلد 24، شماره 3 - ( 9-1392 )
چکیده
مساله زمانبندی کارکارگاهی بهبررسی نحوه توزیع کارها بین ماشین ها می پردازد به طوری که کارها در کمترین زمان ممکن انجام شوند. در این مساله فاکتورهایی نظیر زمان پردازش فعالیت ها و زمان موعد مقرر برای تحویل کارها، اغلب بصورت مبهم برای تحلیل گر تعریف می شوند. در چنین شرایطی، استفاده از پارامترهای فازی و اهداف چندگانه مبتنی بر علم فازی، لازم به نظر می رسد. که باعث ایجاد مساله زمانبندی کارکارگاهی فازی می شود. این مساله از مسائل غیر چندجمله ای (NP) می باشد، به همین دلیل روشی مبتنی بر الگوریتم اکتشافی بهینه سازی اکسترمال پیشنهاد می شود. به طوری که فعالیت های کم ارزش را با احتمال بیشتر انتخاب و تغییر می دهد، این باعث می شود تعداد فعالیت های کم ارزش، کمتر و تعداد فعالیتهای با ارزش یکسان، بیشتر شود در این حالت هر تغییر جزئی در زمانبندی، تغیرات زیادی در آن ایجاد می کند بنابراین باعث فرار از بهینه محلی شده و به سمت بهینه سراسری حرکت میکند. با توجه به نتایج حاصل از شبیه سازی بر روی داده های آزمایشی 6×6 و 10×10، روش پیشنهادی، رضایتمندی مطلوبی از اهداف مساله را با سرعت همگرایی مناسب، در مقایسه با روش های دیگر نشان می دهد، درستی جواب های ارائه شده و همچنین صحت روش پیشنهادی با استفاده از اصل همگرایی، آزمون آماری t و خطای امکان پذیری(F) اثبات شده است.