خرید و فروش ارز

1-4-1- زمانبندی در تولیدسفارشاتی که به جایگاه تولید رسیدهاند باید به کارهایی با موعد تحویل مربوطه تبدیل شوند. این کارها اغلب باید بر روی ماشینها در یک مرکز کاری در توالی و ترتیبی از پیش فرض شده پردازش شوند. پردازش کارها با تأخیر مواجه خواهد شد هنگامیکه ماشینهای خاصی مشغول به کار باشند. اگر کارهایی با اولویت بالا آماده پردازش در سیستم باشند و ماشین خاصی مشغول به کار باشد، با توجه به این نکته که کارها با اولویت بالا باید بلافاصله پردازش شوند، بریدگی در سیستم رخ خواهد داد. رویدادهای غیر قابل پیشبینی در کارگاه مانند خرابی ماشین و زمانهای بیش از انتظار طولانی شده نیز باید مورد توجه قرار گیرند به این سبب که میتوانند تأثیر بسزایی بر روی زمانبندی داشته باشند. ایجاد زمانبندی دقیق کارهایی که قرار است پردازش شوند منجر به حفظ کارایی و کنترل عملیات میشود.
کارگاه تنها قسمت تأثیرگذار بر روی فرآیند زمانبندی نمیباشد. در واقع، فرآیند زمانبندی تحت تأثیر فرآیند برنامهریزی تولید قرار دارد که برنامهریزی میان مدت تا بلند مدت را برای کل سازمان بر عهده دارد. هدف فرآیند برنامهریزی تولید، بهینه کردن ترکیب محصول کلی شرکت، تخصیص بلند مدت منابع بر اساس سطوح موجودی و پیشبینی تقاضا و نیازمندیهای منابع است. تصمیمات گرفته شده در سطوح بالای برنامهریزی به طور مستقیم بر فرآیند زمانبندی مؤثر میباشد.
در تولید، واحد زمانبندی باید با دیگر واحدهای تصمیمگیری در سازمان تعامل داشته باشد .یکی از سیستمهای شناخته شده که بسیار مورد استفاده است، سیستم برنامهریزی نیازمندیهای مواد (MRP) میباشد. بعد از مشخص شدن زمانبندی، تمام مواد خام و منابع باید در زمانهای مشخصی قابل دسترس باشند. زمان در دسترس بودن کارها باید به طور پیوسته توسط برنامهریزی تولید، سیستم زمانبندی و سیستم برنامهریزی نیازمندیهای مواد مشخص شود.
سیستم برنامهریزی نیازمندیهای مواد به طور طبیعی نسبتاً پیچیده میباشد. برای انجام هر کار لیستی از قطعات مورد نیاز (BOM) مشخص میشود. سیستم برنامهریزی نیازمندیهای مواد موجودی هر قطعه را کنترل میکند. علاوه بر این سیستم، زمان خرید هر قطعه را مشخص میسازد. بدین منظور سیستم برنامهریزی نیازمندیهای مواد از روشهایی همچون اندازه انباشته و زمانبندی انباشته استفاده میکند که مشابه روشهای مورد استفاده در زمانبندی میباشند.
بستههای تجاری MRP بسیار در دسترس هستند. بنابراین بسیاری از سازمانهای تولیدی از این سیستم استفاده میکنند. اگر سیستم زمانبندی در سازمان تولیدی وجود نداشته باشد، سیستم برنامهریزی نیازمندیهای مواد ممکن است برای اهداف برنامهریزی تولید مورد استفاده قرار گیرد. با این وجود در سطوح پیشرفته MRP برای انجام زمانبندی دقیق با مشکلاتی مواجه میشود.
سازمانهای پیشرفته معمولاً از سیستمهای اطلاعاتی پیشرفته که شامل یک کامپیوتر مرکزی و پایگاه داده میباشد، استفاده میکنند. شبکههای محلی کامپیوترهای شخصی، ایستگاههای کاری و ترمینالهای ورودی داده به کامپیوتر مرکزی متصل شدهاند که میتوانند برای بازیابی اطلاعات یا برای ورود دادههای جدید مورد استفاده قرار گیرند. ترمینالها در مکانهای مهم به کامپیوتر زمانبندی متصل میشوند و بدین وسیله امکان دسترسی دپارتمانها را به اطلاعات زمانبندی جاری فراهم میکند. در نتیجه، این دپارتمانها سیستم زمانبندی را با اطلاعات مناسب مانند تغییرات در وضعیت ماشین و کار تجهیز میکنند.
1-4-2- زمانبندی در خدماتتعریف سیستم زمانبندی خدماتی به معنای عام کار مشکلی است. واحد زمانبندی در یک سازمان خدماتی با مشکلات متنوعی مانند تخصیص منابع (کامیونها، اتاقهای جلسه یا دیگر تجهیزات) یا زمانبندی نیروی کار (تخصیص نوبت کاری) مواجه میشود. الگوریتمهای مورد استفاده در محیطهای خدماتی کاملاً متفاوت با الگوریتمهای مورد استفاده در محیطهای تولیدی میباشند. در حالیکه زمانبندی در هر دو محیط باید با دیگر واحدهای تصمیمگیری هماهنگ باشد. این هماهنگی معمولاً در داخل سیستمهای اطلاعاتی پیچیده و مفصل حاصل میشود. سیستم اطلاعاتی در محیط خدماتی معمولاً متکی بر پایگاه داده وسیعی است که شامل اطلاعات مرتبط با در دسترس بودن منابع و مشتریان بالقوه میباشد. در چنین محیطی، سیستم زمانبندی با ماژولهای پیشبینی و مدیریت تعامل دارد.
1-5- مروری بر مدلهاسیستمهای تولیدی و خدماتی با معیارهای بسیاری مانند تعداد ماشینها، سطح اتوماسیون، ویژگیهای مربوط به ساختار مورد نظر، نوع سیستم حمل و نقل و غیره مشخص شدهاند. تفاوت در همه این معیارها تعداد بسیار زیادی از مدلهای زمانبندی را سبب میشود.

مدلهای زمانبندی معمولا از طریق ترکیب ماشینها، محدودیتها و توابع هدف مشخص میشوند.
دو راه برای مشخص نمودن یک برنامه زمانبندی وجود دارد. راه ابتدایی توسط کنوی ارائه شد و روش دوم که بیشتر مورد استفاده است، توسط گراهام و همکارانش در سال 1979 توسعه داده شده است که با سه تایی مرتب α|β|γ توصیف میگردد.
محیط ماشین (α)محیط ماشین و تعریفی که از نظم و سازماندهی ماشینها در نظر داریم را نشان میدهد. پنج محیط متعارف ماشین، به شرح زیر است.
تک ماشین: در این محیط فقط یک ماشین برای زمانبندی کارهای داده شده تحت محدودیتهای مشخص شده، وجود دارد که در واقع سادهترین محیط ممکن است. سیستمهای تولیدی بسیاری به سیستمهای تولیدی تک ماشین منجر میشوند. برای مثال، اگر در محیطی که شامل چندین ماشین میباشد گلوگاهی رخ دهد، آنگاه توالی کارها در گلوگاه به طور کلی بیان کننده عملکرد کل سیستم خواهد بود. در این حالت تمامی عملیات پس از زمانبندی گلوگاه زمانبندی خواهند شد. چنین رویکردی دلالت بر در نظر گرفتن مسأله اصلی به صورت مسأله تک ماشین دارد. مدلهای تک ماشین همچنین در رویکردهای تجزیه کاربرد دارند. در چنین سیستمی، مسائل زمانبندی در محیطهای پیچیده به چندین مسأله زمانبندی تک ماشین تبدیل میشوند. مدلهای تک ماشین با محدودیتها و توابع هدف مختلفی در نظر گرفته شدهاند. نتایج به دست آمده منجر به ایجاد مجموعهای از قواعد گردیده است که نتیجه آنها ایجاد جواب بهینه در محیطهای تک ماشین میباشد. برای مثال، قانون زودترین موعد تحویل (EDD) که کارها را به ترتیب صعودی موعد تحویل زمانبندی میکند، منجر به حداقل شدن حداکثر دیرکرد در میان تمام کارها میشود. قانون کمترین زمان پردازش (SPT) که کارها را به ترتیب صعودی زمان پردازش زمانبندی میکند منجر به حداقل شدن تعداد کارهای منتظر برای پردازش میشود.
مدلهای ماشینهای موازی: ماشینهای موازی تعمیمی از مدل تک ماشین میباشد. بسیاری از محیطهای تولیدی از چندین مرحله یا مرکز کاری تشکیل شدهاند در حالیکه هر یک از آنها دارای چندین ماشین به صورت موازی میباشند. ماشینهای موجود در یک مرکز کاری میتوانند یکسان باشند. در این حالت هر زمانی که کار وارد سیستم شود امکان پردازش آن بر روی هر یک از ماشینهای در دسترس فراهم خواهد بود. همچنین، مدلهای ماشینهای موازی مانند مدلهای تک ماشین از این جهت دارای اهمیت میباشند که اگر در سیستمهای تولید چند مرحلهای یک مرکز کاری خاص به صورت گلوگاه عمل کند، آنگاه زمانبندی در مرکز کاری مورد نظر تعیین کننده عملکرد کل سیستم خواهد بود. در این صورت گلوگاه میتواند به صورت مجموعهای از ماشینهای موازی مدل شود و به تنهایی مورد تحلیل قرار گیرد. در بعضی از موارد ماشینهای موازی ممکن است یکسان نباشند. در واقع در این حالت برخی از ماشینها قدیمیتر از بقیه هستند و با سرعت پایینتری عمل میکنند یا ممکن است ماشینی بهتر نگهداری شده باشد و بتواند کار را با کیفیت بالاتری انجام دهد. در این صورت برخی از کارها ممکن است بر روی هر یک از m ماشین موازی پردازش شوند در حالیکه بقیه ممکن است تنها بر روی مجموعه خاصی از m ماشین پردازش شوند. زمانی که ماشینها انسان باشند، آنگاه زمان پردازش یک عملیات به نوع کار و به اپراتور نیز بستگی خواهد داشت. اپراتوری ممکن است در کار خاصی مهارت داشته باشد در حالیکه اپراتور دیگری ممکن است کار دیگری را به خوبی انجام دهد.
جریان کارگاهی (Fm): در بسیاری از محیطهای تولیدی یا مونتاژ، کارها دارای چندین عملیات میباشند که معمولاً باید بر روی چندین ماشین مختلف پردازش شود. اگر مسیر همه کارها یکسان باشد، یعنی همه کارها ماشینهای یکسانی را در ترتیب یکسانی بازدید کنند چنین محیطی به عنوان محیط جریان کارگاهی در نظر گرفته میشود. در واقع ماشینها در چنین محیطی به صورت سری چیده میشوند و هنگامیکه کاری زمان پردازشش بر روی ماشین خاصی تکمیل میشود، وارد صف ماشین بعدی میشود. ترتیب کارها از ماشینی به ماشین دیگر ممکن است متفاوت باشد به ا ین سبب که کارها ما بین ماشینها ممکن است دوباره مرتب شوند. با این وجود، اگر سیستم حمل و نقل مواد، کارها را از یک ماشین به ماشین بعدی منتقل کند، در این صورت توالی یکسانی از کارها در کل سیستم برقرار خواهد بود. در برخی از سیستمهای جریان کارگاهی، هنگامیکه کاری به پردازش بر روی ماشین خاصی نیاز نداشته باشد، کار از ماشین مورد نظر میگذرد و جلوتر از کارهایی که پردازش شدهاند یا منتظر پردازش در آن مرحله هستند، قرار میگیرد. تعمیمی از مدل جریان کارگاهی، مدل جریان کارگاهی انعطاف پذیر میباشد که از چندین مرحله به صورت سری تشکیل شده است که در هر مرحله دارای تعدادی ماشین به صورت موازی وجود دارند. کارها در هر مرحله بر روی یکی از ماشینهای موازی پردازش میشوند. ظرفیت انبار بین ماشینهای متوالی ممکن است برای اهداف عملی نامحدود باشد، که این موضوع اغلب برای محصولاتی که از نظر فیزیکی کوچک هستند صادق است، بنابراین انبار نمودن مقادیر زیادی از این محصولات بین دو ماشین امری ممکن میباشد.
کار کارگاهی (Jm): این حالت، مانند حالت قبل است با این تفاوت که نیازی به وجود مسیر یکسانی برای همه کارها نیست. به عبارت دیگر هر کار دارای مسیر مخصوصی بین ماشینها است. به این محیط در نظریه زمانبندی بیشترین توجه شده است و بیشترین پیشرفتها در این محیط صورت گرفته است. در کارگاههای چند عملیاتی، کارها اغلب دارای مسیرهای مختلفی هستند. در حقیقت مدل جریان کارگاهی مدل کار کارگاهی است که در آن هر کار مسیر یکسانی دارد. سادهترین مدل کار کارگاهی فرض میکند که هر کار حداکثر یکبار بر روی ماشین خاص پردازش میشود. در حالیکه در مدلهایی ممکن است که یک کار چند بار در مسیرش در طول سیستم بر روی ماشینی خاص پردازش شود. چنین محیطهایی مقدس به گردش کاری مجدد هستند که به طور قابل ملاحظهای پیچیدگی مدل را افزایش میدهد. تعمیمی از مدل کار کارگاهی، مدل کار کارگاهی انعطاف پذیر است که دارای چندین ماشین به صورت موازی میباشد. اگر در این مسائل یک کار روی ماشین خاصی بیش از یکبار برود، آن کار را دارای جریان مجدد میگویند و این حالت یک پدیده کاملا عمومی در دنیای واقعی است. به عنوان مثال، در تولید نیمه رسانا، کارها در اکثر اوقات دارای جریان مجدد است.
کارگاه باز (Om): در این محیط هیچگونه محدودیتی از نظر مسیر کارها در بین ماشینها وجود ندارد، به این معنی که کارهای یکسان ممکن است دارای مسیرهای متفاوتی باشند. در این محیط m ماشین وجود دارد و هریک از کارها میتواند روی هریک از m ماشین مجدداً فرایند شود، علاوه بر این ممکن است بعضی از زمان فرایندها صفر باشد. در مدل زمانبندی فوق، انعطاف زیادی جهت زمانبندی و تعیین توالی عملیات بهینه وجود دارد، ولی بدست آوردن توالی بهینه در این مدل دشوار است. هدف در مدل مذکور معمولاً حداقل کردن کل زمان تمکیل میباشد.
کارگاه مرکب (X): در این محیط، یک زیر مجموعهای از کارها وجود دارد که برای آن مسیر فرآیند ثابتی مشخص شده است و همزمان، بقیه کارها برای کمینه کردن تابع هدف برنامهریزی میشوند.
1-6 - فرضیات عمومی و ارائه یک مدل کلیمسأله مورد بررسی در این تحقیق، مسأله زمانبندی ماشینهای موازی چندهدفه میباشد. یک مسأله زمانبندی شامل تعدادی کار میباشد که هر کدام زمان پردازش خاصی دارند.
فرضیات عمومی برای مسائل زمانبندی ماشینهای موازی یکنواخت به شرح زیر است:
در هر زمان فقط یک کار بر روی یک ماشین پردازش میشود.
همه کارها باید بهطور کامل پردازش شوند.
m ماشین موازی یکنواخت با سرعتهای مختلف در زمان صفر در دسترس میباشند.
هیچ ماشینی نمیتواند در یک زمان بیش از یک کار را پردازش کند.
پارامترهای مسأله از جمله زمان پردازش و موعد تحویل کارها در ابتدای کار معین بوده و ثابت میباشند.
ماشینها ممکن است زمان بیکاری داشته باشند.
زمان آمادهسازی ماشینها به صورت وابسته به توالی در نظر گرفته شده است.
کارها در طول افق برنامهریزی به مرور زمان (بهصورت پویا) وارد میشوند.
اندیسها و پارامترها ی مدل به شرح زیر است:
j: اندیس کار (j=1,2,…,n)
m: اندیس ماشین (m=1,2,…,m)
Cj: زمان تکمیل کار j
Wj: وزن مربوط به کار jام
Tj: مقدار دیرکرد کار jام
βj: جریمه دیرکرد کار jام
Ej: مقدار زودکرد کار jام
αj: جریمه زودکرد کار jام
dj: موعد تحویل کار jام
بهطور کلی میتوان مدل زیر را برای مسأله ماشینهای موازی با اهداف کمینهکردن میانگین وزنی زمان تکمیل کارها و مجموع جریمههای دیرکرد و زودکرد استفاده کرد:
Min 1wj=1nwjcj ,
Min j∈JαjEj+βjTj ,
s.t.
constraints

محدودیتهای مسأله در فصل سوم به تفصیل شرح داده خواهد شد.
1-7- ضرورت انجام تحقیقبا توجه به اهمیت روز افزون مسائل ماشینهای موازی، در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم میباشد. امروزه در اغلب کارخانجات تولیدی و تولیدی، تامین به موقع سفارش مشتری یا خدمترسانی بهموقع، حائز اهمیت است. هزینههای زودکرد و دیرکرد در این مورد نه تنها مشتری را متضرر میگرداند، بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از دست میدهد. حداقل کردن زمان تکمیل و جریمههای حاصل از دیرکرد سبب حداکثر شدن بهرهوری و کارایی سیستم تولیدی یا خدماتی میشود. همچنین حداقل کردن جریمههای زودکرد، باعث حداقل شدن هزینههایی از قبیل هزینه موجودی خواهد شد. لذا در این پایاننامه، مسأله زمانبندی ماشینهای موازی با استفاده از روش بهینهسازی چندمعیاره حل گردیده است.
در بسیاری از مسائل زمانبندی فرض میشود که همه کارها به طور همزمان برای اجرا در دسترس باشند. اما در موارد متعددی ممکن است ورود کارها غیرهمزمان باشد. در حالتیکه با زمانهای دسترسی مختلف سر و کار داریم، مجموعه کارهایی که باید زمانبندی شود با گذشت زمان تغییر میکند که باعث تبدیل شدن محیط زمانبندی به یک محیط پویا میشود. در این پایاننامه، زمانهای دسترسی کارها بهصورت پویا در نظر گرفته شده است و کارها به مرور زمان وارد سیستم میشوند. همچنین در مسأله فوق، به دلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی به توالی لحاظ شده است و سپس یک مدل ترکیبی بهینهسازی برای حل این مسأله ایجاد شده است.
1-8- هدف از تحقیقبا توجه به اهمیت سیستمهای تولید به موقع و نقش آن در شرکتهای تولید و خدماتی، توجه به دو معیار زودکرد و دیرکرد با در نظر گرفتن هزینههایی که به دنبال آن منجر میشود، ضروری به نظر میرسد. از طرفی در سیستمهای تولیدی امروزی، همواره بالا بردن بهرهوری و کارایی سیستم، بسیار مورد توجه مدیران سیستمها و محققان بوده است. به همین دلیل در مسائل زمانبندی، معیار زمان تکیمل کارها، از اهمیت بالایی برخوردار است چون حداقل شدن این معیار سبب بالا رفتن بهرهوری سیستم خواهد شد. در سیستمهای تولیدی واقعی، کارها دارای مشخصه اولویت برای تکمیل و آماده شدن میباشند. بنابراین بررسی معیار میانگین وزنی زمان تکمیل کارها بسیار موثر میباشد.
در این تحقیق، مسأله زمانبندی ماشینهای موازی با هدف تعیین توالی تولید بهینه با توجه به معیارهای میانگین وزنی زمان تکمیل و مجموع هزینههای زودکرد و دیرکرد مطرح شده است. به دلیل اهمیت زمان آمادهسازی در بسیاری از سیستمهای تولیدی امروزی، محدودیت زمان آمادهسازی وابسته به توالی نیز برای کارها در نظر گرفته شده است. همچنین برای نزدیکتر شدن به محیط تولید در دنیای واقعی، زمانهای دسترسی کارها بهصورت پویا در نظر گرفته شده است.
از آنجا که مسألهی مورد بررسی جز مسائل پیچیدهی ترکیباتی و از کلاس NP-Hardمیباشد، کارایی روش حل دقیق برای اندازههای بزرگ مسأله کاهش مییابد. بنابراین با استفاده از الگوریتم تکامل دیفرانسیلی (DE) به ارایه جواب برای مسائل با اندازههای بزرگ میپردازیم.
با توجه به مرور ادبیات انجام شده در حیطه مسائل زمانبندی ماشینهای موازی یکنواخت با درنظر گرفتن زمانهای آمادهسازی وابسته به توالی و زمانهای دسترسی پویا بهطور همزمان، میتوان به این نتیجه رسید که در این محیط، هیچ تحقیقی وجود ندارد که توابع مسأله را بهصورت چندهدفه درنظر گرفته باشد و روش حل آن الگوریتم فراابتکاری باشد. در نتیجه نوآوری این تحقیق، مدل درنظر گرفته شده و روش حل آن، الگوریتم فراابتکاری تکامل دیفرانسیلی میباشد.
1-9- جمعبندیدر این فصل، به معرفی کار و نظریه زمانبندی و نحوه تعامل آن با برنامهریزی پرداختیم. با توجه به این که مدلهای زمانبندی معمولاً براساس ترکیب ماشینها، نوع محدودیتها و معیارهای در نظر گرفته شده مشخص میشوند، انواع متداولی از موارد بالا مورد بررسی قرار گرفت. ضرورت انجام این پژوهش و هدف از انجام آن نیز بیان گردید. ساختار ادامهی این پژوهش بدین شکل میباشد. در فصل دو، ادبیات موضوع و پیشینهی تحقیق، مورد مطالعه قرار گرفته است. در بخش سه، مدل ریاضی ارائه شده برای مسأله معرفی و پارمترهای مسأله شرح داده شده است. در فصل چهار الگوریتم تکامل دیفرانسیلی توسعه داده شده برای این مسأله و الگوریتم NSGA-II معرفی میشود. نتایج عددی حل مسایل و مقایسه عملکرد دو روش DEو NSGA-II نیز در انتهای این بخش آورده شده است. در بخش پایانی، جمعبندی و پیشنهادها برای کار آیندگان آورده شده است. همچنین در پیوست پژوهش، کد مدل ریاضی ارایه شده در محیط نرمافزار GAMS و کد الگوریتمهای فررابتکاری در محیط Matlab آورده شده است.
فصل دوم ادبیات و پیشینه تحقیق
2-1- مقدمهبا توجه به اینکه در این پایاننامه برآنیم تا مسأله ماشینهای موازی را با در نظر گرفتن شرایط محیط پویا و زمانهای آمادهسازی وابسته به توالی، مورد بررسی قرار دهیم، در ادامه مروری بر ادبیات موضوع مطرح در زمینههایی که در این پژوهش بهطور مستقیم یا غیر مستقیم مورد توجه قرار گرفتهاند، خواهیم پرداخت. در ابتدا مسأله ماشینهای موازی را در سه بخش محدودیتها، توابع هدف و روش حل مورد بررسی قرار میدهیم. سپس، مسائل چندهدفه با تمرکز بر روی الگوریتم تکاملی DE و NSGA-II مورد بررسی قرار میگیرد.
2-2- مروری بر محدودیتها در محیط ماشینهای موازی ADDIN EN.CITE <EndNote><Cite ExcludeAuth="1" ExcludeYear="1" Hidden="1"><Author>Muramatsu</Author><Year>1985</Year><RecNum>2</RecNum><record><rec-number>2</rec-number><foreign-keys><key app="EN" db-id="2tv22aafbexfe3efz9m5vff4ts0sr2zv5asw">2</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Muramatsu, Rtntaro</author><author>Ishii, Kazuyoshi</author><author>Takahashi, Katsuhtko</author></authors></contributors><titles><title>Some ways to increase flexibility in manufacturing sys--s</title><secondary-title>International Journal of Production Research</secondary-title></titles><periodical><full-title>International Journal of Production Research</full-title></periodical><pages>691-703</pages><volume>23</volume><number>4</number><dates><year>1985</year><pub-dates><date>1985/01/01</date></pub-dates></dates><publisher>Taylor &amp; Francis</publisher><isbn>0020-7543</isbn><urls><related-urls><url>http://www.tandfonline.com/doi/abs/10.1080/00207548508904738</url></related-urls></urls><electronic-resource-num>10.1080/00207548508904738</electronic-resource-num><access-date>2012/08/09</access-date></record></Cite></EndNote>در صنایع، یک عملیات گلوگاهی معمولاً بر روی ماشینهای موازی پردازش میشود [5]. با در نظر گرفتن این موضوع که با افزایش تعداد مناسب ماشینها، انعطافپذیری یک سیستم تولیدی میتواند افزایش پیدا کند [6]، ماشینهای موازی در بسیاری از سیستمهای تولیدی قابل استفاده و کاربردی میشود. هرچند مسائل زمانبندی ماشینهای موازی (PMSP)، از جمله دسته مسائل سخت و مشکل زمانبندی است، به دلیل اینکه اکثر مسائل PMSP، NP-Hard هستند [7].
مسائل PMSP را در حال حاضر میتوان به سه دسته ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط تقسیمبندی کرد مرور ادبیات کامل و دقیقتر را میتوانید در مقاله گراهام و همکاران [8] پیدا کنید. از آنجایی که مشکل اصلی به دست آوردن جواب بهینه (و نزدیک بهینه) ریشه در وجود زمانهای آمادهسازی وابسته به توالی بین کارها دارد [9]، در اکثر الگوریتمهایی که برای مسأله PMSP وجود دارد، محدودیت SDST و زمانهای دسترسی کارها به صورت پویا در نظر گرفته نشده است [10].
در زیر به بررسی و مروری بر ادبیات دو محدودیت زمانهای آمادهسازی وابسته به توالی و محیط پویا در محیط ماشینهای موازی که در این پایاننامه در نظر گرفته شده است، پرداخته میشود.
2-2-1- زمانهای آمادهسازی وابسته به توالیدر برنامهریزی سیستمهای تولیدی، به طور کلی زمان آمادهسازی شامل کار جهت آماده کردن ماشین و یا تعیین موقعیت کارها در مرحله پردازش مواد اولیه میباشد. مسائل تولیدی که بهطور صریح ملاحظات زمانبندی را در نظر میگیرند به دو گروه عمده تقسیمبندی میشوند: در گروه اول زمانها و یا هزینههای آمادهسازی تنها وابسته به کاری هستند که قرار است بر روی ماشین پردازش شود. چنین مسائلی با عنوان زمانهای آمادهسازی مستقل از توالی در ادبیات موضوع شناخته میشوند. در گروه دوم زمانها یا هزینههای آمادهسازی نه تنها وابسته به کاری هستند که قرار است پردازش شود، بلکه وابسته به کاری که پردازش آن اخیراً تمام شده است نیز هستند. چنین مسائلی با عنوان زمانهای آمادهسازی وابسته به توالی شناخته میشوند.
مسائل زمانبندی که نیازمند در نظر گرفتن زمانهای آمادهسازی به طور واضح میباشند در بسیاری از محیطهای کارگاهی یافت میشوند. بررسی کاملی بر روی زمانبندیها شامل زمان آمادهسازی توسط اللهوردی و همکاران [11] انجام شده است. اواکیک و اوزسی [12] مسأله زمانبندی پویای ماشینهای موازی را با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی در نظر گرفتند. مجموعهای از الگوریتمهای افق غلتان برای انتخاب جواب بهینه توسط آنها پیشنهاد شده است. روچا و همکاران [13] مسأله زمانبندی ماشینهای موازی نامرتبط را با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و ماشین مورد بررسی قرار دادند. این مسأله در ادبیات مسائل زمانبندی به صورت R | Sijm |Cmax +ΣwiTi نشان داده میشود. آنها دو مدل مجزای برنامهریزی آمیخته عدد صحیح پیشنهاد کردند. مدل اول بر اساس مدل من در محیط کار کارگاهی و مدل دوم بر اساس مدل وگنر در محیط کار کارگاهی توسعه یافته است. متغیر تصمیم بر اساس زمان آغاز پردازش کار تعریف شده است. علاوه بر این، الگوریتم شاخه و کران برای یافتن جواب بهینه ارائه شده است. الگوریتم شاخه و کران دارای سه جز اصلی میباشد: یافتن جواب اولیه به عنوان حد بالا، توسعه دادن قواعدی بر مبنای خواص مسأله و طراحی رویکردی به منظور محاسبه حد پایین. الگوریتم شاخه و کران ارائه شده توسط روچا و همکاران دارای دو بخش طراحی رویکردهایی برای محاسبه حد پایین و بالا میباشد. در الگوریتم ارائه شده جواب حاصله از روش ابتکاری GRASP به عنوان حد بالا مورد استفاده قرار گرفته است. الگوریتم در دو فاز طراحی شده است. در فاز اول، کارها به ماشینها تخصیص یافتهاند، اما هیچ توالی مشخص نشده است. توالی کارها بر روی ماشینها در فاز دوم مشخص شده است. برای توابع هدف حداکثر زمان تکمیل کارها و کل دیرکرد وزنی، حد پایینهای جداگانه ارائه گردیده است. در پایان عملکرد الگوریتم شاخه و کران با دو رویکرد مدل برنامهریزی آمیخته عدد صحیح مقایسه شده است.
توکلی مقدم و مهدیزاده [14] یک مدل برنامهریزی مختلط عدد صحیح خطی جدیدی را برای مسأله زمانبندی ماشینهای موازی یکسان با در نظر گرفتن زمانهای آمادهسازی خانواده کارها بهمنظور حداقل نمودن کل زمان جریان ساخت پیشنهاد کردند. برای حل مسأله مورد نظر، یک الگوریتم فراابتکاری بر اساس الگوریتم ژنتیک برای دستیابی به جواب مناسب و نزدیک بهینه، مخصوصاً برای مسائل با اندازه بزرگ، پیشنهاد شده است.
در بعضی از مقالات زمانهای آمادهسازی به صورت وابسته به توالی کارها و توالی ماشینها بررسی شده است. والادا و رویز [15] یک الگوریتم ژنتیک برای مسأله زمانبندی ماشینهای موازی نامرتبط که در آن زمان آمادهسازی وابسته به توالی کارها و ماشینها میباشد، ارائه شده است. الگوریتم ژنتیک ارائه شده شامل یک جستجوی محلی سریع میباشد. فلشزار و همکاران [16] مسأله NP-Hard زمانبندی کارها بر روی ماشینهای موازی نامرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی کارها و ماشینها بررسی شده است. در این مقاله، هدف کمینه کردن زمان تکمیل کارها میباشد. برای حل این مسأله از الگوریتم جستجوی همسایگی متغیر استفاده شده است.
2-2-2- محیط پویادر محیط واقعی معمولاً شرایط پویا حاکم میباشد؛ بدین معنی که تمام کارها به طور همزمان در زمان صفر در دسترس نمیباشند. بیلج و همکاران [17]، مسأله زمانبندی ماشینهای یکسان را که در آن کارها در زمانهای متفاوتی در طول افق برنامهریزی در دسترس هستند مورد بررسی قرار گرفته است. حداقل کردن کل دیرکرد به عنوان تابع هدف در نظر گرفته شده است. سوبور و لاجندران [18] مسأله زمانبندی ماشینهای موازی نامرتبط را مورد توجه قرار دادند. در مسأله در نظر گرفته شده، کارها دارای زمانهای در دسترس بودن متفاوت و ماشینها دارای زمانهای آماده به کار بودن متفاوت میباشند. در مسأله مذکور، تمهیداتی برای مجموعهای از کارها در نظر گرفته شده است؛ بر این اساس کارها به دلیل داشتن اولویت بالا، موعد تحویل تنگ یا میزان بار کاری بالا، میتوانند شکسته شوند و بر روی چندین ماشین به صورت موازی پردازش شوند. در مطالعه انجام شده، زمانهای آمادهسازی به صورت مستقل از توالی در نظر گرفته شده بودند که در آن زمان آمادهسازی کار بر روی ماشین با زمان پردازش کار بر روی همان ماشین موردنظر جمع شده است و حاصل جمع به صورت زمان پردازش کار بر روی ماشین در نظر گرفته شده است. لاجندران و همکاران [19] مسأله ماشینهای موازی نامرتبط را با فرضهای زمانهای متفاوت برای در دسترس بودن کارها و آماده به کار بودن ماشینها مورد مطالعه قرار دادند. زمان آمادهسازی موردنیاز یک کار بر روی ماشین وابسته به میزان شباهت یا تفاوت موجود میان کار مورد نظر و کار بلافاصله قبل از آن بود. هدف از زمانبندی حداقل کردن کل دیرکرد وزنی کارهایی بود که در طول افق برنامهریزی در دسترس هستند. برای افزایش دادن سودمندی و کارایی الگوریتم جستجو پیشنهاد شده، چهار جواب اولیه متفاوت توسعه یافته است که بر اساس مکانیسمهای مبتنی بر قواعد موجود (دیسپچینگ) در ادبیات موضوع میباشند. با انجام دادن آنالیزهای آماری بسیار، الگوریتم مناسب برای مسائل با اندازه کوچک، اندازه متوسط و اندازه بزرگ مشخص شده است.
توکلی مقدم و همکاران [20] یک مدل ریاضی چندهدفه جدید برای مسأله زمانبندی ماشینهای موازی پیشنهاد کردند به نحوی که تعداد کارهای دارای دیرکرد و مجموع مدت زمان تکمیل کارها کمینه گردد. در این مدل ماشینهای نامرتبط دارای سرعتهای متفاوت در نظر گرفته شدهاند. همچنین کارها در لحظه شروع زمانبندی، از لحاظ زمانهای دسترسی و موعد تحویل دارای شرایط یکسانی نبوده و بین برخی از کارها محدودیتهای تقدمی در پردازش ماشینها وجود دارد. در مسأله، زمانهای آمادهسازی قبل از پردازش کارها در نظر گرفته شده است که این زمانها به توالی کارها و همچنین نوع ماشینی که بر روی آن قرار میگیرند، وابسته هستند.
ژانگ و همکاران [21] یک مسأله زمانبندی ماشینهای موازی نامرتبط که در آن کارهای مختلف بهصورت پویا و بر اساس فرآیند پواسون وارد میشوند. در این مسأله، زمان دسترسی کارها و موعد تحویل آنها به صورت تصادفی میباشند.
ادیس و اگوز [22] مسأله زمانبندی منابع انعطافپذیر ماشینهای موازی مورد بررسی قرار گرفته است. یک مدل عدد صحیح ریاضی برای دو حالت قطعی و پویا با هدف کمینه کردن زمان تکمیل کارها ارائه شده است. برای حل ابعاد بزرگ این مسأله، یک رویکرد برنامهریزی متغیرهای IP ارائه گردیده است.
2-3- مروری بر توابع هدف در محیط ماشینهای موازیدر سالهای اخیر، تحقیقات زمانبندی شامل معیارهای عملکرد بیقاعده مورد توجه بسیاری قرار گرفتهاند که در نتیجه افزایش شرایط رقابتی در بازارهای محلی و بینالمللی میباشد. دو معیار عملکرد بیقاعده که عموماً در مسائل زمانبندی ماشینها مورد توجه قرار میگیرند عبارتند از: معیارهای minsum و معیارهای minmax. معیار minsum به دنبال حداقل کردن مجموع انحرافات مطلق وزنی زمان تکمیل کارها از موعدهای تحویل به منظور حداقل کردن مجموع نارضایتی مشتریان میباشد. در حالیکه معیار minmax به دنبال حداقل کردن حداکثر انحراف مطلق وزنی تکمیل کارها از موعدهای تحویل به منظور حداقل کردن حداکثر نارضایتی مشتریان میباشد.
چنگ و سین [23] مروری کامل بر روی مسائل زمانبندی ماشینهای موازی با معیارهای عملکرد معمول مبتنی بر موعد تحویل، زمانهای تکمیل و زمانهای در جریان ساخت ارائه دادند. دانگ کوا و همکاران [24] به طور همزمان مسأله انتخاب و زمانبندی ماشینهای موازی نامرتبط را به منظور حداقل کردن هزینههای نگهداری ماشینها و هزینه دیرکرد کارها مورد بررسی قرار دادند. آنها مدل بهینهسازی ترکیباتی توسعه دادند. واضح است که حل این مسأله از طریق الگوریتم جستجوی brute force با افزایش اندازه مسأله کارا نخواهد بود. در نتیجه برای حل مسأله، الگوریتم جستجوی ابتکاری مبتنی بر الگوریتم جستجوی ممنوع پیشنهاد شده است. مکانیسم جستجوی ممنوع بهمنظور کنترل کردن فضای جستجو در همسایگی جواب برای کارهای زمانبندی شده بر روی ماشین ویژهای طراحی شده است. این الگوریتم قادر به یافتن جوابهای بهینه یا نزدیک به بهینه میباشد. لام و زینگ [25] مسأله زمانبندی ماشینهای موازی را با معیار عملکرد بیقاعده مورد بررسی قرار دادند که شامل مفاهیم مرتبط با سیستمهای تولیدی انعطافپذیر و سیستمهای تولیدی بهموقع بود.
بسیاری از کارهای انجام شده تنها به میزان دیرکرد به عنوان جریمه تکمیل کار بعد از موعد مقرر توجه کردهاند و برای تکمیل کارها قبل از موعد مقرر جریمهای در نظر گرفته نشده است. گسترش مفهوم تولید بهموقع و هوشیار شدن از مزایای این فلسفه تولیدی، منجر به در نظر گرفتن جریمه برای کارهایی که قبل از موعد مقرر تکمیل میشوند علاوه بر جریمه تکمیل کار بعد از موعد مقرر شده است.
اولین کار انجام شده در این زمینه توسط کنت [26] منجر به ایجاد الگوریتم چند جملهای برای حداقل کردن کل انحراف زمانهای تکمیل از موعدهای تحویل مشترک بر روی تک ماشین شد. در مسأله مورد بررسی، موعدهای تحویل به صورت نامحدود کننده در نظر گرفته شدهاند. موعد تحویل به صورت نامحدود کننده در نظر گرفته میشود اگر آن قدر زود نباشد که به عنوان محدودیتی بر روی مسأله زمانبندی عمل کند.
بانک و ورنر [27] مسأله زمانبندی ماشینهای موازی نامرتبط را با هدف حداقل کردن مجموع وزنی دیرکرد و زودکرد مورد بررسی قرار گرفته است. در مسأله مورد بررسی کارها دارای زمان تحویل مشترک میباشند و همچنین تمامی کارها در زمان صفر در دسترس نیستند؛ به عبارت دیگر، مسأله در محیط پویا مورد بررسی قرار گرفته است. در این کار ابتدا چندین خصوصیت ساختاری توسعه پیدا کردهاند و سپس با توجه به ویژگیهای حاصل شده الگوریتمهای فراابتکاری برای حل مسأله پیشنهاد شدهاند.
قانون Covert ، اولین قانون دیسپچینگ مرکبی است که در [28] توسط کراول و همکاران برای حداقل کردن کل دیرکرد ارائه شده است. این قانون در ابتدا برای محیطهای تک ماشین و ماشینهای موازی طراحی شده بود، اما این قانون میتواند در محیط کار کارگاهی نیز به کار گرفته شود. در این قانون، اهمیت کار به طور خطی در بازه فرض شده افزایش مییابد در حالیکه میزان slack کاهش مییابد.
وپسالاینن و مورتن [29] برای اولین بار قانون ATC را برای حداقل کردن دیرکرد وزنی پیشنهاد کردند. مورتون و پنگ سی او [30] قانون ATC را در مسألهای مورد بررسی قرار دادند که در آن برای زودکرد نیز علاوه بر دیرکرد جریمه در نظر گرفته شده است. این قانون در محیط تک ماشین، محیط ماشینهای موازی و محیطهای دیگر نیز مورد استفاده قرار گرفته است. پیندو و همکاران [31] قانون ATCS را توسعه دادند که زمان آمادهسازی را علاوه بر قانون ATC در نظر میگرفت. قانون ATCS، تاثیر slack باقیمانده و تأثیر زمان آمادهسازی را به صورت مجزا در نظر میگرفت.
پارک و همکاران [32] مسأله زمانبندی کارها بر روی ماشینهای یکسان با زمانهای آمادهسازی وابسته به توالی و مستقل از ماشین را مورد بررسی قرار دادند. تابع هدف در نظر گرفته شده به دنبال یافتن توالی به گونهای بود که مجموع دیرکرد وزنی حداقل شود. بسطی از قانون ATCS پیشنهاد شده است. در این کار علاوه بر چهار عامل در نظر گرفته شده در [31] عامل دیگری تعریف شده است و شبکهی عصبی برای به دست آوردن مقادیر صحیحی از پارامترهای پیشبینی، توسعه یافته است.
بسیاری از صنایع همچون هواپیماسازی، الکترونیک و تولید نیمهرسانا، توازن را در مسائل زمانبندی در نظر میگیرند که در آن چندین تابع هدف باید مورد توجه قرار گیرد؛ بدین منظور که عملکرد کلی سیستم بهینه شود. بهینه کردن تنها یک تابع هدف، عموماً منجر به بدتر شدن تابع هدف دیگر میشود. برای مثال، افزایش میزان ورودی محصول به داخل سیستم، عموماً منجر به افزایش خروجی میشود، اما از سویی دیگر میزان موجودی در حال ساخت را افزایش میدهد. زمانبندی ماشینهای موازی، مسأله سخت چند جملهای است حتی برای مسائل تک هدفه که در آن هدف مورد نظر حداقل پیچیدگی را دارد. هیچ روشی قادر به تولید جوابهای بهینه برای موارد چند هدفه در زمان چند جملهای نیست. این مسأله، کیفیت طراحی و آنالیزی را که میتواند در مقدار زمان مشخص تعیین شدهای انجام شود، محدود میسازد. برای مسائل چند هدفه تعیین مجموعهای درست از جوابهای پارتو، حداکثر اطلاعات را در مورد مسائل بهینهسازی به همراه دارد. کوچران و همکاران [33]، الگوریتم ژنتیک چند جمعیتی دو مرحلهای، برای حل مسائل زمانبندی ماشینهای موازی با دو تابع هدف حداکثر زمان تکمیل کارها و کل دیرکرد وزنی پیشنهاد شده است. همچنین مدل پیشنهاد شده در حالت در نظر گرفتن سه تابع هدف حداکثر زمان تکمیل کارها، کل دیر کرد وزنی و کل زمان تکمیل کارهای وزنی توسعه داده شده است.
2-4- مروری بر روشهای حل در محیط ماشینهای موازیدر حوزه مسائل بهینهسازی میتوان روشهای حل را به دو دسته کلی تقسیمبندی کرد. روشهای دقیق و روشهای تقریبی. روشهای دقیق شامل روشهایی میشوند که با استفاده از آنها میتوان جواب بهینه کلی را یافت. در حالیکه روشهای تقریبی شامل روشهایی میشوند که با استفاده از آنها تنها میتوان جوابی نزدیک به بهینه کلی را یافت. در واقع روشهای تقریبی دارای تضمینی بهمنظور رسیدن به جواب بهینه کلی نمیباشند. در ادامه این فصل مروری بر روی ادبیات موضوع الگوریتمهای فراابتکاری در حوزه مسائل زمانبندی خواهیم داشت.
الگوریتمها براساس روشهای فراابتکاری تقریباً به طور گسترده برای حل مسائل زمانبندی مورد استفاده قرار گرفتهاند و آنها ابزاری ارزشمند برای فراهم آوردن جوابها با کیفیت بالا میباشند. روش فراابتکاری، اصول و ویژگیهایی را که مورد نیاز هستند تا بر روی مسأله مورد نظر اعمال شوند، شرح میدهد.
پالوچی و انگینولفی [34]، مسألهای مورد بررسی قرار گرفته است که هدف آن ارزیابی امکان تعریف الگوریتمهای فراابتکاری تطبیق یافته هیبرید شده از الگوریتمهای فراابتکاری مرجع یعنی جستجوی ممنوع، باز پخت شبیهسازی شده و جستجوی همسایگی متغیر بود. رویکرد فراابتکاری هیبرید شده پیشنهاد شده به مسأله سخت حداقل کردن کل دیرکرد در زمانبندی ماشینهای موازی اعمال شد. زمانهای در دسترس متفاوت، موعدهای تحویل مجزا و زمانهای آمادهسازی و ماشینهای یکنواخت محدودیتهای در نظر گرفته شده در مسأله مورد نظر میباشند.
مسأله بررسی شده در [35] توسط اوزسی و مالوی، قسمتی از تلاش در حال جریان برای توسعه سیستمهای بهینه زمانبندی در صنایع نیمهرسانا میباشد. آنها مسأله را به صورت حداقل کردن حداکثر دیرکرد بر روی ماشینهای پردازش دستهای یکسان با زمانهای متفاوت آماده به کار بودن کارها در نظر گرفتند. تعداد متنوعی از الگوریتمهای ابتکاری برای مسأله حداقل کردن حداکثر دیرکرد بر روی ماشینهای پردازش دستهای یکسان پیشنهاد شده است. این روشها همچنین با الگوریتم ژنتیک ترکیب شدهاند. با انجام دادن محاسبات وسیع، آنها به این نتیجه رسیدند که ترکیب الگوریتم ابتکاری تکرار شونده با الگوریتم ژنتیک به طور ثابت بهتر از الگوریتمهای ابتکاری تکرار شونده عمل میکند.
در ادامه برخی از واژگان مطرح در حوزه مسائل چندهدفه و برخی از روشهای مطرح برای حل مسائل چند هدفه را مورد بررسی قرار میدهیم.
2-5- مسائل چند هدفهبهینهیابی چندهدفه بر خلاف بهینهیابی تکهدفه با فضای متغیرهای تصمیم سروکار ندارد و روند بهینهیابی بر روی فضای اهداف انجام میشود. در شکل، فضای 3 متغیر تصمیم و فضای دو هدف را مشاهده میکنید، هر جواب شامل 3 متغیر تصمیم، در فضای هدف تصویر میشود (شکل 2-1):
شکل 2-1- محیط متغیرهای تصمیم و فضای هدف [36]
در روشهای کلاسیک برای حل چنین مسائلی برای هر تابع هدف ارزشی در نظر گرفته میشد و بر این اساس وزنی خاص به توابع اختصاص داده میگردید، اهداف را به یک تابع هدف تبدیل و در انتهای بهینهیابی یک جواب به تصمیمگیرنده اعلام میگردید. روشهای کلاسیک توانایی پوشش کاملی از فضای جواب نداشته و بسیار وقتگیر بودند. بهینهیابی چندهدفه دارای مفاهیم زیادی است که در این پایاننامه قصد تشریح کامل این مطالب را نداریم، تنها به مواردی خاص و مورد نیاز اکتفا شده است، علاقهمندان برای اطلاعات بیشتر در مورد بهینهیابی چندهدفه میتوانند به کتاب "الگوریتمهای ژنتیک با رویکرد بهینهیابی چندهدفه" نوشته "کالیانموی دب" [36] مراجعه کنند.
بر خلاف بهینهیابی تکهدفه، در بهینهیابی چندهدفه نمیتوان تنها یک جواب بهینه ارائه کرد، در این روشها مجموعهای از جوابها ارائه میگردد که نسبت به جوابهای دیگر برتری دارند، این مجموعه را مجموعه جوابهای غیر مغلوب مینامند، مجموعه جوابهای غیرمغلوب نهایی بهینهیابی نیز مجموعه پارتو یا سطح پارتو نامیده میشود. این مجموعه جواب دارای شرایطی است، برای مثال یک مسأله دو هدفه و کمینهسازی دو هدف را در نظر بگیرید (شکل 2-2)، مجموعه نقاط سیاه رنگ نسبت به نقاط سفید برتری دارند و یا حداقل نسبت به جواب هم سطحی خود دارای شرایط یکسانی هستند (نقاط A و B نسبت به یکدیگر) در نتیجه مجموعه جوابهای سیاه رنگ مجموعه غیرمغلوب محسوب میشوند.
A
B
شکل 2-2- مجموعه جوابهای مغلوب و غیرمغلوب
مسأله بهینهسازی چندهدفه را به طور کلی میتوان از لحاظ ریاضی به شکل زیر بیان کرد:
f(x)Minimize
g(x)≤0with
hx=0and
x∈IRn,fx∈IRk,gx∈IRm,h(x)∈IRpهمانطور که در بالا مشخص شده است، بردار f شامل k تابع هدف میباشد که باید بهینه شوند. هنگامیکه مسأله بهینهسازی چندهدفه حل میشود، اغلب، مجموعه جوابی حاصل میشود. تنها مجموعه کوچکی از این جوابها قابل قبول خواهند بود. برای جواب قابل قبول باید رابطهی تسلّط میان آن و جوابهای دیگر به شکل زیر برقرار باشد:
تعریف 2-1- رابطه تسلط: بردار x1 بر بردار x2 غالب است اگر: x1 برای تمام اهداف حداقل به
همان اندازه خوب است که x2 خوب میباشد و x1 حداقل برای یک هدف به طور حتم بهتر از x2 میباشد.
جوابهایی که غالب بر دیگر جوابها میباشند ولی بر یکدیگر غالب نمیباشند جوابهای بهینه به صورت پارتو نامیده میشوند (جوابهای غیرمغلوب).
بهینگی موضعی و بهینگی کلی در مفهوم پارتو به شکل زیر تعریف میشود.
تعریف 2-2- بهینگی موضعی در مفهوم پارتو: بردار x ∈IRn بهینه موضعی در مفهوم پارتو است اگر مقدار حقیقی δ>0 وجود دارد چنانکه هیچ بردار x' غالب بر بردار x وجود ندارد در صورتیکه x' ∈IRn∩B(x,δ) که در آن B(x,δ) بیانگر دایرهای به مرکز x و شعاع δ میباشد.
تعریف 2-3- بهینگی کلی در مفهوم پارتو: بردار x بهینه کلی در مفهوم پارتو میباشد اگر هیچ بردار x' غالب بر بردار x وجود نداشته باشد.
2-6- روشهای حل مسائل بهینهسازی چندهدفهروشهای مختلفی برای حل مسائل بهینهسازی وجود دارد که میتوان آنها را به پنج دسته تقسیم کرد.
روشهای وزندهی
روشهای تعاملی