بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
زمانبندی جاب شاپ با هدف توازن بار با استفاده از الگوریتم ژنتیک
چکیده
مسئله زمانبندیٌ job shop با هدف توازن بارٍ در دنیای واقعی با ماشین آلات مشابه بررسی شده که هدف اصلی الگوریتم توازن بار ، تق سیم مقادیر زیادی از کارهایی در ما شین آلات یک سان به منظور کاهش زمان کل توان عملیاتیَ کار در جهت بهبودُ ا ستفاده از ماشین ها و یا دستگاه ها می باشد .
الگوریتم ژنتیک توسعه یافته تا با استفاده از تابع ارزیابی, توازن بار ایجاد شده را در زمانبندی بررسی نماید. توازن بار در الگوریتم ژنتیک چند منظوره که کمترین متوســط تاخیر ورود یا دیرکرد ,تعداد کارهای دارای تاخیر, زمان تنظیمات , مدت زمان بیکاری ماشین و زمان حاصل از اجرای کار را به حداقل می رساند.
کلمات کلیدی : زمانبندی جاب شاپ ، الگوریتم ژنتیک، توازن بار
-1 مقدمه
مشـــخص نمودن یک ز مانبندی موثر و عمل یات پی در پی در بر نامه ریزی تولیدات صنعتی و یا کارگاهی یکی از عوامل مهم و کارامد در هر صــنعت تولیدی و یا گارگاهی می باشــد زیرا زمانبندی می تواند باعث افزایش ســرمایه ، کاهش و یا محدود کردن زمان بیکاری ماشــین ها و پی شرفت در بهره وری ما شین آلات و ر سیدگی و به پایان ر ساندن به موقع کارهای سفارش داده شده تو سط م شتریان یا تامین مواد اولیه و قطعات مورد نیاز در مدت زمان مناســب در صــنعت می باشــد . هدف ز مانب ندی تول ید تخصـــیص م نابع م حدود در طول ز مان برای ان جام گروهی از فعالیت های رقیب ا ست . دا شتن یک برنامه زمانبندی تولید منا سب ، تاثیر زیادی بر افزایش کارائی و د ستر سی به اهداف سازمان دارد.[1] مدل زمانبندی با توجه به اهداف صنعت تولیدی و یا گارگاهی بر اساس الویت های دسترسی به هر یک از آنها متفاوت است.
زمانبندی سیستم های تولیدی کارگاهی بر اساس سفارش با محدودیت تعداد ماشــین آلات در هر مرحله و بهینه کردن مجموع مدت تاخیرات مورد برر سی قرار گرفته که با ا ستفاده از الگوریتم ژنتیک با هدف توازن بار در هر یک از ما شین آلات اجرا شده ا ست الگوریتم ژنتیک سعی بر این دارد تا بهترین بهینگی را ارایه دهد.
الگوریتمهای ژنتیک یکی از الگوریتمهای ج ستجوی ت صادفی ا ست که ایده آن برگرفته از طبیعت میباشد. در طبیعت از ترکیب کروموزومهای بهتر، نســــل های بهتری پد ید میآی ند. در این بین گاهی او قات جهشهایی نیز در کروموزومها روی میدهد که ممکن ا ست باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل م سائل میکند ، روند ا ستفاده از الگوریتمهای ژنتیک به صورت زیر میباشد:
الف ) معرفی جوابهای مسئله به عنوان کروموزوم ب) معرفی تابع فیت نس ج) جمعآوری اولین جمعیت د) معرفی عملگرهای انتخاب
ه ) معرفی عملگرهای تولید مثل
در الگوریتمهای ژنتیک ابتدا به طور تصـــادفی یا الگوریتمیک، چندین جواب برای مســئله تولید میکنیم. این مجموعه جواب را جمعیت اولیه مینامیم. هر جواب را یک کروموزوم مینامیم. ســـپس با اســـتفاده از عملگرهــای الگوریتم ژنتیــک پس از انتخــاب کروموزومهــای بهتر، کروموزومها را با هم ترکیب کرده و جهشــی در آنها ایجاد میکنیم. در نها یت نیز جمع یت فعلی را با جمعیت جدیدی که از ترکیب و جهش در کروموزومها حاصل میشود، ترکیب میکنیم در مســـئله زمانبندی job shop مجموعه ای از کارها , که در آن هر کار متشکل از زنجیره ای عملیات است, که به وسیله ی مجموعه ای از ما شین آلات پردازش می شود. هر د ستگاه میتواند یک عملیات را در طول بازه زمانی معین بدون وقفه, بر روی یک ماشـــین معلوم و معین پردازش کند. [2] هدف این ا ست به همان اندازه که بار بر روی ما شین آلات به صورت حداکثری گســـترش می یابد , در حالی که مجموع زمان اجرای کار به حداقل بر سد(یعنی توان بار گ سترده و , max و مجموع زمان عملیات .(minاین را میتوان از انتقال کارها از ســـنگین به ســـبک , زمان بار گذاری ما شین ها بد ست آورد , بطوری که هیچ ما شینی بیکار نبا شد در حالی که کارهایی وجود دارد که برای پردازش شدن در حالت انتظار هستند. [3] [4]
واگذاری کارها به ماشین آلات و تخصیص ماشین ها به اپراطور مربوطه به منظور به حداقل رســاندن عدم تعادل , از وظایف ســنگین در میان اپراتور هاست. یک الگوریتم ژنتیک برای توازن بار در یک سیستم توزیعی توسعه داده است.
در این مقاله ,مشـــکل پیچیده زمانبندی job shop در دنیای واقعی از یک شرکت چاپ را مورد بررسی قرار می دهیم . به منظور جلب رضایت م شتری , شرکت اغلب کارها را به تعداد زیادی تق سیم و تلاش میکند که آنها را به موقع تحویل دهد.[5] هدف الگوریتم ژنتیک با توجه به توازن بار در ماشــین ها ، اختصــاص دادن این مقادیر پر کاربرد به ماشـــین ها می باشـــد , برای به حداقل رساندن متوسط تاخیر ورود یا دیرکرد کارها در برنامه زمانبندی : s
دیر کرد تا زمان تاخیر از کار Jj است, Cj زمان اتمام از کار Jj است و Wj اهمیت نسبی است از کار :Jj
حداقل رساندن تعداد کارهای کندرو در برنامه زمانی
برای به حداقل رســاندن مجموع مدت زمان توان عملیاتی تعریف شــده به عنوان زمان کل کارها که در کارگاه صرف کردند.
حداقل رساندن زمان راه اندازی کل در برنامه ها
که در آن T تعداد کل دوره زمانی در افق برنامه ریزی اســت و برای به حداقل رساندن مجموع مدت زمان بیکاری ماشین آلات که در آن زمان بیکار است به عنوان زمان در افق برنامه ریزی که در طی آن دستگاه ها نه برای استفاده پردازش شغل و نه برای راه اندازی تعریف می شود.
برای به حداقل ر ساندن مجموع مدت زمان توان تعریف شده به عنوان زمان کل صرف شده در کار کارگاهی
که در آن SJ زمانی است که کار Jj پردازشش را شروع میکند.
-2 کارهای انجام شده
الگوریتم های فرا ابتکاری از برخی قوانین طبیعت مثل تکامل زیســتی، فرایندهای فیزیکی و تفکر انسان الهام گرفتهاند. در حال حاضر الگوریتم های ابتکاری که برای مســـاله زمانبندی ســـیســـتم های کارکارگاهی ا ستفاده شدهاند عموماً شامل الگوریتم های م شخص ، ا ستراتژی های تخمینی ،الگوریتم ژنت یک ، الگوریتم جســـتجو حرام ، الگوریتم های ترکیبی ژنتیک و ج ستجو حرام ، بهینه سازی پرندگان و ا ستفاده از الگوریتم جدید متاهیوریستیکْ بر پایه مدیریت سازمان هستند.
در ت مام این الگوریتم ها تعیین یک روش کد گذاری برای ازمایش راه حل ها در قالب کروموزوم یا راه حلهای فردی به عنوان یک کار پایه، ضروری ا ست. اکثر نمایشهای رایج ا ستفاده شده به صورت باینری، عددی و ســمبلیک می باشــد. به عنوان مثال در نمایش عددی هر راه حل فردی یک بردار m*1 اســت، که موقعیت i<m) i>0) بیانگر کار t_i و مقدار درون آن شماره ماشینی است که کار i در آن نگاشت شده است. که تا کنون روش های مختلفی برای حل مسله زمانبندی سیستم های تولید کار کارگاهی ارائه شده است.
اولین » الگوریتم مشخص « برای حل مسأله در سال 1954 ارائه شده ا ست. این تحقیق در نظریه زمانبندی و در تحقیقات بعدی تأثیر زیادی داشـــته اســـت، زیرا در آن برای اولین بار تابع هدف، مینیمم کردن معرفی شده است.
-1-2 هوش مصنوعی
هوش م صنوعی ، کاربرد کامپیوتر بر ا ساس علوم بیولوژیکی می با شد.
بدین ترتیب که از مفاهیم پایه بیولوژیکی برای مدل کردن و یافتن پا سخ مسائل ا ستفاده میشود. در اینجا، تنها روش معروف ( شبکه
های عصـــبی) و کاربرد آن مورد تحلیل قرار می گیرد. روشـــهای دیگر هوش مصنوعی، همچون (ارضای محدودیت) و سیستم های خبره نیز بکار رفته اند که جواب های مناســـبی ارائه نکرده اند. این روش کمک می کند تا جســـتجو برای یافتن جواب بهینه در فضـــای محدودتری صورت گیرد. بعد از اینکه زمان شروع برای هر عملیات اخت صاص داده شــد، تناقض هایی با محدودیتهای مســأله ایجاد می شــود، ســپس این تناقض ها حذف می شوند و جواب بهبود می یابد.
-2-2 شبکه های عصبی
شــبکه های عصــبی، ســاختارهایی الهام گرفته شــده از ســاختار مغز موجودات ابتدایی می باشـــند. در این روش، اطلاعات از شـــبکه ای از ت عداد ز یادی وا حد پردازشـــی (نرون) موازی عبور می ک ند. علیرغم ساختار ساده، به دلیل انجام محاسبات موازی، قدرت یادگیری و تعمیم، شبکه های عصبی جزو محبوبترین روشهای هوش مصنوعی می باشد و کاربرد های زیادی نیز در زندگی واقعی پیدا کرده است.
شــبکه های عصــبی ســاختارهای متفاوتی دارند و برخی از مهمترین ساختار های آن که برای حل مسأله بکار برده شده اند.
-3-2 الگوریتم های ژنتیک
یکی دیگر از روشـــهای کلی بهینه ســـازی، الگوریتم های ژنتیک می با شند که برای حل م سأله نیز به کار رفته اند. الگوریتم های
