كلمات كليدي : برنامهريزي رياضي، مسأله زمانبندي کارگاه باز، بهينه سازي چند هدفه، نگهداري و تعميرات دورهاي، الگوريتمهاي فرا ابتکاري، طراحي آزمايشات تاگوچي. فهرست مطالبعنوانصفحه1- فصل اول: معرفي و كليات تحقيق11-1- مقدمه21-2- تعاريف زمانبندي31-2-1- نمادها31-2-2- محيط ماشينها و نوع كارگاه41-2-3- مشخصههاي كاري و محدوديتهاي زمانبندي51-2-4- معيارهاي بهينهسازي71-3- نظريهء زمانبندي91-4- برنامهريزي رياضي91-5- زمانبندي چند هدفه91-6- الگوريتمهاي فرا ابتكاري در بهينهسازي111-6-1- الگوريتم ژنتيك111-6-2- الگوريتم شبيهسازي تبريد121-7- طراحي آزمايشات121-8- مسألهء زمانبندي كارگاه باز132- فصل دوم: مرور ادبيات152-1- مقدمه162-2- معيارهاي اندازهگيري و تابع هدف162-3- مجازنبودن بريدگي كارها182-4- نگهداري و تعميرات دورهاي و محدوديت عدم دسترسي ماشينها182-5- زمانهاي حمل و نقل192-6- زمانهايآمادهسازي و جداسازي202-7- روشهاي حل202-8- طراحي آزمايشات223- فصل سوم: طرح مسأله و ارائه روشهاي حل243-1- مقدمه253-2- فرمولبندي مسأله253-2-1- فرضهاي مسأله253-2-2- نماد گذاري263-2-2-1- انديسها263-2-2-2- پارامترها263-2-2-3- متغيرهاي تصميم263-2-3- مدل برنامهريزي خطي مختلط263-2-4- يك مثال283-2-5- تحليل مدل293-3- الگوريتمهاي فرا ابتكاري303-3-1- الگوريتم ژنتيك303-3-1-1- نمايش كروموزوم303-3-1-2- جمعيت اوليه303-3-1-3- تابع هدف313-3-1-4- تابع برازندگي313-3-1-5- انتخاب313-3-1-6- تقاطع313-3-1-7- جهش333-3-1-8- معيار توقف333-3-1-9- الگوريتم ژنتيك اوليه333-3-1-10- الگوريتم ژنتيك موازي چند هدفه343-3-2- الگوريتم شبيهسازي تبريد353-3-2-1- الگوريتم شبيهسازي تبريد اوليه353-3-2-2- الگوريتم شبيهسازي تبريد موازي چند هدفه374- فصل چهارم: طراحي آزمايشات و ارزيابي محاسباتي384-1- مقدمه394-2- طراحي آزمايشات تاگوچي394-2-1- توليد دادهها404-2-2- تنظيم پارامترهاي الگوريتم MOPGA404-2-3- تنظيم پارامترهاي الگوريتم MOPSA424-3- ارزيابي محاسباتي43 5- فصل پنجم: جمعبندي و مطالعات آتي 455-1- جمعبندي465-2- مطالعات آتي46مراجع48 فهرست جداولعنوانصفحه1-1- مقادير پارامتر α51-2- مقادير پارامتر β71-3- مقادير پارامتر γ83-1- تعداد متغيرها293-2- تعداد محدوديتها293-3- تعداد متغيرها و محدوديتها مطابق با مدل MOMILP294-1 فاكتورهاي الگوريتم MOPGAو سطوح آنها414-2- آزمايشات مربوط به آرايهء L9در الگوريتمMOPGA414-3- جدول تحليل واريانس كسرS/Nمربوط به فاكتورهاي الگوريتمMOPGA424-4- فاكتورهاي الگوريتمMOPSAو سطوح آنها424-5- آزمايشات مربوط به آرايهءL4در الگوريتمMOPSA424-6- جدول تحليل واريانس كسرS/Nمربوط به فاكتورهاي الگوريتمMOPSA434-7- عملكرد مدلMOMILPو الگوريتمهايGAوSAاوليه در برخورد با مسألههاي با ابعاد كوچك444-8- ميانگينRPDبراي الگوريتمهايMOPGAوMOPSAدر حل مسألههاي با ابعاد بزرگ44 فهرست شكلهاعنوانصفحه1-1- رابطهء جايگزيني بين دو هدف و103-1- توالي كارها روي يك ماشين j253-2- نمودار گانت مربوط به حل بهينهء مثال283-3- نحوهء تقسيمبندي جمعيت و عملكرد موازي زير-جمعيتها343-4- جستجوي همسايگي الگوريتم شبيهسازي تبريد363-5- قدمهاي الگوريتم شبيهسازي تبريد اوليه364-1- نمودار كسرS/Nمربوط بهRPDدر فاكتورهاي الگوريتمMOPGA414-2- نمودار كسرS/Nمربوط بهRPDدر فاكتورهاي الگوريتمMOPSA43معرفي و كليات تحقيق 1-1-مقدمهاز مهمترين شرطهاي ارتقاي وضعيت فعلي در هر سازمان ميتوان به استفادهء مناسب از سرمايهها و جلوگيري از هدر رفت آنها اشاره كرد. منظور از " استفادهء مناسب " در اينجا مفهومِ واژهء كارايي[1] يعني سرعت عمل در استفاده از ظرفيت است كه بدون داشتن برنامهء از پيش تعيين شده ممكن نيست. افزون بر آن، هرچه دقت در برنامه بيشتر و مطالعه مكفيتر باشد سرعت عمل بيشتر شده و توان رقابتي بالاتر ميرود. وقتي صحبت از سرمايههاي يك سازمان به ميان ميآيد ممكن است ذهنها به سمت سرمايههاي فيزيكي مثل ماشينآلات و دستگاههاي گرانقيمت منحرف شود. حال آنكه، مفهوم مورد انتظار ما بطور خاص "زمان" است. استفادهء مناسب از زمان بعنوان يك سرمايه و جلوگيري از هدر رفت آن از جمله ابزارهاي مهم مديرانِ سازمانها در عرصههاي رقابتي است. زمان را ميتوان منبعي دانست كه بايد بطور صحيح تقسيمبندي و مديريت شده و با برنامهء خاص به فعاليتها تخصيص داده شود و اين همان چيزيست كه به آن زمانبندي[2] اطلاق ميشود.زمانبندي شامل تخصيص[3] منابع محدود به فعاليتهاست با هدف بهينهسازي يك يا چند معيار اندازهگيري[4] [1]. از طرفي، ماهيت برخي منابع همچون ماشينآلات و نيروي انساني بگونهاي است كه قادر به انجام همزمان بيش از يك فعاليت نيستند. بنابراين، تعريف ديگري براي زمانبندي به اين شرح ارائه ميشود: زمانبندي، يافتن توالي[5] مناسب انجام فعاليتها توسط ماشينها و يا نيروي انساني است بنحوي كه يك يا چند معيار اندازهگيري بهينه شوند. براي تحليل سيستم زمانبنديِ توليدِ جاري و يافتن راههاي بهبود آن، آگاهي از روشهاي زمانبندي توليد بسيار مهم است. دو مسألهء كليدي در زمانبنديِ توليد اولويت و ظرفيت هستند [2]. بعبارت ديگر، "چه كاري بايد ابتدا انجام شود؟" و "چه كسي بايد آن را انجام دهد؟" وايت [2] زمانبندي را اينگونه تعريف ميكند: "تعيين زمان براي انجام يك فعاليت". او همچنين، در يك شركت توليدي زمانبنديِ تفصيلي[6] در سطح يك كارگاه را درنظر ميگيرد. يعني، زمانبندي كه در آن زمان شروع و پايان هر عمليات معلوم است. كوكس و همكاران [3] زمانبندي تفصيلي را اينگونه تعريف ميكنند: "تخصيص واقعي زمان شروع و يا پايان فعاليتها يا گروهي از فعاليتها بنحوي كه سفارش توليد در موعد مقرر تكميل شود." آنها همچنين از زمانبندي عمليات[7]، زمانبندي سفارش[8] و زمانبندي كارگاه[9] بطور معادل ياد ميكنند.تعابير متنوعي از تعريفهاي ارائه شده براي زمانبندي در محيط هاي مختلف قابل تصور است. بعنوان مثال، منابع ميتوانند ماشينها در يك كارگاه، پردازنده و حافظه در يك سيستم كامپيوتري، باندهاي فرود در يك فرودگاه، تعميركاران در يك تعميرگاه خودرو و غيره باشند. همچنين، فعاليتها ميتوانند شامل عمليات مختلف در يك فرآيند ساخت، اجراي يك برنامهء كامپيوتري، نشستن و برخاستن هواپيماها در فرودگاه، تعمير خودروهاي تعميرگاه و مواردي از اين دست باشند.مطالعه بر روي زمانبندي به دههء 1950 برميگردد كه محققان در پژوهش عملياتي[10]، مهندسي صنايع و مديريت با مسألهء اداره كردن فعاليتهاي مختلفي كه در يك كارگاه رخ ميدادند مواجه بودند. در آن زمان، الگوريتمهاي زمانبندي خوب ميتوانستند هزينهء توليد را در فرآيند ساخت كاهش داده و توان رغابتي شركتها را بالا ببرند. در اواخر دههء 1960، دانشمندان كامپيوتر نيز با مسألهء زمانبندي در توسعه سيستمهاي عملياتي روبرو شدند. چراكه، در آن روزها منابع محاسباتي همچون پردازشگرها و حافظهها محدود بودند و بهرهبرداري مؤثر از اين منابع محدود ميتوانست هزينهء اجراي برنامههاي كامپيوتري را كاهش دهد. بنابراين، مطالعه بر روي زمانبندي توجيه اقتصادي پيدا كرد [4].مسألههاي زمانبندي در دههء 1950 بسيار ساده بودند و تعدادي الگوريتمهاي كارا براي رسيدن به جواب بهينه توسعه يافتند كه كارهاي جكسون [5،6]، جانسون [7] و اسميت [8] از مهمترين آنها هستند. با گذشت زمان، مسألهها پيچيدهتر شده و ديگر محققان قادر به توسعه الگوريتمهاي كارا براي آنها نبودند. بيشتر محققان تلاش كردند روشهاي شاخه و كران[11] را كه عمدتاً الگوريتمهايي با زمان نمايي[12] بودند را گسترش دهند. با ظهور تئوري پيچيدگي[13] [11-9]، محققان دريافتند كه بسياري از اين مسألهها ذاتاً براي حل سخت هستند. در دههء 1970 نشان داده شد كه بيشتر مسألههاي زمانبندي NP-hardهستند [15-12] يعني زمان حل آنها شديداً غير چندجملهاي[14] است. در دههء 1980، چندين زمينهء مختلف در دانشگاه و صنعت مورد بررسي قرار گرفت. يكي از اين زمينهها توسعه و تحليل الگوريتمهاي تقريبي[15] و ديگري افزايش توجه به مسألههاي زمانبندي اتفاقي[16] بود. از آن پس، تحقيق در زمينهء تئوري زمانبندي با فراز و نشيبهايي همراه بودهاست. بعد از گذشت بيش از 60 سال، هنوز ابهاماتي در اين شاخه از علم وجود دارد.1-2-تعاريف زمانبنديهر چند كه مفهوم زمانبندي بسيار فراگير بوده و كاربردهاي متنوعي در محيطهاي مختلف براي آن قابل تصور است ولي ما از رويكرد سيستمهاي توليدي و صنعتي جهت بسط و گسترش آن استفاده ميكنيم. پيش از آن كه بخواهيم درمورد زمانبندي تخصصيتر صحبت كنيم، لازم است نمادها و عبارتهاي مصطلح در اين زمينه معرفي شوند. اين بخش به معرفي برخي از آنها پرداخته و پس از توضيح چند نماد و تشريح محيط مورد نظر و شرايط آن، هدفها و معيارهاي زمانبندي بيان ميشوند.1-2-1- نمادهادر زير به برخي پارامترها و نمادهايي كه در طول اين تحقيق استفاده ميشوند اشاره ميكنيم.تعداد كارها nو تعداد ماشينها mدرنظر گرفته ميشود. زير نويسهاي iو kبه كار و زيرنويسهاي jو hبه ماشين اشاره دارند. بدينترتيب، اصطلاحات زير مربوط به كار i هستند:زمان پردازش[17] (pij): مدت زمان پردازش كار iتوسط ماشين jاست كه در صورت عدم استفاده از ماشين jدر فرآيند تكميل كار i، اين مقدار صفر درنظر گرفته ميشود و چنانچه قرار باشد كار iتنها توسط يكي از mماشين (هركدام) پردازش شود زير نويس jحذف ميشود.زمان آمادهسازي[18] (Sij): زمان آمادهسازي كار iروي ماشين j مدت زماني است كه طول ميكشد تا كار روي ماشين قرار گرفته، تثبيت شده و آمادهء پردازش شود. عمليات پردازش بلافاصله پس از اتمام آمادهسازي شروع ميشود.زمان جداسازي[19] (Rij): زمان جداسازي كار iاز روي ماشين j مدت زماني است كه طول ميكشد تا كار پس از تكميل پردازش از روي ماشين برداشته شود. اين زمان بدليل جدا كردن ابزار تثبيت از قطعه درنظر گرفته ميشود. اتمام زمان جداسازي بمنزله اتمام كار است.زمان آماده به كار بودن[20] (ri): نقطهاي از زمان كه كار i به سيستم وارد ميشود و در حقيقت زودترين زماني است كه ميتوان شروع به پردازش كار i نمود.موعد تحويل[21] (di): نقطهاي از زمان كه طبق قرار قبلي با مشتري بايد كار iتحويل شود. باتوجه به تعريف مذكور، تكميل كار زودتر از موعد تحويل، هزينههاي نگهداري و تأخير از موعد تحويل، هزينههاي ديركرد را ميتواند ناشي شود.در اين تحقيق از نمادگذاري براي كلاسه بندي مسألههاي زمانبندي استفاده ميشود [16]. در اين نمادگذاري، αنمايندهء محيط ماشينها و نوع كارگاه بوده و شامل يك ورودي منفرد است. نماد βمشخصههاي كاري و محدوديتهاي زمانبندي را بيان ميكند كه ميتواند چندين ورودي داشته باشد و يا تهي باشد. نماد γنيز شامل تابع هدفي است كه ميبايست بهينه گردد كه عمدتاً يك ورودي منفرد دارد. در ادامه به تشريح مقادير ممكن هريك از نمادهاي مذكور ميپردازيم.1-2-2- محيط ماشينها و نوع كارگاهدر يك واحد صنعتي و يا به تعبيري كارگاه، تركيبهاي مختلف ماشينها اعم از نوع ماشينها و عملياتي كه ميتوانند انجام دهند، چگونگي انجام عمليات و نيز نحوهء چيدمان آنها منجر به ايجاد سيستمها مختلفي ميشود. درحقيقت مزيت چنين دستهبنديهايي اين است كه امكان تحليل بهتر براي محققين فراهم ميشود. پارامتر αكه پيشتر به آن اشاره شد، بيانگر اين دستهبندي بوده و مقاديري بشرح زير را ميتواند داشته باشد:تك ماشين[22] (1): در اين محيط تنها يك ماشين در سيستم وجود دارد. اين محيط حالت خاصي از تمامي محيطهاي پيچيدهء ديگر است.mماشين موازي يكسان[23] (Pm): mماشين كاملاً يكسان بصورت موازي در سيستم وجود دارند. هر كار iداراي يك عمليات است كه بايد تنها توسط يكي از اين ماشينها پردازش شود.mماشين موازي با سرعتهاي متفاوت[24] (Qm): mماشين با سرعتهاي متفاوت بصورت موازي در سيستم وجود دارند. با درنظرگرفتن پارامتر sjبعنوان سرعت ماشين j، زمان پردازش كار iدرصورت قرار گرفتن روي ماشين j(pij) از تقسيم pi/Sj حاصل ميشود.mماشين موازي نامرتبط[25] (Rm): mماشين بصورت موازي در سيستم وجود دارند كه هر يك از آنها كارهاي مختلف را با سرعتهاي متفاوتي انجام ميدهند. ماشين j كار iرا با سرعت sijپردازش ميكند.زمان پردازش كار iروي ماشين j (pij) برابر با pi/Sj خواهد بود.كار كارگاهي[26] m ماشينه (Jm): در كار كارگاهي با mماشين، هركار مسير از پيش تعيين شدهء خود را دارد كه ممكن است توسط برخي از ماشينها چندين بار پردازش شود و يا روي ماشيني هرگز قرار نگيرد.جريان كارگاهي[27] m ماشينه (Fm): در جريان كارگاهي با mماشين، ماشينها بصورت خطي و پشت سر هم قرار گرفتهاند و تمامي كارها از اولين تا آخرين ماشين مسير يكساني دارند.كارگاه باز[28]m ماشينه (Om): در كارگاه باز با mماشين، هر كار بايد دقيقاً يكبار توسط هر يك از ماشينها پردازش شود ولي ترتيب آنها دلخواه است.بمنظور سادگي، عبارتهاي فوق بهمراه نماد مربوطه در جدول (1-1) آمدهاست.جدول 1-1- مقادير پارامتر αمحيط ماشينهامقدار پارامتر αتك ماشين1mماشين موازي يكسانPmmماشين موازي با سرعتهاي متفاوتQmmماشين موازي نامرتبطRmكار كارگاهي m ماشينهJmجريان كارگاهي m ماشينهFmكارگاه باز m ماشينهOm يادآور ميشويم كه، در صورت عدم اشاره به mتعداد ماشينها در تمامي سيستمهاي فوق دلخواه خواهد بود. بدين معني كه بعنوان يك پارامتر ورودي تعيين ميشود.1-2-3- مشخصههاي كاري و محدوديتهاي زمانبنديمشخصههاي كاري و محدوديتهاي زمانبندي در هر يك از انواع كارگاهها شرايط خاصي را بوجود ميآورند. در برخي موارد ممكن است فضاي حل مسأله كوچكتر و رسيدن به بهينگي را در سيستم تسريع ببخشند و در مواردي نيز ميتوانند منجر به افزايش پيچيدگي محاسباتي مسألهها شوند. اين مشخصهها و محدوديتها كه توسط نماد βنشان داده ميشوند بقرار زيرند:بريدگي[29] (pmtn): پردازش كارها ميتواند قطع شده و بعداً روي ماشين ديگري ادامهء آن پردازش شود. درصورت مجاز بودن بريدگي، عبارت pmtnدر قسمت مربوط به نماد βنمايش داده ميشود.توقف ماشين با بريدگي[30] (r-a): ماشينها در زمانهايي قابل استفاده نبوده و كارها در صورت قطع شدن مجدداً از نقطهء قطع شده پردازش ميشوند.توقف ماشين بدون بريدگي[31] (nr-a): ماشينها در زمانهايي قابل استفاده نبوده و كارها در صورت قطع شدن از ابتدا پردازش ميشوند.توقف ماشين با بريدگيِ ناقص نوع 1[32] (sr1-a): ماشينها در زمانهايي قابل استفاده نبوده و در صورت قطع شدن كار، پردازش اضافهاي مازاد بر قسمت باقيماندهء كار بايد انجام شود.توقف ماشين با بريدگيِ ناقص نوع 2[33] (sr2-a): ماشينها در زمانهايي قابل استفاده نبوده و در صورت قطع شدن كار، فرآيند آمادهسازي تكرار و سپس باقيماندهء كار از نقطهء قطع شده پردازش ميشود.همچنين، در مواردي كه محدوديت عدم دسترسي ماشين ناشي از فرآيند نگهداري و تعميرات دورهاي[34] باشد از عبارت pmبجاي عبارت aاستفاده ميشود. بعنوان مثال، محدوديت توقف ناشي از نگهداري و تعميرات دورهاي بدون بريدگي با نماد nr-pmنمايش داده ميشود.عدم انتظار[35] (nwt): محدوديت عدم انتظار تنها براي جريان كارگاهي مطرح ميشود كه طبق آن كارها مجاز به انتظار بين دو ماشين متوالي نيستند. عدم نمايش عبارت nwtدر قسمت مربوط به βبيانگر مجاز بودن انتظار كارها بين دو ماشين متوالي خواهد بود.محدوديت تقدم[36] (prec): اين محدوديت بيان ميكند كه برخي كارها بايد قبل از برخي ديگر پردازش گردند. شكل عموميتر محدوديت تقدم بوسيلهء يك گراف بدون دور ارائه ميشود كه در آن هر گره نمايندهء يك كار و درصورت تقدم كار iبر كار k، يك كمان از iبه kوصل ميشود. اگر هر كار حداكثر يك پيشنياز و حداكثر يك پسنياز داشته باشد، محدوديت تقدم با عبارت chainsنشان داده ميشود. چنانچه هر كار حداكثر يك پسنياز داشته باشد، از عبارت intreeبعنوان محدوديت تقدم استفاده خواهد شد. اگر هر كار حداكثر يك پيشنياز داشته باشد، از عبارت outtreeبعنوان محدوديت تقدم استفاده ميشود. عدم اشاره به عبارت precو يا زير شاخههاي آن در قسمت مربوط به βنشاندهندهء عدم وجود محدوديت تقدم براي كارهاست.