واژههاي کليدي:سیستم تولید جریانی، پذیرش و رد کارها، نگهداری پیشگیرانه، تولید بهنگام، الگوریتمهای فراابتکاری. فهرست مطالب ثفهرست جدولهاجفهرست شکلها1فصل اول :کلیات تحقیق21-1- مقدمه21-2- مفهوم زمانبندی31-3- اهمیت و ضرورت زمانبندی41-4- طبقهبندی و مفاهیم پایه مسایل زمانبندی تولید61-4-1- طبقهبندی محیطهای تولیدی81-4-2- خصوصیات کار و محدودیتهایی که بر محیط اعمال میشود91-4-2-1-محدودیت رد یا پذیرش سفارشات101-4-2-2- محدودیت دسترسی به ماشینها121-4-3- توابع هدف و ویژگیهای آنها141-4-3-1- نظام تولید بهنگام151-5- بیان مساله جریان کارگاهی در نظر گرفته شده در این مطالعه161-6- روش حل171-7- اهداف تحقیق171-8- نتیجهگیری19فصل دوم : ادبیات تحقیق202-1- مقدمه202-2- مروری بر ادبیات کارگاه گردش کاری222-3- زمانبندی و محدودیت دسترسی ماشینها232-3-1- مروری بر ادبیات مساله کارگاه گردش کاری با محدودیت دسترسی ماشینها252-4- مروری بر ادبیات محدودیت رد یا پذیرش سفارشات27فصل سوم : روشهای حل 283-1- مقدمه283-2- تعریف مساله293-3- مدل پیشنهادی333-4- اعتبارسنجی مدل343-5- پیچیدگی مساله363-6- الگوریتم ژنتیک373-6-1- واژگان الگوریتم ژنتیک383-6-2- شمای کلی الگوریتم ژنتیک393-6-3- مفاهیم الگوریتم ژنتیک393-6-3-1- کدگذاری423-6-3-2- جامعه اولیه423-6-3-3- عملیات ژنتیک473-6-3-4- تابع برازش473-6-3-5- شرط توقف الگوریتم483-7- پیادهسازی الگوریتم ژنتیک پیشنهادی483-7-1- کدگذاری الگوریتم493-7-2- ایجاد جمعیت اولیه503-7-3- تابع برازش503-7-4- عملگرهای ژنتیک503-7-4-1- عملگر تقاطع533-7-4-2- عملگر جهش543-7-4-3- عملگر نخبهگرایی543-7-4-4- معیار توقف543-7-4-5- جستجوی موضعی553-8- تبرید شبیهسازی شده573-8-1- مفاهیم الگوریتم573-8-1-1- جواب همسایگی573-8-1-2- دما573-8-1-3- الگوی کاهش دما583-8-1-4- احتمال پذیرش جوابها583-8-1-5- شرط توقف593-9- پیادهسازی الگوریتم شبیهسازی تبرید پیشنهادی593-9-1- روش نمایش جواب593-9-2- جواب اولیه593-9-3- ساختار همسایگی603-9-4- برنامه انجماد603-9-5- قاعده توقف613-10- نتیجهگیری62فصل چهارم : نتایج محاسباتی634-1- مقدمه634-2- تولید مسایل نمونه644-3- تنظیم پارامتر664-3-1- تنظیم پارامتر الگوریتم ژنتیک674-3-1-1- طراحی آزمایشات چند عاملی724-3-2- تنظیم پارامتر الگوریتم شبیهسازی تبرید734-3-2-1- طراحی آزمایشات چند عاملی برای الگوریتم شبیهسازی تبرید794-4- نتایج محاسباتی854-5- جمعبندی86فصل پنجم : نتیجهگیری و پیشنهادها875-1- نتیجهگیری875-2- پیشنهادها89فهرست مراجع فهرست جدولها جدول4-1- حدود پارامترهای مسایل تولید شده64جدول4-2- پارامترهای کنترلکننده الگوریتم ژنتیک و محدوده موثر آنها67جدول4-3- ترکیبات عاملها و سطوح پاسخ نرمال شده در آزمایشات چند عاملی الگوریتم ژنتیک68جدول4-4- پاسخ نسبت های S/N در الگوریتم ژنتیک68جدول 4-5- پاسخ میانگینها در الگوریتم ژنتیک68جدول 4-6- مقادیر بهینهی پارامترهای کنترل کننده الگوریتم ژنتیک70جدول 4-7- پارامترهای کنترل کننده الگوریتم شبیهسازی تبرید و محدوده موثر آنها74جدول4-8- ترکیبات عاملها و سطوح پاسخ نرمال شده در آزمایشات چند عاملی الگوریتم شبیهسازی تبرید74جدول4-9- پاسخ نسبتهای S/N در الگوریتم شبیهسازی تبرید75جدول 4-10- پاسخ میانگینها در الگوریتم شبیهسازی تبرید75جدول 4-11- مقادیر بهینهی پارامترهای کنترل کننده الگوریتم شبیهسازی تبرید77جدول 4-12- حل مسایل کوچک با روش شاخه و کران و الگوریتمهای فراابتکاری پیشنهادی79جدول 4-13- مقایسه جوابهای الگوریتمهای فراابتکاری در ده تکرار برای مسایل مختلف82جدول 4-14- مقایسه RPD% برای مسایل مختلف84 فهرست شکلها شکل 1-1- تقسیمبندی و نحوه ارتباط مسایل زمانبندی5شکل3-1- کدگذاری ترتیبی39شکل3-2- کدگذاری ارزشی40شکل3-3- کدگذاری درختی40شکل3-4- فضای کدگذاری و فضای جواب41شکل3-5- موجهبودن و قانونمندی کروموزومها42شکل3-6- تقاطع تک نقطهای46شکل3-7- تقاطع دو نقطهای46شکل3-8- ساختار کلی الگوریتم ژنتیک48شکل3-9- نمایش کروموزوم49شکل3-10- انتخاب دو کروموزوم والد51شکل3-11- مرحله دوم عملگر تقاطع برای ایجاد توالی51شکل3-12- مرحله سوم عملگر تقاطع برای ایجاد توالی52شکل3-13- مرحله چهارم عملگر تقاطع برای ایجاد توالی52شکل3-14- عملگر تقاطع برای ایجاد بخش دوم کروموزوم53شکل3-15- عملگر جهش برای بخش اول کروموزوم53شکل3-16- عملگر جهش برای بخش دوم کروموزوم54شکل3-17- شبهکد الگوریتم شبیهسازی تبرید56شکل3-18- عملگرهای تغییر توالی در الگوریتم شبیهسازی تبرید پیشنهادی60شکل4-1- میانگین نسبت S/N در الگوریتم ژنتیک69شکل4-2- پاسخ میانگین در الگوریتم ژنتیک70شکل4-3- میانگین نسبت S/N در الگوریتم ژنتیک برای مسایل در اندازههای متوسط71شکل4-4- پاسخ میانگینها در الگوریتم ژنتیک برای مسایل در اندازههای متوسط72شکل4-5- میانگین نسبت S/N در الگوریتم شبیهسازی تبرید76شکل4-6- پاسخ میانگینها در الگوریتم شبیهسازی تبرید76شکل4-7- میانگین نسبت S/N در الگوریتم شبیهسازی تبرید برای مسایل در اندازههای متوسط78شکل4-8- پاسخ میانگینها در الگوریتم شبیهسازی تبرید برای مسایل در اندازههای متوسط78شکل4-9- زمان محاسباتی روش شاخه و کران80شکل4-10- نمودار LSD در سطح اطمینان 95% برای مقادیر RPD85 فصل اول کليات تحقيق 1-1- مقدمهرمز بقای هر سازمان، ارایه خدمات با کیفیت بالا و قیمت پایین است. یکی از عوامل موثر در کیفیت و قیمت ارایه خدمات و کالاها، زمان تولید ارایه آن خدمات است. توالی[1] و زمانبندی[2] عملیات در خلال اجرای مجموعهای از وظایف، از مهمترین دغدغههای تصمیمگیرندگان در عرصه صنعت و خدمات بوده است. در دنیای رقابتی امروز زمانبندی و توالی موثر، در ادامه حیات سازمان در بازار رقابتی از اهمیت فوق العادهای برخوردار است. شرکتها باید سفارش رسیده از سوی مشتریان را بهموقع برآورده کنند، زیرا انجام ندادن بهموقع کار باعث از دست دادن سود است]1[.زمانبندی تولید، مسالهای است که هم بر روی تحویل بموقع کالاها و هم بر روی استفاده بهینه از سرمایههای سازمان اثرگذار است. در یک مساله زمانبندی زمانهای شروع و پایان فعالیتها، دستگاهها،تجهیزات مورد نیاز و... تعیین میشود.با توجه به تاثیر زمانبندی بر دو هدف اصلی سازمانهای تولیدی، ارایه مدلهای زمانبندی از دیرباز مد نظر بوده است. با اینکه پژوهشگران زیادی در ارایه مدلهای زمانبندی فعالیت کردهاند، ولی هنوز مدلهایی که کاملا جوابگوی سازمانها باشند به صورت جامع ارایه نشدهاند]2[. 1-2- مفهوم زمانبندیزمانبندی، تخصیص منابع در طول زمان، برای انجام مجموعهای از فعالیتها با هدف بهینهسازی یک یا چند معیار عملکرد است. به عبارتی دیگر، در زمانبندی به دو سوال اساسی زیر پاسخ داده میشود:رویکرد عملی به مساله برنامهریزی عملیات[3]، ریشه در انقلاب صنعتی و تلاشهای هنری گانت دارد. در اکثر قریب به اتفاق مسایل برنامهریزی به طور اعم و مساله تعیین توالی عملیات به طور اخص، حالات مختلف حل مساله و ترکیبهای حاصل از این تنوع، برنامهریزان را با طیف گستردهای از راه حلهای مساله روبهرو میسازد.توالی عملیات در برنامهریزی به عنوان یک معیار تصمیمگیری مطرح بوده است، روشهای متفاوتی برای انتخاب نوع تصمیمات وجود دارند که از آن جمله میتوان به روشهای ترکیبی، شبیهسازی، شبکه، الگوریتمهای ابتکاری و فراابتکاری اشاره کرد. مشخص کردن توالیهای بهینه یا مناسب میتواند منجربه میزان قابل توجهی صرفهجویی در زمان و هزینه شود، که این امر به نوبه خود میتواند اثر بسیار مهمی بر عملکرد سازمان داشته باشد، و بهعلاوه باعث رضایت مشتریان از بنگاه شود که مطمئنا در حفظ مشتریان موثر خواهد بود.]2[ 1-3- اهمیت و ضرورت زمانبندیبا ادامه فرایند صنعتی شدن جهان، منابع بیشتری حالت بحرانی به خود میگیرند. امروزه، ماشینآلات، نیروی انسانی و تسهیلات به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند. زمانبندی این منابع منجر به ارتقای کارایی، بهرهوری و در نهایت، سودآوری میشود. زمانبندی، مشخص میکند که چه موقع زمان پردازش هر کار روی هر یک از ماشینهایی که آن کار در فرایند تولید خود به آن نیاز دارد، آغاز شود. به علاوه، این برنامه زمان پایان هر کار را روی هر ماشین تعیین میکند. بنابراین، نتیجه فرآیند زمانبندی، یک جدول زمانی برای کارها و ماشینهاست. زمان شروع اولین فرایند هر کار باید بزرگتر یا مساوی با زمان ورود آن کار به کارگاه باشد. از طرف دیگر، در صورتی که برای محصولی، موعد تحویل در نظر گرفته شده باشد، زمان پایان آخرین فرایند آن محصول حتیالامکان نباید از این زمان تجاوز کند. زمانبندی تولید را میتوان به صورت تعیین توالی زمانی و تخصیص سفارشات مشتریان به منابع موجود تولید( اعم از پرسنل، ماشینآلات، ابزار و غیره) به منظور انجام مجموعهای از عملیات مربوطه تعریف کرد. معمولا زمانبندی با توجه به اهدافی نظیر: دستیابی به موعدهای تعیین شده، کمینهسازی زمان کار در جریان ساخت و موجودی کار در جریان ساخت، بیشینهسازی خروجی و بهرهبرداری بیشتر از مراکز کاری[4]، انجام میشود]3[.مساله زمانبندی در همه قلمروهای اقتصادی از مهندسی کامپیوتر تا تکنیکهای تولید کاربرد دارد. بیشتر مسایل زمانبندی، مسایل بهینهسازی پیچیده ترکیبی هستند و حل آنها بسیار دشوار است.مساله زمانبندی تولید جریانی یکی از جذابترین مسایل زمانبندی است که در بین پژوهشگران از توجه بسیار بالایی برخوردار بوده است. پژوهشگران در مقالات متعدد، حالات و فرضیات مختلفی از این محیط را مطالعه، مدلسازی و حل کردهاند. اما با همه این تلاشها هنوز هم بررسیها برای مدلسازی جامعتر و منطبق با واقعیتها و ارایه روشهای حل کاراتر ادامه دارند. 1-4- طبقه بندی و مفاهیم پایه مسایل زمانبندی تولیدطبقهبندیهای متنوعی از مسایل تولید صورت گرفتهاند که در ادامه به چند مورد اشاره میکنیم. میلر[5]]4[ مسایل زمانبندی تولید را بر اساس ساختار تولید به هشت دسته تک ماشینه[6]، کارگاه گردش کاری[7]، کارگاهی[8]، کارگاه باز[9]، ماشینهای موازی[10]، کارگاه گردش کاری با ماشینهای موازی[11]، کارگاهی با ماشینهای موازی[12]و کارگاه باز با ماشینهای موازی[13] تقسیم کرد. تقسیمبندی این مسایل و نحوه ارتباط آن ها در شکل 1-1 نشان داده شدهاند.گوپتا[14]]5[ مسایل زمانبندی تولید را به صورت پویا[15]یا ایستا[16]، قطعی[17] یا احتمالی[18]، تک محصولی[19] یا چند محصولی[20]، تک پردازشی یا چند پردازشی و ... دستهبندی کرد. گراهام[21]و همکاران ]6[ مسایل زمانبندی قطعی را با سه تایی طبقهبندی کردند، که بیانگر محیط ماشین و تعریفی از نظم و سازماندهی ماشین، نشان دهنده جزییات و ویژگیهای فرایند یا محدودیتها، و تابع هدف زمانبندی (معیار زمانبندی) هستند.کارگاه باز با ماشینهای موازیکارگاهی با ماشینهای موازیکارگاه گردش کاری با ماشینهای موازیکارگاه گردش کاریتک ماشینهماشینهای موازیکارگاه بازکارگاهی شکل 1-1-تقسیم بندی و نحوه ارتباط مسایل زمانبندی]4[1-4-1- طبقه بندی محیطهای تولیدیابتداییترین مدل زمانبندی تولید، انجام کار متوالی روی یک ماشین است. در این سیستمها تنها یک ماشین روی کارهای مختلف، فرایندی را انجام میدهند و به عبارت دیگر، میتوانیم بگوییم که برای هر کار تنها یک فرایند تعریف میشود.مجموعهای از ماشینهایی به صورت موازی در کنار هم قرار میگیرند و عملیات پردازش روی کارها را انجام میدهند. در این حالت، هر کار تنها نیاز به یک فرایند دارد . ابتدا هر یک از کارها به ماشینها تخصیص مییابد و سپس برای کارهای تخصیص یافته به هر ماشین یک ترتیب تعیین میشود. ماشینهای موازی به سه صورت مختلف ماشینهای موازی یکسان[22]، ماشینهای موازی با سرعتهای متفاوت[23]، ماشینهای موازی ناوابسته[24] تقسیم میشوند.در اکثر سیستمهای ساخت و مونتاژ تعدادی عملیات روی هر کار انجام میشود. اغلب، این عملیات روی همه کارها به ترتیب یکسانی انجام میشود، که این خود دلیل بر این است که کارها در مسیر یکسانی جریان مییابند. در واقع، ماشینها در چنین محیطی که کارگاه گردش کاری (فلوشاپ) معروف است، به صورت سری چیده میشوند.