زمان تکمیل کارها
w j C j
مجموع وزنی زمان های جریان ساخت
w j T j
مجموع وزنی زمان های دیرکرد
w j T j
مجموع وزنی تعداد کارهای دارای دیرکرد
w j U j
در ادامه به برخی از مهم ترین معیارهای مورد بحث در مسائل زمانبندی، به طور خلاصه اشاره شده است.
معیار حداکثر زمان تکمیل کل کارها: حداکثر زمان تکمیل کل کارها توسط Cmax نشان داده میشود و به عنوان زمانی که آخرین کار سیستم را ترک می کند تعریف می شود. Cmax max(C1,C2 ,…,Cn ) که در آن Ci برابر زمان تکمیل کار i ام می باشد.
اهداف وابسته به موعد تحویل: یکی از مهم ترین این اهداف، در نظر گرفتن میزان دیرکرد کارهاست که سعی در حداقل کردن حداکثر تاخیر57 را دارد. تاخیر کار i به صورت Li Ci di تعریف می شود. بنابراین حداکثر تاخیر به صورت Lmax max(L1,L2 ,…,Ln ) بیان می شود. حداقل کردن حداکثر تاخیر به طور معناداری مرتبط با حداقل کردن بدترین عملکرد زمانبندی می باشد. هدف مهم دیگر، تعداد کارهای دارای دیرکرد58 است. تعداد کارهای دارای دیرکرد از جمله آماری است که دنبال کردن آن آسان می باشد. بنا براین مدیران اغلب از روی درصد تحویل های به موقع عملکرد تولید را مورد سنجش قرار می دهند. با این وجود، حداقل کردن این هدف می تواند منجر به ارائه زمانبندی شود که در آن برخی از کارها دارای میزان دیر کرد قابل توجهی می باشند، که اغلب در عمل غیر قابل قبول هستند. هدف وابسته به موعد تحویل که این نگرانی را برطرف می کند حداقل سازی کل دیرکرد59 می باشد. دیرکرد کار i به صورت T  max (0, C i d i ) تعریف می شود. هیچ یک از توابع هدف توضیح داده شده تکمیل زودتر از موقع کار را جریمه نمی کنند. در عمل، اگرچه معمولا تکمیل زودتر یک کار مطلوب نمی باشد زیرا منجر به هزینه انبار و هزینه های اضافی حمل و نقل می شود.
زمان تکمیل کارها: بازده یک کارگاه که برابر با نرخ خروجی می باشد معمولا توسط ماشین های گلوگاه تعیین می شود. به عبارت دیگر ماشینی که کمترین ظرفیت را در مقایسه با تقاضای ورودی به خود دارد، نرخ محصولات خروجی را تعیین می کند. در نتیجه، زمانبندی کارها باید به طریقی انجام شود که مجموع زمان های آماده سازی یا معادل آن یعنی متوسط زمان آماده سازی، حداقل گردد.
هزینه های موجودی در حال ساخت60: موجودی در حال ساخت سرمایه محسوب می شود و هزینه های حمل و نقل را افزایش می دهد. متوسط زمان بازده معیار عملکردی است که می تواند به عنوان شاخصی برای اندازه گیری موجودی در حال ساخت استفاده شود. زمان بازده مدت زمانی است که یک کار به خوداختصاص می دهد تا از سیستم خارج شود. حداقل کردن متوسط زمان بازده با فرض این که خروجی دارای سطح مشخصی می باشد میزان موجودی در حال ساخت را حداقل می سازد. حداقل کردن متوسط زمان بازده به حداقل کردن مجموع زمان های تکمیل، بسیار مرتبط است.
الگوریتم ژنتیک
در این قسمت از پایان نامه مفاهیم الگوریتم ژنتیک61 شرح داده شده است برای این منظور در ابتدا تکنیک‌های حل مسائل بهینه سازی مطرح شده و سپس ساختار و نحوه عملکرد الگوریتم ژنتیک به طور کامل بیان می‌شود . الگوریتم‌ ژنتیک یکی از الگوریتم‌های تکاملی است که اولین بار توسط جان هالند62 در حوالی سال‌های 1965 تا 1975 ارائه شد و مبتنی بر نظریه تکاملی داروین است [17]. الگوریتم ژنتیک در جمعیتی از راه حل‌های بالقوه، به جستجوی راه حل مناسب می‌‌گردد. در الگوریتم ژنتیک بسیاری از مفاهیمی که در زیست شناسی وجود دارد نظیر انتخاب بهتر، ترکیب ژن‌ها، جهش ژن‌ها و … شبیه سازی می‌شود [11,12].
تکنیک‌های حل مسائل بهینه سازی
فرآیند بهتر نمودن هر چیز، بهینه‌سازی نامیده می‌شود. مساله زمانبندی سیستم باز در واقع نوعی مساله بهینه‌سازی است که به دلیل بزرگ بودن فضای جستجو امکان استفاده از روش‌های جستجوی کامل را ندارد. اعمال روش‌های جستجوی کامل برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارد. به همین دلیل تکنیک‌های جستجوی ابتکاری63 با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شده است. شکل 2-10 دسته بندی استراتژی‌های جستجو را نشان می‌دهد [77،8].
الگوریتم‌های تکاملی64 دسته‏ای از الگوریتم‌های جستجو هستند که در هر تکرار، جمعیتی از جواب‌ها را مورد بررسی قرار داده و ذخیره می کنند. شکل 2-11 مراحل کلی الگوریتم‌های تکاملی را نشان می‌دهد. در میان الگوریتم‌های تکاملی، الگوریتم ژنتیک یکی از کاربردیترین روش‌های حل مسائل بهینه‌سازی است [69،74].
صورت کلی الگوریتم ژنتیک
ویـژگی اساسی الگوریتم ژنتیک سـاده بودن آن است. در الگوریتم ژنتیک ابتدا بصورت تصادفی تعدادی از افراد به عنوان جمعیت65 اولیه ساخته می‌شود و میزان شایستگی هر یک از آن‌ها بر اساس تابع شایستگی66 مشخص می‌شود سپس تعدادی از افراد بر اساس میزان شایستگی به عنوان والد انتخاب شده، فرزندان جدیدی به وجود می‌آید. فرزندان جدید در جمعیت کپی شده و جمعیت جدید به وجود می‌آید این کار تا بر آورده شدن شرط خاتمه ادامه می‌یابد [19،44]. مراحل کلی الگوریتم ژنتیک عبارتند از:
مقداردهی اولیه: تولید افرادی برای جمعیت اولیه67
انتخاب والدین: انتحاب جفتهایی از والدین برای عملگر تبادل
عملگر تبادل: تولید دو فرزند از هر زوج والد
عملگر جهش: انجام عملگر جهش روی هر فرزند
تعویض جمعیت: انتخاب فرزندها برای جمعیت نسل بعد
اتمام الگوریتم: اگر تعداد تولید نسل‌ها کامل شده است، پایان، وگرنه برو به 2.
تعاریف
در الگوریتم ژنتیک یک سری تعاریف وجود دارد که در زیر آمده است.
ژن68: ژن ها خصوصیات هر فرد را کد می‌کنند. به عبارت دیگر به هر عضو کروموزوم ژن گفته می‌‌شود.
کروموزوم(فرد)69: به گروهی از ژن‌ها اطلاق می‌شود که اطلاعات وراثتی را از نسلی به نسل دیگر انتقال می‌دهند. راه حل هر مسئله به عنوان یک کروموزوم در نظر گرفته می‌شود.
جمعیت(نسل)70: به مجموعه‌ای از کروموزوم‌ها جمعیت یا نسل گفته می‌شود.
نمایش کروموزوم
باید توجه داشت که نوع عملیات مورد نیاز در بسیاری از مراحل الگوریتم ژنتیک، به شدت وابسته به نوع ساختار انتخابی برای نمایش کروموزوم‌ها است. روش‌های بسیار زیادی وجود دارد که میتواند برای نمایش کروموزوم‌ها استفاده شود. در اینجا برخی روش‌های نمایش کروموزوم‌ها بررسی شده است.
نمایش باینری71
متداول ترین نوع نمایش کروموزوم‌ها در الگوریتم ژنتیک، نمایش باینری است. در این روش برای نمایش کروموزوم‌ها از مقادیر گسسته برای هر ژن استفاده می‌شود. این روش علی رغم کاربرد زیاد دارای معایبی نیز است که منجر به گسترگی فضای پاسخ مساله می‌شود. از مزایای این روش سادگی عملگرهای ژنتیک است. این روش کدگذاری، برای مسائلی که در آنها تمامی حالات کروموزم نوعی پاسخ مساله به شمار می‌آید بسیار مناسب است. به عنوان مثال می توان به مساله کولهپشتی صفر و یک اشاره نمود.
نمایش جایگشتی72
در این روش برای نمایش کروموزوم‌ها از اعداد برای هر ژن استفاده می‌شود و کروموزم ها به صورت آرایه از اعداد نمایش داده می‌شوند از مزایای این روش این است که روش جایگشتی در برخی مسائل به صورت بسیار مناسب توصیفی از پاسخ مساله را در خود دارد. مثال بسیار مناسب برای روش جایگشتی مساله فروشنده دورهگرد است. در این مساله هدف یافتن مسیری است که از هر شهر فقط و تنها فقط یک بار عبور نمایید به نحوی که کمترین مسافت ممکن طی شود. برای این مساله هر عدد بیانگر یک شهر و کروموزم بیان کننده ترتیب رفتن به شهرهای مختلف است. واضح است که استفاده از کدگذاری دودویی برای حل این مساله، علاوه بر بزرگ نمودن فضای پاسخ و پیچیده نمودن عملگرها، تشخیص پاسخ مساله از روی کروموزم را مشکلتر می کند، زیرا نیازمند تبدیل کدهای باینری به کد شهرها است.
نمایش مقداری73
در این روش هر کروموزم به صورت آرایهای ساده از مقادیر است که این مقادیر می تواند هر چیز مرتبط با مساله باشد. مثلا اعداد اعشاری، کاراکتر و یا اشیاء کد شده، نمونه هایی از مقادیر مورد استفاده است.این روش در حل مسائل خاصی کاربرد دارد. مثلا برای پیدا کردن وزنهای شبکههای عصبی می‌توان از این روش استفاده نمود که مقادیر ژنهای کروموزم همان وزنهای شبکه است.
نمایش درختی74
در این روش برای سازماندهی ژنها از ساختار درختی استفاده می‌شود. از این روش برای برنامه نویسی ژنتیک75 استفاده می‌شود. در روش نمایش درختی هر کروموزم به صورت درختی از اشیاء مثل توابع یا دستورات است. شکل2-12 نمایش کروموزوم به صورت درختی را نشان می‌دهد.
تابع شایستگی
یکی از مهمترین ارکان الگوریتم‌ ژنتیک، تابع شایستگی است. تابع شایستگی برای هر کروموزوم مقداری را به عنوان شایستگی مشخص کرده و به آن کروموزوم نسبت می‌دهد. که این مقدار میزان خوب بودن هر کروموزوم را نشان می‌دهد. به عبارت دیگر تابع شایستگی بر اساس پارامترهای مورد توجه برای حل یک مساله، کیفیت کروموزم را به صورت عددی مشخص می نماید. در مسائل بیشینه‌سازی این عدد، میزان مطلوبیت کروموزم را نشان می‌دهد. در این نوع مسائل هدف الگوریتم ژنتیک، ایجاد کروموزمی است که میزان شایستگی آن کروموزم بیشینه باشد و در مسائل کمینه‌سازی این عدد بیانگر میزان نامناسب بودن کروموزم است. در این مسائل الگوریتم ژنتیک به دنبال ایجاد کروموزمی با شایستگی کمینه است.
عملگر انتخاب76
در این مرحله از الگوریتم ژنتیک، دو والد جهت جفتگیری و تولید کروموزم جدید انتخاب میشوند. طبق اصل بقای اصلح قضیه داروین، لازم است که افراد شایسته‌تر جمعیت در نسل‌های مختلف طبیعت بمانند بنابراین عملگر انتخاب باید به نحوی باشد که کروموزمهای برتر شانس بالاتری برای انتخاب شدن داشته باشند. در ادامه تعدادی از روش‌های انتخاب بررسی شده است.
انتخاب تصادفی
در این روش یک کروموزوم به صورت کاملا تصادفی انتخاب میشود. البته توابع مختلفی را می‌توان برای ایجاد عدد تصادفی پیشنهاد داد.
انتخاب چرخ گردان 77
انتخاب چرخ گردان اولین بار توسط هالند78 پیشنهاد شد. ایده اصلی این روش از بازی چرخ گردان گرفته شده است. بازی چرخ گردان بدین شکل است که یک دایره وجود دارد که به تعدادی قطاع تقسیم شده است و به هر فرد تعدادی قطاع (نه لزوما یکسان) داده می شود. چرخ گردان چرخانده می‌شود. پس از توقف چرخ، فردی که قطاع مقابل شاخص، متعلق به اوست برنده می‌شود. در پیادهسازی این بازی، محدوده بین صفر تا یک به بازههای نه لزوما هم اندازه تقسیم می‌شود و هر بازه به یک فرد اختصاص می‌یابد سپس یک عدد بین صفر تا یک انتخاب می‌شود. عدد مورد نظر در محدوده هر فرد قرار داشت آن فرد برنده است. این روش از تکنیک‌های متداول انتخاب بوده و جزو مجموعه روش‌های انتخاب تصادفی وزندار است. در روش‌های انتخاب تصادفی وزندار، احتمال تخصیص داده شده جهت انتخاب هر کروموزوم، متناسب با میزان شایستگی آن کروموزوم است. یعنی احتمال انتخاب متناظر با هر کروموزوم، بر اساس میزان شایستگی آن محاسبه می‌شود. اگر Fi مقدار برازندگی کروموزوم i ام باشد و n‌ تعداد کروموزومهای جمعیت،‌ احتمال انتخاب کروموزوم iام از معادله 2-1 محاسبه می‌شود.
انتخاب به روش چرخ گردان در حالتی که میزان شایستگی کروموزوم‌ها خیلی با هم اختلاف داشته باشند کارایی ضعیفی خواهد داشت زیرا سبب می شود والدین انتخاب شده شبیه به هم باشند یعنی احتمال انتخاب کروموزوم‌هایی با شایستگی پایین، بسیار کاهش پیدا می‌کند.

این مطلب رو هم توصیه می کنم بخونین:   منابع پایان نامه درموردوظایف، زمانبندی، وظیفه
دسته‌ها: No category

دیدگاهتان را بنویسید