g =åw j U j
در ادامه به برخی از مهم ترین معیارهای مورد بحث در مسائل زمانبندی، به طور خلاصه اشاره شده است.
معیار حداکثر زمان تکمیل کل کارها: حداکثر زمان تکمیل کل کارها توسط Cmax نشان داده می شود و به عنوان زمانی که آخرین کار سیستم را ترک می کند تعریف می شود. Cmax =max(C1,C2 ,…,Cn ) که در آن Ci برابر زمان تکمیل کار i ام می باشد.
اهداف وابسته به موعد تحویل: یکی از مهم ترین این اهداف، در نظر گرفتن میزان دیرکرد کارهاست که سعی در حداقل کردن حداکثر تاخیر[۵۷] را دارد. تاخیر کار i به صورت Li =Ci -di تعریف می شود. بنابراین حداکثر تاخیر به صورت Lmax = max(L1,L2 ,…,Ln ) بیان می شود. حداقل کردن حداکثر تاخیر به طور معناداری مرتبط با حداقل کردن بدترین عملکرد زمانبندی می باشد. هدف مهم دیگر، تعداد کارهای دارای دیرکرد[۵۸] است. تعداد کارهای دارای دیرکرد از جمله آماری است که دنبال کردن آن آسان می باشد. بنا براین مدیران اغلب از روی درصد تحویل های به موقع عملکرد تولید را مورد سنجش قرار می دهند. با این وجود، حداقل کردن این هدف می تواند منجر به ارائه زمانبندی شود که در آن برخی از کارها دارای میزان دیر کرد قابل توجهی می باشند، که اغلب در عمل غیر قابل قبول هستند. هدف وابسته به موعد تحویل که این نگرانی را برطرف می کند حداقل سازی کل دیرکرد[۵۹] می باشد. دیرکرد کار i به صورت T = max (0, C i -d i ) تعریف می شود. هیچ یک از توابع هدف توضیح داده شده تکمیل زودتر از موقع کار را جریمه نمی کنند. در عمل، اگرچه معمولا تکمیل زودتر یک کار مطلوب نمی باشد زیرا منجر به هزینه انبار و هزینه های اضافی حمل و نقل می شود.
زمان تکمیل کارها: بازده یک کارگاه که برابر با نرخ خروجی می باشد معمولا توسط ماشین های گلوگاه تعیین می شود. به عبارت دیگر ماشینی که کمترین ظرفیت را در مقایسه با تقاضای ورودی به خود دارد، نرخ محصولات خروجی را تعیین می کند. در نتیجه، زمانبندی کارها باید به طریقی انجام شود که مجموع زمان های آماده سازی یا معادل آن یعنی متوسط زمان آماده سازی، حداقل گردد.
هزینه های موجودی در حال ساخت[۶۰]: موجودی در حال ساخت سرمایه محسوب می شود و هزینه های حمل و نقل را افزایش می دهد. متوسط زمان بازده معیار عملکردی است که می تواند به عنوان شاخصی برای اندازه گیری موجودی در حال ساخت استفاده شود. زمان بازده مدت زمانی است که یک کار به خوداختصاص می دهد تا از سیستم خارج شود. حداقل کردن متوسط زمان بازده با فرض این که خروجی دارای سطح مشخصی می باشد میزان موجودی در حال ساخت را حداقل می سازد. حداقل کردن متوسط زمان بازده به حداقل کردن مجموع زمان های تکمیل، بسیار مرتبط است.
الگوریتم ژنتیک
در این قسمت از پایان نامه مفاهیم الگوریتم ژنتیک[۶۱] شرح داده شده است برای این منظور در ابتدا تکنیک‌های حل مسائل بهینه سازی مطرح شده و سپس ساختار و نحوه عملکرد الگوریتم ژنتیک به طور کامل بیان میشود . الگوریتم ژنتیک یکی از الگوریتم‌های تکاملی است که اولین بار توسط جان هالند[۶۲] در حوالی سال‌های ۱۹۶۵ تا ۱۹۷۵ ارائه شد و مبتنی بر نظریه تکاملی داروین است [۱۷]. الگوریتم ژنتیک در جمعیتی از راه حل‌های بالقوه، به جستجوی راه حل مناسب می‌‌گردد. در الگوریتم ژنتیک بسیاری از مفاهیمی که در زیست شناسی وجود دارد نظیر انتخاب بهتر، ترکیب ژنها، جهش ژنها و … شبیه سازی میشود [۱۱,۱۲].
تکنیک‌های حل مسائل بهینه سازی
فرایند بهتر نمودن هر چیز، بهینه‌سازی نامیده میشود. مساله زمانبندی سیستم باز در واقع نوعی مساله بهینه‌سازی است که به دلیل بزرگ بودن فضای جستجو امکان استفاده از روش‌های جستجوی کامل را ندارد. اعمال روش‌های جستجوی کامل برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارد. به همین دلیل تکنیک‌های جستجوی ابتکاری[۶۳] با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شده است. شکل ۲-۱۰ دسته بندی استراتژی‌های جستجو را نشان میدهد [۷۷،۸].
شکل ۲‑۱۰: دسته بندی استراتژی‌های جستجو
الگوریتم‌های تکاملی[۶۴] دستهای از الگوریتم‌های جستجو هستند که در هر تکرار، جمعیتی از جواب‌ها را مورد بررسی قرار داده و ذخیره می کنند. شکل ۲-۱۱ مراحل کلی الگوریتم‌های تکاملی را نشان میدهد. در میان الگوریتم‌های تکاملی، الگوریتم ژنتیک یکی از کاربردیترین روش‌های حل مسائل بهینه‌سازی است [۶۹،۷۴].
شکل ۲‑۱۱: مراحل کلی الگوریتم های تکاملی
صورت کلی الگوریتم ژنتیک
ویـژگی اساسی الگوریتم ژنتیک سـاده بودن آن است. در الگوریتم ژنتیک ابتدا بصورت تصادفی تعدادی از افراد به عنوان جمعیت[۶۵] اولیه ساخته میشود و میزان شایستگی هر یک از آنها بر اساس تابع شایستگی[۶۶] مشخص میشود سپس تعدادی از افراد بر اساس میزان شایستگی به عنوان والد انتخاب شده، فرزندان جدیدی به وجود می‌آید. فرزندان جدید در جمعیت کپی شده و جمعیت جدید به وجود می‌آید این کار تا بر آورده شدن شرط خاتمه ادامه می‌یابد [۱۹،۴۴]. مراحل کلی الگوریتم ژنتیک عبارتند از:
- مقداردهی اولیه: تولید افرادی برای جمعیت اولیه[۶۷]
- انتخاب والدین: انتحاب جفتهایی از والدین برای عملگر تبادل
- عملگر تبادل: تولید دو فرزند از هر زوج والد
- عملگر جهش: انجام عملگر جهش روی هر فرزند
- تعویض جمعیت: انتخاب فرزندها برای جمعیت نسل بعد
- اتمام الگوریتم: اگر تعداد تولید نسل‌ها کامل شده است، پایان، وگرنه برو به ۲.
تعاریف
در الگوریتم ژنتیک یک سری تعاریف وجود دارد که در زیر آمده است.
ژن[۶۸]: ژن ها خصوصیات هر فرد را کد می‌کنند. به عبارت دیگر به هر عضو کروموزوم ژن گفته میشود.
کروموزوم(فرد)[۶۹]: به گروهی از ژنها اطلاق میشود که اطلاعات وراثتی را از نسلی به نسل دیگر انتقال می‌دهند. راه حل هر مسئله به عنوان یک کروموزوم در نظر گرفته میشود.
جمعیت(نسل)[۷۰]: به مجموعه‌ای از کروموزوم‌ها جمعیت یا نسل گفته میشود.
نمایش کروموزوم
باید توجه داشت که نوع عملیات مورد نیاز در بسیاری از مراحل الگوریتم ژنتیک، به شدت وابسته به نوع ساختار انتخابی برای نمایش کروموزوم‌ها است. روش‌های بسیار زیادی وجود دارد که می تواند برای نمایش کروموزوم‌ها استفاده شود. در اینجا برخی روش‌های نمایش کروموزوم‌ها بررسی شده است.
نمایش باینری[۷۱]
متداول ترین نوع نمایش کروموزوم‌ها در الگوریتم ژنتیک، نمایش باینری است. در این روش برای نمایش کروموزوم‌ها از مقادیر گسسته برای هر ژن استفاده میشود. این روش علی رغم کاربرد زیاد دارای معایبی نیز است که منجر به گسترگی فضای پاسخ مساله میشود. از مزایای این روش سادگی عملگرهای ژنتیک است. این روش کدگذاری، برای مسائلی که در آنها تمامی حالات کروموزم نوعی پاسخ مساله به شمار می‌آید بسیار مناسب است. به عنوان مثال می توان به مساله کولهپشتی صفر و یک اشاره نمود.
نمایش جایگشتی[۷۲]
در این روش برای نمایش کروموزوم‌ها از اعداد برای هر ژن استفاده میشود و کروموزم ها به صورت آرایه از اعداد نمایش داده میشوند از مزایای این روش این است که روش جایگشتی در برخی مسائل به صورت بسیار مناسب توصیفی از پاسخ مساله را در خود دارد. مثال بسیار مناسب برای روش جایگشتی مساله فروشنده دورهگرد است. در این مساله هدف یافتن مسیری است که از هر شهر فقط و تنها فقط یک بار عبور نمایید به نحوی که کمترین مسافت ممکن طی شود. برای این مساله هر عدد بیانگر یک شهر و کروموزم بیان کننده ترتیب رفتن به شهرهای مختلف است. واضح است که استفاده از کدگذاری دودویی برای حل این مساله، علاوه بر بزرگ نمودن فضای پاسخ و پیچیده نمودن عملگرها، تشخیص پاسخ مساله از روی کروموزم را مشکلتر می کند، زیرا نیازمند تبدیل کدهای باینری به کد شهرها است.
نمایش مقداری[۷۳]
در این روش هر کروموزم به صورت آرایهای ساده از مقادیر است که این مقادیر می تواند هر چیز مرتبط با مساله باشد. مثلا اعداد اعشاری، کاراکتر و یا اشیاء کد شده، نمونه هایی از مقادیر مورد استفاده است.این روش در حل مسائل خاصی کاربرد دارد. مثلا برای پیدا کردن وزنهای شبکه های عصبی می‌توان از این روش استفاده نمود که مقادیر ژنهای کروموزم همان وزنهای شبکه است.
نمایش درختی[۷۴]
در این روش برای سازماندهی ژنها از ساختار درختی استفاده میشود. از این روش برای برنامه نویسی ژنتیک[۷۵] استفاده میشود. در روش نمایش درختی هر کروموزم به صورت درختی از اشیاء مثل توابع یا دستورات است. شکل۲-۱۲ نمایش کروموزوم به صورت درختی را نشان میدهد.
شکل ۲‑۱۲: نمایش کروموزوم به صورت درختی [۱]
تابع شایستگی
یکی از مهمترین ارکان الگوریتم ژنتیک، تابع شایستگی است. تابع شایستگی برای هر کروموزوم مقداری را به عنوان شایستگی مشخص کرده و به آن کروموزوم نسبت میدهد. که این مقدار میزان خوب بودن هر کروموزوم را نشان میدهد. به عبارت دیگر تابع شایستگی بر اساس پارامترهای مورد توجه برای حل یک مساله، کیفیت کروموزم را به صورت عددی مشخص می نماید. در مسائل بیشینه‌سازی این عدد، میزان مطلوبیت کروموزم را نشان میدهد. در این نوع مسائل هدف الگوریتم ژنتیک، ایجاد کروموزمی است که میزان شایستگی آن کروموزم بیشینه باشد و در مسائل کمینه‌سازی این عدد بیانگر میزان نامناسب بودن کروموزم است. در این مسائل الگوریتم ژنتیک به دنبال ایجاد کروموزمی با شایستگی کمینه است.
عملگر انتخاب[۷۶]
در این مرحله از الگوریتم ژنتیک، دو والد جهت جفتگیری و تولید کروموزم جدید انتخاب میشوند. طبق اصل بقای اصلح قضیه داروین، لازم است که افراد شایسته‌تر جمعیت در نسل‌های مختلف طبیعت بمانند بنابراین عملگر انتخاب باید به نحوی باشد که کروموزمهای برتر شانس بالاتری برای انتخاب شدن داشته باشند. در ادامه تعدادی از روش‌های انتخاب بررسی شده است.
انتخاب تصادفی
در این روش یک کروموزوم به صورت کاملا تصادفی انتخاب می شود. البته توابع مختلفی را می‌توان برای ایجاد عدد تصادفی پیشنهاد داد.
انتخاب چرخ گردان [۷۷]
انتخاب چرخ گردان اولین بار توسط هالند[۷۸] پیشنهاد شد. ایده اصلی این روش از بازی چرخ گردان گرفته شده است. بازی چرخ گردان بدین شکل است که یک دایره وجود دارد که به تعدادی قطاع تقسیم شده است و به هر فرد تعدادی قطاع (نه لزوما یکسان) داده می شود. چرخ گردان چرخانده میشود. پس از توقف چرخ، فردی که قطاع مقابل شاخص، متعلق به اوست برنده میشود. در پیادهسازی این بازی، محدوده بین صفر تا یک به بازههای نه لزوما هم اندازه تقسیم میشود و هر بازه به یک فرد اختصاص می‌یابد سپس یک عدد بین صفر تا یک انتخاب میشود. عدد مورد نظر در محدوده هر فرد قرار داشت آن فرد برنده است. این روش از تکنیک‌های متداول انتخاب بوده و جزو مجموعه روش‌های انتخاب تصادفی وزندار است. در روش‌های انتخاب تصادفی وزندار، احتمال تخصیص داده شده جهت انتخاب هر کروموزوم، متناسب با میزان شایستگی آن کروموزوم است. یعنی احتمال انتخاب متناظر با هر کروموزوم، بر اساس میزان شایستگی آن محاسبه میشود. اگر Fi مقدار برازندگی کروموزوم i ام باشد و n تعداد کروموزومهای جمعیت، احتمال انتخاب کروموزوم iام از معادله ۲-۱ محاسبه میشود.
معادله ۲‑۱: احتمال انتخاب کروموزوم در روش چرخ گردان [۱]
انتخاب به روش چرخ گردان در حالتی که میزان شایستگی کروموزوم‌ها خیلی با هم اختلاف داشته باشند کارایی ضعیفی خواهد داشت زیرا سبب می شود والدین انتخاب شده شبیه به هم باشند یعنی احتمال انتخاب کروموزوم‌هایی با شایستگی پایین، بسیار کاهش پیدا می‌کند. به عنوان مثال در جدول ۲-۴ برای ۵ کروموزوم با مقدار شایستگی مشخص شده احتمال انتخاب هر کروموزوم در روش چرخ گردان محاسبه شده است شکل ۲-۱۳ تفاوت احتمال انتخاب کروموزوم ها در روش چرخ گردان را به صورت درصدی نشان میدهد.
جدول ۲‑۴: احتمال انتخاب در روش چرخ گردان برای داده‌های فرضی [۱]
فرم در حال بارگذاری ...
