عضو شوید
عضویت سریع
تبادل لینک هوشمند 
آمار مطالب
آمار بازدیدPlease enter banners and links.
3-3-1-2- جمعيت اوليه 303-3-1-3- تابع هدف 31
3-3-1-4- تابع برازندگي 31
3-3-1-5- انتخاب 31
3-3-1-6- تقاطع 31
3-3-1-7- جهش 33
3-3-1-8- معيار توقف 33
3-3-1-9- الگوريتم ژنتيك اوليه 33
3-3-1-10- الگوريتم ژنتيك موازي چند هدفه 34
3-3-2- الگوريتم شبيهسازي تبريد 35
3-3-2-1- الگوريتم شبيهسازي تبريد اوليه 35
3-3-2-2- الگوريتم شبيهسازي تبريد موازي چند هدفه 37
4- فصل چهارم: طراحي آزمايشات و ارزيابي محاسباتي 38
4-1- مقدمه 39
4-2- طراحي آزمايشات تاگوچي 39
4-2-1- توليد دادهها 40
4-2-2- تنظيم پارامترهاي الگوريتم MOPGA 40
4-2-3- تنظيم پارامترهاي الگوريتم MOPSA 42
4-3- ارزيابي محاسباتي 43
5- فصل پنجم: جمعبندي و مطالعات آتي 45
5-1- جمعبندي 46
5-2- مطالعات آتي 46
مراجع 48
فهرست جداول
عنوان صفحه
1-1- مقادير پارامتر α5
1-2- مقادير پارامتر β 7
1-3- مقادير پارامتر γ8
3-1- تعداد متغيرها 29
3-2- تعداد محدوديتها 29
3-3- تعداد متغيرها و محدوديتها مطابق با مدل MOMILP29
4-1 فاكتورهاي الگوريتم MOPGA و سطوح آنها 41
4-2- آزمايشات مربوط به آرايهء L9 در الگوريتم MOPGA 41
4-3- جدول تحليل واريانس كسر S/N مربوط به فاكتورهاي الگوريتم MOPGA 42
4-4- فاكتورهاي الگوريتم MOPSA و سطوح آنها 42
4-5- آزمايشات مربوط به آرايهء L4 در الگوريتم MOPSA 42
4-6- جدول تحليل واريانس كسر S/N مربوط به فاكتورهاي الگوريتم MOPSA 43
4-7- عملكرد مدل MOMILP و الگوريتمهاي GA و SA اوليه در برخورد با مسألههاي با ابعاد كوچك 44
4-8- ميانگين RPD براي الگوريتمهاي MOPGA و MOPSA در حل مسألههاي با ابعاد بزرگ 44
فهرست شكلها
عنوان صفحه
1-1- رابطهء جايگزيني بين دو هدف γ1 و γ210
3-1- توالي كارها روي يك ماشين j 25
3-2- نمودار گانت مربوط به حل بهينهء مثال 28
3-3- نحوهء تقسيمبندي جمعيت و عملكرد موازي زير-جمعيتها 34
3-4- جستجوي همسايگي الگوريتم شبيهسازي تبريد 36
3-5- قدمهاي الگوريتم شبيهسازي تبريد اوليه 36
4-1- نمودار كسر S/N مربوط به RPD در فاكتورهاي الگوريتم MOPGA 41
4-2- نمودار كسر S/N مربوط به RPD در فاكتورهاي الگوريتم MOPSA 43
فصل اول
معرفي و كليات تحقيق
مقدمه
از مهمترين شرطهاي ارتقاي وضعيت فعلي در هر سازمان ميتوان به استفادهء مناسب از سرمايهها و جلوگيري از هدر رفت آنها اشاره كرد. منظور از ” استفادهء مناسب ” در اينجا مفهومِ واژهء كارايي يعني سرعت عمل در استفاده از ظرفيت است كه بدون داشتن برنامهء از پيش تعيين شده ممكن نيست. افزون بر آن، هرچه دقت در برنامه بيشتر و مطالعه مكفيتر باشد سرعت عمل بيشتر شده و توان رقابتي بالاتر ميرود. وقتي صحبت از سرمايههاي يك سازمان به ميان ميآيد ممكن است ذهنها به سمت سرمايههاي فيزيكي مثل ماشينآلات و دستگاههاي گرانقيمت منحرف شود. حال آنكه، مفهوم مورد انتظار ما بطور خاص “زمان” است. استفادهء مناسب از زمان بعنوان يك سرمايه و جلوگيري از هدر رفت آن از جمله ابزارهاي مهم مديرانِ سازمانها در عرصههاي رقابتي است. زمان را ميتوان منبعي دانست كه بايد بطور صحيح تقسيمبندي و مديريت شده و با برنامهء خاص به فعاليتها تخصيص داده شود و اين همان چيزيست كه به آن زمانبندي اطلاق ميشود.
زمانبندي شامل تخصيص منابع محدود به فعاليتهاست با هدف بهينهسازي يك يا چند معيار اندازهگيري [1]. از طرفي، ماهيت برخي منابع همچون ماشينآلات و نيروي انساني بگونهاي است كه قادر به انجام همزمان بيش از يك فعاليت نيستند. بنابراين، تعريف ديگري براي زمانبندي به اين شرح ارائه ميشود: زمانبندي، يافتن توالي مناسب انجام فعاليتها توسط ماشينها و يا نيروي انساني است بنحوي كه يك يا چند معيار اندازهگيري بهينه شوند. براي تحليل سيستم زمانبنديِ توليدِ جاري و يافتن راههاي بهبود آن، آگاهي از روشهاي زمانبندي توليد بسيار مهم است. دو مسألهء كليدي در زمانبنديِ توليد اولويت و ظرفيت هستند [2]. بعبارت ديگر، “چه كاري بايد ابتدا انجام شود؟” و “چه كسي بايد آن را انجام دهد؟” وايت [2] زمانبندي را اينگونه تعريف ميكند: “تعيين زمان براي انجام يك فعاليت”. او همچنين، در يك شركت توليدي زمانبنديِ تفصيلي در سطح يك كارگاه را درنظر ميگيرد. يعني، زمانبندي كه در آن زمان شروع و پايان هر عمليات معلوم است. كوكس و همكاران [3] زمانبندي تفصيلي را اينگونه تعريف ميكنند: “تخصيص واقعي زمان شروع و يا پايان فعاليتها يا گروهي از فعاليتها بنحوي كه سفارش توليد در موعد مقرر تكميل شود.” آنها همچنين از زمانبندي عمليات، زمانبندي سفارش و زمانبندي كارگاه بطور معادل ياد ميكنند.
تعابير متنوعي از تعريفهاي ارائه شده براي زمانبندي در محيط هاي مختلف قابل تصور است. بعنوان مثال، منابع ميتوانند ماشينها در يك كارگاه، پردازنده و حافظه در يك سيستم كامپيوتري، باندهاي فرود در يك فرودگاه، تعميركاران در يك تعميرگاه خودرو و غيره باشند. همچنين، فعاليتها ميتوانند شامل عمليات مختلف در يك فرآيند ساخت، اجراي يك برنامهء كامپيوتري، نشستن و برخاستن هواپيماها در فرودگاه، تعمير خودروهاي تعميرگاه و مواردي از اين دست باشند.
مطالعه بر روي زمانبندي به دههء 1950 برميگردد كه محققان در پژوهش عملياتي، مهندسي صنايع و مديريت با مسألهء اداره كردن فعاليتهاي مختلفي كه در يك كارگاه رخ ميدادند مواجه بودند. در آن زمان، الگوريتمهاي زمانبندي خوب ميتوانستند هزينهء توليد را در فرآيند ساخت كاهش داده و توان رغابتي شركتها را بالا ببرند. در اواخر دههء 1960، دانشمندان كامپيوتر نيز با مسألهء زمانبندي در توسعه سيستمهاي عملياتي روبرو شدند. چراكه، در آن روزها منابع محاسباتي همچون پردازشگرها و حافظهها محدود بودند و بهرهبرداري مؤثر از اين منابع محدود ميتوانست هزينهء اجراي برنامههاي كامپيوتري را كاهش دهد. بنابراين، مطالعه بر روي زمانبندي توجيه اقتصادي پيدا كرد [4].
مسألههاي زمانبندي در دههء 1950 بسيار ساده بودند و تعدادي الگوريتمهاي كارا براي رسيدن به جواب بهينه توسعه يافتند كه كارهاي جكسون [5،6]، جانسون [7] و اسميت [8] از مهمترين آنها هستند. با گذشت زمان، مسألهها پيچيدهتر شده و ديگر محققان قادر به توسعه الگوريتمهاي كارا براي آنها نبودند. بيشتر محققان تلاش كردند روشهاي شاخه و كران را كه عمدتاً الگوريتمهايي با زمان نمايي بودند را گسترش دهند. با ظهور تئوري پيچيدگي [11-9]، محققان دريافتند كه بسياري از اين مسألهها ذاتاً براي حل سخت هستند. در دههء 1970 نشان داده شد كه بيشتر مسألههاي زمانبندي NP-hard هستند [15-12] يعني زمان حل آنها شديداً غير چندجملهاي است. در دههء 1980، چندين زمينهء مختلف در دانشگاه و صنعت مورد بررسي قرار گرفت. يكي از اين زمينهها توسعه و تحليل الگوريتمهاي تقريبي و ديگري افزايش توجه به مسألههاي زمانبندي اتفاقي بود. از آن پس، تحقيق در زمينهء تئوري زمانبندي با فراز و نشيبهايي همراه بودهاست. بعد از گذشت بيش از 60 سال، هنوز ابهاماتي در اين شاخه از علم وجود دارد.
تعاريف زمانبندي
هر چند كه مفهوم زمانبندي بسيار فراگير بوده و كاربردهاي متنوعي در محيطهاي مختلف براي آن قابل تصور است ولي ما از رويكرد سيستمهاي توليدي و صنعتي جهت بسط و گسترش آن استفاده ميكنيم. پيش از آن كه بخواهيم درمورد زمانبندي تخصصيتر صحبت كنيم، لازم است نمادها و عبارتهاي مصطلح در اين زمينه معرفي شوند. اين بخش به معرفي برخي از آنها پرداخته و پس از توضيح چند نماد و تشريح محيط مورد نظر و شرايط آن، هدفها و معيارهاي زمانبندي بيان ميشوند.
1-2-1- نمادها
در زير به برخي پارامترها و نمادهايي كه در طول اين تحقيق استفاده ميشوند اشاره ميكنيم.
تعداد كارها n و تعداد ماشينها m درنظر گرفته ميشود. زير نويسهاي i و k به كار و زيرنويسهاي j و h به ماشين اشاره دارند. بدينترتيب، اصطلاحات زير مربوط به كار i هستند:
زمان پردازش (pij): مدت زمان پردازش كار i توسط ماشين j است كه در صورت عدم استفاده از ماشين j در فرآيند تكميل كار i ، اين مقدار صفر درنظر گرفته ميشود و چنانچه قرار باشد كار i تنها توسط يكي از m ماشين (هركدام) پردازش شود زير نويس j حذف ميشود.
زمان آمادهسازي (Sij): زمان آمادهسازي كار i روي ماشين j مدت زماني است كه طول ميكشد تا كار روي ماشين قرار گرفته، تثبيت شده و آمادهء پردازش شود. عمليات پردازش بلافاصله پس از اتمام آمادهسازي شروع ميشود.
زمان جداسازي (Rij): زمان جداسازي كار i از روي ماشين j مدت زماني است كه طول ميكشد تا كار پس از تكميل پردازش از روي ماشين برداشته شود. اين زمان بدليل جدا كردن ابزار تثبيت از قطعه درنظر گرفته ميشود. اتمام زمان جداسازي بمنزله اتمام كار است.
زمان آماده به كار بودن (ri): نقطهاي از زمان كه كار i به سيستم وارد ميشود و در حقيقت زودترين زماني است كه ميتوان شروع به پردازش كار i نمود.
موعد تحويل (di): نقطهاي از زمان كه طبق قرار قبلي با مشتري بايد كار i تحويل شود. باتوجه به تعريف مذكور، تكميل كار زودتر از موعد تحويل، هزينههاي نگهداري و تأخير از موعد تحويل، هزينههاي ديركرد را ميتواند ناشي شود.
در اين تحقيق از نمادگذاري α/β/γ براي كلاسه بندي مسألههاي زمانبندي استفاده ميشود [16]. در اين نمادگذاري، α نمايندهء محيط ماشينها و نوع كارگاه بوده و شامل يك ورودي منفرد است. نماد β مشخصههاي كاري و محدوديتهاي زمانبندي را بيان ميكند كه ميتواند چندين ورودي داشته باشد و يا تهي باشد. نماد γ نيز شامل تابع هدفي است كه ميبايست بهينه گردد كه عمدتاً يك ورودي منفرد دارد. در ادامه به تشريح مقادير ممكن هريك از نمادهاي مذكور ميپردازيم.
1-2-2- محيط ماشينها و نوع كارگاه
در يك واحد صنعتي و يا به تعبيري كارگاه، تركيبهاي مختلف ماشينها اعم از نوع ماشينها و عملياتي كه ميتوانند انجام دهند، چگونگي انجام عمليات و نيز نحوهء چيدمان آنها منجر به ايجاد سيستمها مختلفي ميشود. درحقيقت مزيت چنين دستهبنديهايي اين است كه امكان تحليل بهتر براي محققين فراهم ميشود. پارامتر α كه پيشتر به آن اشاره شد، بيانگر اين دستهبندي بوده و مقاديري بشرح زير را ميتواند داشته باشد:
تك ماشين (1): در اين محيط تنها يك ماشين در سيستم وجود دارد. اين محيط حالت خاصي از تمامي محيطهاي پيچيدهء ديگر است.
m ماشين موازي يكسان (Pm): m ماشين كاملاً يكسان بصورت موازي در سيستم وجود دارند. هر كار i داراي يك عمليات است كه بايد تنها توسط يكي از اين ماشينها پردازش شود.
m ماشين موازي با سرعتهاي متفاوت (Qm): m ماشين با سرعتهاي متفاوت بصورت موازي در سيستم وجود دارند. با درنظرگرفتن پارامتر sj بعنوان سرعت ماشين j ، زمان پردازش كار i درصورت قرار گرفتن روي ماشين j (pij) از تقسيم pi/Sj حاصل ميشود.
m ماشين موازي نامرتبط (Rm): m ماشين بصورت موازي در سيستم وجود دارند كه هر يك از آنها كارهاي مختلف را با سرعتهاي متفاوتي انجام ميدهند. ماشين j كار i را با سرعت sij پردازش ميكند. زمان پردازش كار i روي ماشين j (pij) برابر با pi/Sj خواهد بود.
كار كارگاهي m ماشينه (Jm): در كار كارگاهي با m ماشين، هركار مسير از پيش تعيين شدهء خود را دارد كه ممكن است توسط برخي از ماشينها چندين بار پردازش شود و يا روي ماشيني هرگز قرار نگيرد.
جريان كارگاهي m ماشينه (Fm): در جريان كارگاهي با m ماشين، ماشينها بصورت خطي و پشت سر هم قرار گرفتهاند و تمامي كارها از اولين تا آخرين ماشين مسير يكساني دارند.
كارگاه باز m ماشينه (Om): در كارگاه باز با m ماشين، هر كار بايد دقيقاً يكبار توسط هر يك از ماشينها پردازش شود ولي ترتيب آنها دلخواه است.
بمنظور سادگي، عبارتهاي فوق بهمراه نماد مربوطه در جدول (1-1) آمدهاست.
جدول 1-1- مقادير پارامتر α
محيط ماشينها مقدار پارامتر α
تك ماشين 1
m ماشين موازي يكسان Pm
m ماشين موازي با سرعتهاي متفاوت Qm
m ماشين موازي نامرتبط Rm
كار كارگاهي m ماشينه Jm
جريان كارگاهي m ماشينه Fm
كارگاه باز m ماشينه Om
يادآور ميشويم كه، در صورت عدم اشاره به m تعداد ماشينها در تمامي سيستمهاي فوق دلخواه خواهد بود. بدين معني كه بعنوان يك پارامتر ورودي تعيين ميشود.
1-2-3- مشخصههاي كاري و محدوديتهاي زمانبندي
مشخصههاي كاري و محدوديتهاي زمانبندي در هر يك از انواع كارگاهها شرايط خاصي را بوجود ميآورند. در برخي موارد ممكن است فضاي حل مسأله كوچكتر و رسيدن به بهينگي را در سيستم تسريع ببخشند و در مواردي نيز ميتوانند منجر به افزايش پيچيدگي محاسباتي مسألهها شوند. اين مشخصهها و محدوديتها كه توسط نماد β نشان داده ميشوند بقرار زيرند:
بريدگي (pmtn): پردازش كارها ميتواند قطع شده و بعداً روي ماشين ديگري ادامهء آن پردازش شود. درصورت مجاز بودن بريدگي، عبارت pmtn در قسمت مربوط به نماد β نمايش داده ميشود.
توقف ماشين با بريدگي (r-a): ماشينها در زمانهايي قابل استفاده نبوده و كارها در صورت قطع شدن مجدداً از نقطهء قطع شده پردازش ميشوند.
توقف ماشين بدون بريدگي (nr-a): ماشينها در زمانهايي قابل استفاده نبوده و كارها در صورت قطع شدن از ابتدا پردازش ميشوند.
توقف ماشين با بريدگيِ ناقص نوع 1 (sr1-a): ماشينها در زمانهايي قابل استفاده نبوده و در صورت قطع شدن كار، پردازش اضافهاي مازاد بر قسمت باقيماندهء كار بايد انجام شود.
توقف ماشين با بريدگيِ ناقص نوع 2 (sr2-a): ماشينها در زمانهايي قابل استفاده نبوده و در صورت قطع شدن كار، فرآيند آمادهسازي تكرار و سپس باقيماندهء كار از نقطهء قطع شده پردازش ميشود.
همچنين، در مواردي كه محدوديت عدم دسترسي ماشين ناشي از فرآيند نگهداري و تعميرات دورهاي باشد از عبارت pm بجاي عبارت a استفاده ميشود. بعنوان مثال، محدوديت توقف ناشي از نگهداري و تعميرات دورهاي بدون بريدگي با نماد nr-pm نمايش داده ميشود.
عدم انتظار (nwt): محدوديت عدم انتظار تنها براي جريان كارگاهي مطرح ميشود كه طبق آن كارها مجاز به انتظار بين دو ماشين متوالي نيستند. عدم نمايش عبارت nwt در قسمت مربوط به β بيانگر مجاز بودن انتظار كارها بين دو ماشين متوالي خواهد بود.
محدوديت تقدم (prec): اين محدوديت بيان ميكند كه برخي كارها بايد قبل از برخي ديگر پردازش گردند. شكل عموميتر محدوديت تقدم بوسيلهء يك گراف بدون دور ارائه ميشود كه در آن هر گره نمايندهء يك كار و درصورت تقدم كار i بر كار k، يك كمان از i به k وصل ميشود. اگر هر كار حداكثر يك پيشنياز و حداكثر يك پسنياز داشته باشد، محدوديت تقدم با عبارت chains نشان داده ميشود. چنانچه هر كار حداكثر يك پسنياز داشته باشد، از عبارت intree بعنوان محدوديت تقدم استفاده خواهد شد. اگر هر كار حداكثر يك پيشنياز داشته باشد، از عبارت outtree بعنوان محدوديت تقدم استفاده ميشود. عدم اشاره به عبارت prec و يا زير شاخههاي آن در قسمت مربوط به β نشاندهندهء عدم وجود محدوديت تقدم براي كارهاست.
زمان آماده به كار بودن (ri): همانگونه كه قبلاً نيز به آن اشاره شد، زمان آماده به كار بودن كار i ، زودترين زماني است كه كار i ميتواند شروع به پردازش شود. عدم اشاره به اين نماد، يعني پردازش كار i در هر زماني امكانپذير است. بعبارت ديگر، همهء كارها در ابتداي افق برنامهريزي در دست و قابل پردازش هستند (ri=0;∀i).
محدوديت تعداد كارها (nbr): اشاره به اين نماد بيانگر آنست كه تعداد كارها محدود است. بعنوان مثال، nbr=5 يعني حداكثر 5 كار براي پردازش وجود دارد. همچنين، ننوشتن اين نماد يعني چنين محدوديتي وجود نداشته و تعداد كارها بعنوان پارامتر n از ورودي دريافت ميشود.
محدوديت تعداد عمليات كارها (ni): كاربرد اين نماد تنها در محيط كار كارگاهي مطرح ميشود و همانگونه كه از نام آن پيداست بيانگر محدود بودن تعداد عمليات هر كار i است. بعنوان مثال ni=4 يعني حداكثر تعداد فعاليتهاي هر كار محدود به 4 فعاليت است و بطور واضح، اشاره نكردن به آن نشان از نامحدود بودن تعداد فعاليتهاي هر كار است.
محدوديت زمانهاي پردازش (pi): اگر اين نماد نوشته شود يعني زمان پردازش هر كار محدود است. بعنوان مثال، pi=p يعني زمان پردازش هر كار p واحد است. عدم اشاره به نماد مذكور نيز نامحدود بودن زمان پردازش را نشان ميدهد.
آخرين مهلت (di): چنانچه اين نماد نوشته شود، هر كار i بايد تا قبل از موعد di تكميل شود. عدم نوشتن نماد مذكور نيز نبودن چنين محدوديتي را بيان ميكند.
مقادير مربوط به پارامتر β بطور خلاصه در جدول (1-2) آمدهاند.
جدول 1-2- مقادير مربوط به پارامتر β
محدوديت مقدار پارامتر β
بريدگي pmtn
توقف ماشين با بريدگي r-a
توقف ماشين بدون بريدگي nr-a
توقف ماشين با بريدگيِ ناقص نوع 1 sr1-a
توقف ماشين با بريدگيِ ناقص نوع 2 sr2-a
توقف ناشي از نگهداري و تعميرات دورهاي بدون بريدگي nr-pm
عدم انتظار nwt
محدوديت تقدم prec
محدوديت تقدم با حداكثر يك پيشنياز و حداكثر يك پسنياز براي هر كار chains
محدوديت تقدم با حداكثر يك پسنياز براي هر كار intree
محدوديت تقدم با حداكثر يك پيشنياز براي هر كار outtree
زمان آماده به كار بودن ri
محدوديت تعداد كارها nbr
محدوديت تعداد عمليات كارها ni
محدوديت زمانهاي پردازش pi
آخرين مهلت di1-2-4- معيارهاي بهينهسازي
همانگونه كه در ابتداي اين فصل و در تعاريف زمانبندي گفته شد، در زمانبندي و اصولاً هر برنامهريزي ديگري يك و يا چند هدف و مقصود وجود دارند كه بايد بهينه شوند. دستهبنديهاي مختلفي براي هدفها و معيارها در مسألههاي زمانبندي تعريف شدهاست. بعنوان مثال در يك دستهبندي، معيارهاي زمانبندي را به دو گروه توليدكنندهگرا و مشتريگرا تقسيم ميكنند. معيارهاي توليدكنندهگرا بنحوي با زمان تكميل كارها و معيارهاي مشتريگرا بطور توأم با زمان تكميل كارها و موعد تحويل مرتبط هستند. بهرحال، معياري كه بايد كمينه گردد هميشه تابعي از زمان تكميل كارهاست. Ci را زمان تكميل كار i در يك زمانبندي در نظر بگيريد. دراينصورت، ديركرد كار i بشكل زير محاسبه ميگردد:
Li=Ci-diو بدنبال آن تأخير كار i از رابطهء زير بدست ميآيد:
Ti=maxLi,0همچنين، زودكرد كار i از رابطهء زير بدست ميآيد:
Ei=maxi-Li,0واحد جريمه كار i بدينصورت محاسبه ميشود كه: اگرCi>di آنگاه Ui=1؛ درغيراينصورتUi=0.
با استفاده از تعاريف فوق، برخي توابع هدف كمينهسازي بشرح زير هستند:
طولانيترين زمان تكميل (Cmax): روش محاسبه بيشترين زمان تكميل به اينصورت است Cmax=maxiCi.
طولانيترين ديركرد (Lmax): روش محاسبه بيشترين ديركرد به اينصورت است Lmax=maxiLi.
جمع وزني زمان تكميل (wiCi): جمع وزني زمان تكميل بصورت i=1nwiCi و جمع غيروزني زمان تكميل بصورت i=1nCi محاسبه ميشود.
جمع وزني تأخير (wiTi): جمع وزني تأخير بصورت i=1nwiTi و جمع غيروزني تأخير بصورت i=1nTi محاسبه ميشود.
تعداد وزني كارهاي تأخيردار (wiUi): تعداد وزني كارهاي تأخيردار بصورت i=1nwiUi و تعداد غير وزني كارهاي تأخيردار بصورت i=1nUi محاسبه ميشود.
همچنين، جدول (1-3) مقادير پارامتر γ مربوط به معيارهاي بهينهسازي را نشان ميدهد.
جدول 1-3- مقادير پارامتر γمعيار بهينهسازي مقدار پارامتر γ
طولانيترين زمان تكميل Cmaxطولانيترين ديركرد Lmaxجمع وزني زمان تكميل wiCiجمع غيروزني زمان تكميل i=1nCiجمع وزني تأخير wiTiجمع غيروزني تأخير i=1nTiتعداد وزني كارهاي تأخيردار wiUiتعداد غير وزني كارهاي تأخيردار i=1nUiنظريهء زمانبندي
پس از معرفي انواع محيطها و كارگاههاي زمانبندي و تشريح محدوديتهاي مختلف، بدنبال راهي براي دركنترل گرفتن چنين محيطهايي هستيم بنحوي كه معيار و يا معيارهاي مورد نظر به مقدار بهينهء خود برسند. در حقيقت علت اصلي معرفي نمادها كه عموماً جنبهء رياضياتي داشتند همين امر بود. نظريهء زمانبندي اصولاً با مدلهاي رياضي سروكار دارد و بين كار زمانبندي و توسعهء مدلهاي زمانبندي رابطه برقرار ميكند و بطور پيوسته آنها را با مسألههاي نظري و عملي زمانبندي محك ميزند. ديدگاه نظري بطور غالب رويكردي كمي است و سعي آن دست يافتن به ساختار مسأله در قالب شكل فشرده رياضي است. بويژه، اين رويكرد كمي با تفسير اهداف تصميمگيري در قالب يك تابع هدف صريح و بيان موانع تصميمگيري بصورت محدوديتهاي صريح روشن ميشود. از تهيهء مدلهاي رياضي براي مسألههاي زمانبندي بدنبال تصميمگيري دو موردِ تخصيص منابع و توالي عمليات هستيم [17].
برنامهريزي رياضي
بهينهسازي يا برنامهريزي رياضي، شاخهاي از رياضيات است كه با روشهايي به بهينه كردن يك (يا چند) تابع هدف مشتمل بر تعدادي متغير، با توجه به قيود مشخص روي اين متغيرها، ميپردازد. كاربرد مسألهها و نيز روشهاي بهينهسازي هماكنون بطور وسيعي گسترش يافتهاست. پيش از ظهور كامپيوترهاي رقمي، تنها مدلهاي بسيار سادهء بهينهسازي كه شامل تعداد كمي متغير و قيد بودند، با وسايل دردسترس آن زمانها حل ميشدند. به همين دليل، در آن دوره بيشتر تأكيد روي مدلهاي خيلي كوچك و فشرده ميشد زيرا درغيراينصورت قابل حل نبودند. در 50 سال اخير الگوريتمهاي بيشماري جهت حل مسألههاي بزرگ بهينهسازي توسعه يافتهاند و كامپيوترهاي رقمي قوي براي پيادهسازي و اجراي اين الگوريتمها دردسترس محققان قرار گرفتهاند. اين امر موجب كارآمدي بيشتر گونههاي مختلف مدلهاي بهينهسازي و امكان حل مدلهايي با ابعاد بزرگتر شدهاست.
نكتهاي كه در ساختار مدلهاي بهينهسازي تأكيد زيادي بر آن ميشود، قابل محاسبه بودن و قابل كنترل بودن مدل است. يكي از اين مدلها، مدل برنامهريزي رياضي خطي است. در مدل برنامهريزي رياضي خطي، بدنبال بهينه نمودن يك تابع هدف خطي با توجه به قيودي خطي كه بصورت معادله و يا نامعادله هستند و نيز قيود علامتي كه روي متغيرها قرار دارد هستيم. همچنين، قيود علامت ممكن است بصورت كران بالا و يا پايين باشند. امروزه، الگوريتمهاي بسيار كارآمدي براي حل مدلهاي برنامهريزي خطي توسعه يافتهاند و نرمافزارها با كيفيت بالا و هزينهء پايين در اختيار محققان است. مسألههاي برنامهريزي خطي با مقياس بزرگ شامل چندين هزار قيد و چندين هزار متغير توسط الگوريتمها و نرمافزارهاي جديد با هزينهء كم و در زمان قابل قبول به بهينگي ميرسند.
هرچند كه روشهاي مطلوبي جهت حل مسألههايي كه بصورت برنامهريزي خطي مدل ميشوند وجود دارد ولي تبديل مسأله و رسيدن به مدل خطي پيچيدگيهاي خاص خود را دارد بطوريكه از مدلسازي و فرموله كردن يك مسألهء دنياي واقعي بصورت برنامهريزي خطي بعنوان يك هنر ياد ميكنند [18].
زمانبندي چند هدفه
در اين بخش از تحقيق، به تحليل پارامتري مسألههاي چند هدفه و بطور خاص دو هدفه ميپردازيم. هريك از دو (و يا چند) هدف مورد نظر با اهميتهاي اختياري و بطور همزمان مورد بررسي قرار ميگيرند. مسألهء زمانبندي چند هدفه يكي از موضوعات اصلي تحقيق در زمينهء برنامهريزي چند هدفه را تشكيل ميدهد. رويههاي مختلفي براي برخورد با چنين مسائلي كه در آنها چند هدف ناسازگار بايد بطور همزمان بهينه شوند توسعه داده شده است. يكي از رايجترين دستاوردهايي كه در ادبيات مورد توجه قرار گرفته، استفاده از وزنهاي ثابت است. در اين روش، يك مسألهء چند هدفه از طريق تركيب خطي هدفها و وزنها به يك مسألهء تك هدفه تبديل ميشود. تابع هدف كلي، بصورت كمينهسازي مجموع وزني دو (و يا چند) هدف موردنظر نوشته ميشود. نارسايي عمدهء اين تبديل آنست كه وزن هر هدف بايد بشكل معقول و صحيحي تعيين شود حال آنكه درصورت ناكافي بودن تجربهء تصميم گيرنده، اين تبديل منجر به ايجاد اختلاف زيادي بين جواب بدست آمده و جواب واقعي خواهد شد. وزنها ميتوانند به زمان و يا شرايط ديگري بستگي داشته باشند. بطور معمول، امكان تعيين مقدار دقيقي براي اين وزنها توسط فردي كه زمانبندي را انجام ميدهد وجود ندارد و انجام يك تحليل پارامتري جهت يافتن روابط جايگزيني مطلوب بنظر ميرسد. ايدهء ديگري براي حل مسألههاي چند هدفه وجود دارد كه طبق آن وزنها از پيش تعيين شده نيستند. اين روش جوابهاي مختلفي را براي انتخاب پيش روي تصميمگيرنده قرار ميدهد. جوابهاي جستجو شده، جوابهاي بهينهء پارتو نام دارند.
تعريف 1-5-1- (زمانبندي بهينهء پارتو): يك زمانبندي، بهينهء پارتو گفته ميشود اگر امكان كاهش مقدار يكي از هدفها بدون افزايش مقدار ديگري وجود نداشته باشد.
فرد زمانبند ميخواهد بداند يافتن يك برنامهء زمانبندي با درنظر گرفتن يكي از هدفها چه تأثيري روي هدف ديگر ميگذارد. وقتي چندين هدف داشته باشيم مبحث بهينگي پارتو مطرح ميشود. درچنين شرايطي، فرد زمانبند مايل است قبل از تصميمگيري، مجموعهء برنامههاي زمانبندي بهينهء پارتو را مشاهده كند. بنابراين، همواره سيستمي بايد برنامههاي زمانبندي چندگانه را در حافظه داشته باشد.
تعداد جوابهاي بهينهء پارتو اغلب يكي نبوده و تصميمگيرندهها ميتوانند يكي از آنها را با توجه به برآورده شدن مطلوبيتشان انتخاب نمايند. اين روش انعطاف بيشتري نسبت به روشي كه در آن وزنها ثابت بود دارد. دو هدف γ1 و γ2 را درنظر بگيريد. اگر تابع هدف كلي بصورتθ1γ1+θ2γ2 باشد، كه در آن θ1 و θ2 وزنهاي اهداف هستند، آنگاه مسألهء زمانبندي را بصورت α/β/θ1γ1+θ2γ2نمايش ميدهيم. از آنجايي كه ضرب كردن وزنهاي يكسان مسأله را تغيير نميدهد، وزنها را طوري درنظر ميگيريم كه جمع آنها برابر 1 شود. يعني، θ1+θ2=1.
تمامي جوابهاي بهينهء پارتو را ميتوان بصورت مجموعهاي از نقاط در صفحهء (γ1,γ2) نمايش داد. اين مجموعه نقاط، جايگزيني بين دو هدف را نشان ميدهند. با ميل كردن θ1 بسمت 1 (θ1→1)، γ1 به مقدار بهينهء خود ميرسد و برعكس با ميل كردن θ2 بسمت 1 (θ2→1)، γ2 به مقدار بهينهء خود ميرسد. بنابراين، همانگونه كه در نمودار جايگزيني شكل (1-1) پيداست نقاط انتهايي، هريك نشاندهندهء بهينگيِ يكي از هدفهاست [19].
شكل 1-1- رابطهء جايگزيني بين دو هدف γ1 و γ2الگوريتمهاي فرا ابتكاري در بهينهسازي
مسألههاي دنياي واقعي داراي ذات تركيباتيِ پيچيدهاي هستند كه طبق دستهبندي تئوري پيچيدگي اغلب در دستهء مسألههاي چندجملهاي قرار نميگيرند. اين مسألهها در اندازههاي كاربردي و عملي خود به قدري بزرگ هستند كه نميتوان جواب بهينهء آنها را در مدت زمان قابل پذيرش بدست آورد. با اين وجود، لزوم حل چنين مسألههايي تصميمگيرندگان را برآن ميدارد كه به جوابهاي زير-بهينه كه كيفيت مناسبي داشته و در زمان قابل قبولي بدست ميآيند بسنده كنند.رويكردهاي متفاوتي براي رسيدن به جوابهاي زير-بهينه وجود دارد. يكي از اين رويكردها الگوريتمهاي تقريبي هستند كه يافتن جوابي در يك فاصلهء مشخص از جواب بهينه را تضمين ميكنند. رويكرد ديگر الگوريتمهاي احتمالي هستند كه توليد جواب نزديك به بهينه را با احتمال بالايي تضمين ميكنند. گذشته از آن، دستهاي از الگوريتمها معرفي شدهاند كه هيچگونه تضميني در ارائه جواب مناسب ندارند ولي نتايج حاكي از كاراييِ بالاي آنها در دستيابي به جوابهاي مطلوب در زمان مناسب است [20]. الگوريتمهاي مذكور، الگوريتمهاي فرا ابتكاري نام دارند. از جملهء اين الگوريتمها ميتوان به موارد زير اشاره نمود:
الگوريتم ژنتيك
شبيهسازي تبريد
شبكهء عصبي
جستجوي ممنوع
بهينهسازي جمعيت مورچگان
1-6-1- الگوريتم ژنتيك
الگوريتم ژنتيك (GA) كه ايدهء اصلي آن از نظريهء تكاملي داروين (1859) گرفته شده، يك روش جستجوي تصادفيِ هدايت شده است. داروين در نظريهء تكاملي خود بيان ميكند: آن دسته از صفات طبيعي كه با قوانين طبيعي سازگاري بيشتري دارند، شانس بقاي بيشتري دارند. به بيان ديگر، نسلهاي جديد كه بر اثر جفتگيري و زادوولد بوجود ميآيند به سمت سازگاري بيشتر با طبيعت پيرامون و به تعبير داروين، به سمت تكامل پيش ميروند. هرچند كه اثبات تحليلي و قطعي براي اين نظريه وجود ندارد ولي از نظر تجربي و آماري مورد تأييد قرار گرفته است. اين سازگاريِ بيشتر و بهبود صفات در حقيقت به نوع تركيب ژنها و تشكيل كروموزمهاي جديدِ بهتر مربوط ميشود. الگوريتم ژنتيك كه توسط هولاند، ديجونگ و گلدبرگ در سال 1970 مطرح شد از همين تركيب ژنها و ساختار كروموزومها الهام ميگيرد. اين الگوريتم قادر به جستجوي مؤثر در فضاي بسيار وسيع و جهتگيري به سمت جواب بهينه است. در GA، فضاي حل مسأله به فضاي ژنتيك تبديل ميشود و در هر مرحله (نسل) از الگوريتم با مجموعهاي از كروموزومها كه همان جوابهاي كد شده هستند سروكار داريم. كروموزومها طبق فرآيند خاصي بصورت جفت جفت انتخاب شده و با استفاده از عملگرهاي ژنتيك (شامل اپراتورهاي تقاطع و جهش) با هم تركيب شده و جوابهاي جديد توليد ميشوند. بمنظور كنترل ميزان مطلوبيت جوابهاي توليد شده تابعي تحت عنوان تابع برازندگي متناسب با تابع هدف مسأله تعريف ميشود. بدين ترتيب جوابهاي مناسب با احتمال بالا ذخيره و به مرحله (نسل) بعد منتقل ميشوند. استفاده از فرآيند احتمالي براي انتخاب جوابهاي مناسب موجب حفظ پراكندگي در جستجوي فضاي حل شده و از هدايت الگوريتم به سمت بهينهء محلي جلوگيري ميكند. درنهايت با برقراري شرط توقفي كه از قبل براي الگوريتم تعريف شده، الگوريتم متوقف و جواب نهايي استخراج و رمزگشايي ميشود.
1-6-2- الگوريتم شبيهسازي تبريد
يكي ديگر از الگوريتمهاي فرا ابتكاري الگوريتم شبيهسازي تبريد است كه استفاده از آن بعنوان يك تكنيك بهينهسازي در اوايل دههء 1980 گسترش يافت. ايدهء اصلي شبيهسازي تبريد از آنجا ميآيد كه در فرآيند سردسازي (تبريد)، فاصلهء بين دماي اوليه (گرمترين دما) و دماي نهايي (سردترين دما) و نيز سرعت سردسازي تأثير بسزايي بر روي خواص ماده نهايي بدستآمده ميگذارند. بعنوان مثال، اگر ماده با كندي سرد شود اتمها قادر به آزادسازي انرژي بيشتر و قرارگيري در شرايط پايدارتر و نيز آرايش مناسبتر خواهند بود و درنتيجه ماده نهايي استحكام و مقاومت به ضربهء بيشتري خواهد داشت. ازطرفي، سرد كردن سريع فرصت پايين آمدن سطح انرژي را از ذرات گرفته و ماده نهايي بدست آمده تردتر و شكنندهتر ميشود. بر اين اساس، بادرنظر گرفتن دماي اوليه بعنوان يك نقطهء شروع اوليه، دماي نهايي بعنوان نقطهء پايان حل و سرعت سردسازي بعنوان گام حركت در فضاي جواب، الگو برداري مؤثري از فرآيند سردسازي براي حل مسألههاي پيچيدهء رياضي شدهاست. در اين الگوريتم نيز همانند الگوريتم ژنتيك مكانيزم جلوگيري از رسيدن به جواب بهينهء محلي وجود دارد. بدينمنظور جوابهاي بهبود نيافته در هر مرحله بصورت احتمالي پذيرفته ميشوند.
طراحي آزمايشات
همانگونه كه پيشتر اشاره شد، الگوريتمهاي فرا ابتكاري ما را به سمت جواب زير-بهينه هدايت ميكنند. نكتهء حائز اهميت كيفيت جواب زير-بهينه است كه براي بهبود آن و رسيدن به حالتي پايدار، الگوريتمها را مورد تجزيه و تحليل آماري قرار ميدهيم. بنابراين، بايد عوامل تأثيرگذار (فاكتورها) و سطوح مختلف هر عامل تعيين و بررسي گردد.
تعريف و بررسي شرايط ممكن در يك آزمايش چند فاكتوري “طراحي آزمايشات” ناميده ميشود و درصورت بررسي تمامي حالتهاي ممكن آزمايش، به آن “طرح فاكتوريلي كامل” ويا بطور خلاصه “طرح فاكتوريلي” ميگويند. منشأ پيدايش اينگونه آزمايشات به نيم قرن پيش و به تحقيقات دانشمندي بنام فيشر در زمينهء بهينهسازي عملياتهاي كشاورزي برميگردد كه بعدها در ديگر صنايع نيز توسعه فراواني يافت. عليرغم مزاياي زياد و بهبودهاي انكارناپذير روش طراحي فاكتوريلي، اين روش معايبي را نيز دربر دارد كه از آن جمله ميتوان به رشد نمايي تعداد حالات ممكن با افزايش فاكتورها يا سطوح آنها و عدم توجيه اقتصادي اينگونه طراحيها در ابعاد بزرگ اشاره نمود. تعداد آزمايشات ممكن (N) در يك طراحي فاكتوريلي از رابطهء N=LM بدست ميآيد كه در آن M تعداد فاكتورها و L تعداد سطوح هر در هر فاكتور است. بنابراين، براي طراحي آزمايشي با 15 فاكتور 2 سطحي بايد تعداد 215 يعني 32768 آزمايش اجرا گردد تا بتوان بهترين تركيب ممكن از سطوح فاكتورها را يافت. بمنظور مقابله با اين نارسايي روشهاي ديگري همچون آزمايشات فاكتوريلي جزئي كه منجر به كاهش تعداد آزمايشات شده و تنها كسري از كل تركيبات ممكن را بررسي ميكند مطرح شد. از طرفي، استفاده از چنين روشهايي انجام عمليات و محاسبات رياضي بسيار زيادي را در مراحل طراحي آزمايشات و نيز تحليل نتايج ميطلبد. بعلاوه، براي انجام آزمايشي با يك هدف مشخص، طراحيهاي متفاوتي توسط آزمايشگرهاي مختلف ميتواند ارائه شود كه اين امر موجب بروز مشكلات و اختلاف نظراتي در طراحي آزمايشات و تحليل نتايج ميشود. سرانجام، پس از جنگ جهاني دوم فردي بنام دكتر تاگوچي طراحي الگويي ساده و استاندارد براي آزمايشات فاكتوريلي جزئي ارائه و به اين اختلاف نظرها و نتايج متفاوت براي آزمايشات مشابه پايان داد كه از آن با عنوان “طراحي آزمايشات تاگوچي” ياد ميشود [21].
مسألهء زمانبندي كارگاه باز
همانگونه كه پيشتر اشاره شد، اين تحقيق روي مسألهء زمانبندي كارگاه باز (OSSP) تمركز دارد. مسألهء زمانبندي كارگاه باز شامل m ماشين (M1,M2,…,Mm) براي انجام n كار (J1,J2,…,Jn) است كه هر كار در برگيرندهء m فعاليت است [4]. j -امين فعاليت كار Ji با Oij نشان داده ميشود كه بايد بمدت pij≥0 واحد زماني روي ماشين Mj پردازش شود. بنايراين، در مجموع تعداد n×m فعاليت خواهيم داشت (O11,O12,…,Onm). مجموع زمان پردازش كار Ji برابر با pi=jpij و مجموع زمان نياز به ماشين Mj برابر با Mj=ipij است. همچنين، يك پارامتر جديد بصورت H=maxpi,Mj تعريف ميشود كه بطور آشكار زمان پايان هر برنامهء زمانبندي در كارگاه باز حداقل به اندازهء H خواهد بود.
محدوديتهاي مسألهء كارگاه باز بقرار زيرند:
هر ماشين در آن واحد حداكثر يك فعاليت را پردازش ميكند.
هر كار در آن واحد حداكثر توسط يك ماشين پردازش ميشود.
هر فعاليت Oij بايد بمدت pij واحد زماني روي ماشين Mj پردازش گردد.
تفاوت اصلي بين مسألههاي جريان كارگاهي و كارگاه باز اينست كه در جريان كارگاهي فعاليتهاي هركار بايد بترتيب پردازش شوند. يعني، امكان شروع پردازش فعاليت Oi,j تا زماني كه فعاليت Oi,j-1 تمام نشود وجود ندارد (1<j<m). اين در حالي است كه ترتيب پردازش فعاليتها در كارگاه باز بصورت دلخواه است [22]. در مسألهء كار كارگاهي، تعداد فعاليتهاي هر كار به m محدود نبوده و هر تعدادي ميتواند باشد. برخلاف جريان كارگاهي و كارگاه باز كه j -امين فعاليت هر كار بايد توسط ماشين Mj پردازش شود، در كار كارگاهي چنين محدوديتي وجود نداشته و هر فعاليت از هر كار به يكي از ماشينها اختصاص مييابد. اما همانند جريان كارگاهي، در كار كارگاهي نيز ترتيب پردازش فعاليتها مشخص است. بنابراين، ميتوان اينگونه برداشت نمود كه مسألهء كارگاه باز همانند مسألهء جريان كارگاهي است با افزودن اين انعطاف كه ترتيب پردازش فعاليتها دلخواه است.
بيشتر مطالعههاي صورت گرفته بر روي مسألههاي زمانبندي تحت اين فرض اساسي كه ماشينها در تمام طول افق برنامهريزي در دسترس هستند انجام شدهاست در حالي كه در بسياري موارد در دنياي واقعي اين چنين نيست. ماشينها ممكن است بدلايلي همچون نگهداري و تعميرات پيشگيرانه، خرابي، دورهء استراحت، كارهاي باقيمانده از دورهء برنامهريزي قبلي كه در ابتداي دورهء جديد بايد پردازش شوند و غيره، در دسترس نباشند [4]. در بسياري موارد، اين زمانهاي عدم دسترسي از قبل معلوم هستند و بنابراين تصميمگيرنده با درنظر گرفتن آنها ميتواند تصميم كاراتري اتخاذ نمايد.
در محيط كارگاه باز مورد نظر اين تحقيق، فعاليت نگهداري و تعميرات دورهاي موجب بروز توقف در زمانهاي از پيش تعيين شدهاي روي ماشينآلات توليدي ميگردد. اين توقفات در زمانهاي مختلفي روي ماشينآلات اتفاق ميافتد و طول مدت آن براي ماشينهاي مختلف متفاوت ولي مشخص است. علت انتخاب اين نوع از نگهداري و تعميرات دورهاي، كاربرد وسيع آن در صنعت و تجربهء عملي در كارخانجات مختلف خودروساز و قطعه ساز بودهاست. بهرحال، مشكل اصلي ممكن است اين موضوع باشد كه افزودن محدوديت عدم دسترسي به مسأله موجب پيچيدهتر شدن آن ميشود [4]. از ديگر شرايط موردنظر اين تحقيق مجاز نبودن بريدگي كارهاست كه به سبب آن درصورت نبود زمان كافي براي انجام يك فعاليت و مواجه با توقف ماشين، فعاليت موردنظر روي ماشين بارگذاري نشده و پردازش آن به بعد از اتمام توقف ماشين (يعني؛ اتمام فرآيند نگهداري و تعميرات) موكول ميشود. همچنين، زماني كه يك كار روي ماشيني قرار دارد به سه بخش شامل زمان آمادهسازي، زمان پردازش و زمان جداسازي تقسيم ميشود. درنظرگرفتن زمانهاي حمل و نقل و جابجايي بين ماشينها از ديگر ويژگيهاي مسألهء مذكور است. بدليل امكان استفاده از وسايل مختلف جهت حمل و نقل اقلام مختلف در يك كارگاه، زمان جابجايي در يك مسيرِ ثابت براي هر كالا (كار) متفاوت است. همچنين، مسير رفتِ كاري از ماشيني به ماشين ديگر متفاوت از مسير برگشت آن در نظر گرفته شده كه علت آن به حداقل رساندن تداخل جريان مواد است. بنابراين، ماتريس حمل و نقل كارها بين ايستگاههاي كاري مختلف نامتقارن است. فرض نامتقارن بودن زمانهاي جابجايي از اين نقطهنظر نيز قابل اهميت است كه، يكي از كاربردهاي زمانبندي در زمينهء مهمي بنام مسألهء مسير وسيلهء نقليه (VRP) مطرح ميشود [4]. با درنظر گرفتن ملاقاتها بعنوان فعاليتها، وسايل نقليه بجاي ماشينها و جابجايي بجاي هزينههاي آمادهسازي بين فعاليتها، ميتوان VRP را بصورت يك مسألهء زمانبنديِ كارگاه باز دانست [23]. همچنين، در VRP دو نوع جابجاييِ متقارن و نامتقارن مورد بررسي قرار ميگيرد.
با توجه به نمادگذاريها و علائم تشريح شده در طول اين فصل، مسألهء موردنظر اين تحقيق بصورت O/nr-pm/θ1Cmax+θ2iTi معرفي ميشود كه بيانگر مسألهء زمانبندي كارگاه باز با محدوديتهاي مجاز نبودن بريدگي كارها و عدم دسترسي ماشينها ناشي از نگهداري و تعميرات دورهاي با توابع هدف كمينهسازي شامل طولانيترين زمان تكميل كارها (Cmax) و مجموع تأخيرها (iTi) كه بصورت تركيب وزني در يك تابع منفرد ارائه ميشوند، است. بعلاوه، در اين تحقيق زمانهاي آمادهسازي كارها روي ماشينها و نيز جداسازي آنها بصورت وابسته به كار و ماشين درنظر گرفته ميشوند. بمنظور حل مسألههاي با ابعاد كوچك و در شرايط معلوم بودن وزن هر يك از هدفها، رويكردهاي دقيق و تقريبي شامل يك مدل رياضي دو هدفهء خطيِ آميخته و الگوريتمهاي فرا ابتكاريِ تك هدفهء ژنتيك و شبيهسازي تبريد بكار گرفته ميشوند. بعلاوه، در شرايط نامعلوم بودن وزن هر يك از هدفها، از دستاورد جوابهاي بهينهء پارتو با استفاده از الگوريتمهاي فرا ابتكاري شامل الگوريتم ژنتيك موازي چند هدفه و الگوريتم شبيهسازي تبريد موازي چند هدفه جهت حل مسائل با ابعاد بزرگ استفاده ميشود. پارامترهاي مربوط به الگوريتمهاي فرا ابتكاري با استفاده از روش طراحي آزمايشات تاگوچي تنظيم ميشوند كه در نتيجهء آن، الگوريتمها حالت پايداري در مواجه با مسألههاي مختلف نشان ميدهند. در پايان از مسألههايي كه بصورت تصادفي توليد شدهاند جهت ارزيابي عملكرد مدل رياضي و الگوريتمهاي طراحي شده استفاده ميشود.فصل دوم
مرور ادبيات
2-1- مقدمه
مسألهء زمانبندي كارگاه باز، يكي از پركاربردترين مسألههاي زمانبندي است كه كاربردهاي آن تنها به محيطهاي توليدي و صنعتي محدود نميشود. بعنوان مثال، سيستمهاي كامپيوتري، سازمانهاي خدماتي، حمل و نقل هوايي، شركتهاي مسافري و گردشگري تنها بخشي از كاربردهاي اين محيط زمانبندي را تشكيل ميدهند [4]. عليرغم كاربردهاي وسيع مسألهء زمانبندي كارگاه باز، نسبت به ديگر مسألههاي زمانبندي همچون جريان كارگاهي و يا كار كارگاهي توجه كمتري به اين مسأله شدهاست. در اين بخش، ما بدنبال مرور تحقيقات انجام گرفته بر روي ابعاد مختلف مسألهء مورد نظرِ اين تحقيق هستيم. بدينمنظور، بخشهاي مختلف مسأله شامل محيط و شرايط، محدوديتها، معيارهاي اندازهگيري، روشها و الگوريتمهاي پيشنهاديِ حل و نيز روش تنظيم پارامترهاي الگوريتمها بطور جداگانه بررسي ميشوند.
2-2- معيارهاي اندازهگيري و تابع هدف
معيارهاي اندازهگيري مختلفي جهت بهينه شدن بصورت يك تابع هدف منفرد و يا چند تابع هدف همزمان در مسألههاي زمانبندي توسط محققان مورد بررسي قرار گرفتهاند. از آن جمله ميتوان به كار كولاماس و كيپاريسيس [24] اشاره كرد كه تعداد كارهاي تأخيردار را در محيط كارگاه باز كمينه نمودند. در مسألهء مورد نظر آنها، يكي از ماشينها داراي بيشترين زمان پردازش كارها نسبت به ديگر ماشينها بوده و همهء كارها داراي زمان تحويل يكساني هستند. آنها براي چنين مسألهاي يك الگوريتم با زمان حل چندجملهاي ارائه دادند. تحقيق ديگري كه با هدف كمينه كردن كارهاي تأخيردار در محيط كارگاه باز صورت گرفته مربوط به كار باپتيسته [25] است كه در آن كارها داراي وزن بوده و محيط پوياست، بدين معني كه زمان ورود كارها به كارگاه متفاوت است. آنها درشرايطي يك الگوريتم حل با زمان چندجملهاي بروش برنامهريزي پويا ارائه دادند كه زمان پردازش همهء كارها روي تمام ماشينها واحد درنظر گرفته شدهاست.
طولانيترين تأخير از ديگر معيارهاي مورد توجه محققين در مسألههاي زمانبندي است. شين و ليااُ [26] با استفاده از تكنيك جريان شبكه يك الگوريتم چندجملهاي براي كمينه كردن طولانيترين تأخير در محيط ماشينهاي موازي با سرعتهاي يكسان و شرط مجاز بودن بريدگي كارها معرفي كردند.
ليا [27] يك روش ابتكاري براي كمينه كردن مجموع تأخيرها در مسألهء زمانبندي كارگاه باز با ابعاد بزرگ و شرط مجاز بودن بريدگي كارها ارائه داد. همچنين، او از روش شاخه و كران براي يافتن حد پايين و نيز حل مسألههاي با ابعاد متوسط استفاده نمود. لو و يه [28] نيز كمينه كردن مجموع تأخيرها را در محيط كارگاه باز مورد نظر قرار دادند. آنها ابتدا يك مدل برنامهريزي صفر و يك ارائه دادند و سپس از روشهاي ابتكاري بر اساس الگوريتم ژنتيك براي حل مسألههاي بزرگتر استفاده نمودند. پناهي و همكاران [29] مجموع تأخيرها و طولانيترين زمان تكميل را بعنوان توابع هدف كمينهسازي در محيط كارگاه باز بررسي كردند.
ليا و همكاران [30] مجموع زمان تكميل كارها در مسألهء كارگاه باز را با روش ابتكاري و روش شاخه و كران كمينه نمودند. ويژگي خاص كارگاه باز مورد نظر آنها مشخص بودن توالي كارها روي يكي از ماشين بود. نتايج نشان داد كه روش ابتكاري آنها براي حل مسألههاي بزرگ و روش شاخه و كران براي حل مسألههاي كوچك كاراست. بعلاوه، ليا در كار ديگر خود [31] مجموع زمان تكميل كارها را در مسألهء كاركاه باز دو ماشينه با شرط مجاز بودن بريدگي كارها كمينه نمود. او از روشهاي ابتكاري و برنامهريزي پويا براي مسألهء مذكور در دو حالت كارهاي وزني و غير وزني بهره برد و توانست مسألههايي تا 30 كار را در زمان معقول حل كند. از ديگر كارهاي انجام شده با معيار كمينه كردن مجموع زمان تكميل كارهاي وزني ميتوان به تحقيق كلر و همكاران [32] اشاره كرد كه در محيط تك ماشين انجام شدهاست. مجاز نبودن بريدگي كارها و وجود يك زمان توقف از پيش تعيين شده براي ماشين از خواص مسألهء موردنظر آنهاست. آنها دو روش ابتكاري براي مسألهء مذكور ارائه دادند. براسل و هنس [33] كمينه كردن ميانگين زمان تكميل را بعنوان تابع هدف در مسألهء كارگاه باز با شرط مجاز بودن بريدگي كارها موردنظر قرار دادند. ميانگين زمان تكميل را ميتوان حالت خاصي از مجموع وزني زمانهاي تكميل دانست. آنها حدود پايين و روشهاي ابتكاري را براي مسألهء مذكور توسعه دادند.
يكي از معيارهايي كه بيشترين توجه محققين را به خود جلب كرده و كارهاي فراواني روي آن صورت گرفته معيار طولانيترين زمان تكميل است. سدنو نودا و همكاران [34] از دستاورد جريان شبكه براي كمينه كردن طولانيترين زمان تكميل در مسألهء كارگاه باز با مجاز بودن بريدگي كارها استفاده كردند. آنها براي هر كار پنجرهء زماني شامل زمان ورود كار به كارگاه و زمان تحويل متصور شدند. بعلاوه، ديركرد از زمان تحويل مجاز نبوده و زمان تحويل درحقيقت آخرين مهلت درنظر گرفته شدهاست. همچنين، آنها در كار ديگر خود [35] مسألهء مذكور را بصورت دو هدفه با معيارهاي طولانيترين زمان تكميل بعلاوهء يك معيار هزينهاي بررسي كرده و مجدداً از دستاورد جريان شبكه براي حل آن بهره بردند. سِن و بِنلي [36] جريان انباشته را در مسألهء كارگاه باز مورد توجه قرار داده و طولانيترين زمان تكميل را در حالت تك كاره و نيز حالت چند كارهء دو ماشينه كمينه نمودند. ليا [37] از روش بهبود مكرر بر پايهء تجزيهء بِندِر براي كمينه كردن طولانيترين زمان تكميل در مسألهء كارگاه باز با شرط مجاز بودن بريدگي كارها استفاده كردهاست. در روش بِندِر اجزاي زمانبندي و توالي عمليات تجزيه شده و با هر يك جداگانه برخورد ميشود. ليا و همكاران [38] مسألهء كمينهسازي طولانيترين زمان تكميل را در كارگاه باز دو ماشينه با شرايط مجاز نبودن بريدگي كارها و نيز مجاز نبودن انتظار كارها بين ماشينها مورد بررسي قرار دادند. آنها يك الگوريتم حل دقيق بر پايهء روش شاخه و كران براي مسألههاي با ابعاد متوسط با بيش از 100 كار و يك الگوريتم ابتكاري دو فازي براي مسألههاي با ابعاد بزرگ ارائه كردند. گورِت و پرينس [39] دو روش ابتكاري براي حل مسألهء كمينهسازي طولانيترين زمان تكميل كارها در محيط كارگاه باز با شرط مجاز نبودن بريدگي كارها معرفي كردند. مرادي و همكاران [40] طولانيترين زمان تكميل را در محيط كاركارگاهي انعطافپذير با استفاده از روش فرا ابتكاري معماري ژنتيك كمينه نمودند. برِيت و همكاران [41] طولانيترين زمان تكميل را بعنوان معيار كمينهسازي در مسألهء كارگاه باز دو ماشينه با درنظرگرفتن نوع خاصي از مجاز بودن بريدگي كارها و نيز يك زمان توقف از پيش تعيين شده روي يكي از ماشينها بررسي كردند. در مسألهء موردنظر آنها كارها مجاز به بريده شدن حين پردازش و ادامهء پردازش در هر زمان ديگري هستند با اين شرط كه تا تكميل نشدن فعاليت قطع شده، روي ماشين ديگري قرار نگيرند. همچنين، آنها در كار بعدي خود [42] طولانيترين زمان تكميل كارها را با شرط مجاز نبودن بريدگي كارها و چند زمان توقف از پيش تعيين شده براي هر دو ماشين در مسألهء كارگاه باز دو ماشينه بطور تقريبي كمينه كردند. چِن و همكاران [43] طولانيترين زمان تكميل كارها را در مسألهء كارگاه باز با وجود زمانهاي ورود كارها به كارگاه (يعني، سيستم پويا) درنظر گرفتند. اِستراسويچ [44] طولانيترين زمان تكميل كارها را در محيط كارگاه باز دو ماشينه و وجود زمانهاي حمل ونقل و شرط مجاز نبودن بريدگي كارها با استفاده از يك الگوريتم تقريبي بررسي كرد. وي همچنين در كار بعدي خود [45] دستاورد تكنولوژي گروهي كه در آن كارها در دستههاي مختلف قرار گرفته و هر دسته يك زمان آمادهسازي دارد را در محيط كارگاه باز دو ماشينه درنظر گرفته و طولانيترين زمان تكميل را با شرط مجاز نبودن بريدگي بررسي كرد. او يك الگوريتم ابتكاري با زمان حل خطي براي حل مسألهء مذكور ارائه داد. كيپاريسيس و كولاماس [46] تابع هدف مسألهء كارگاه باز دو ماشينه را بصورت سلسله مراتبي درنظر گرفتند. بدين صورت كه مجموع زمانهاي تكميل كارها با توجه به حداقلِ طولانيترين زمان تكميل كمينه گردد.
جانگواتاناكيت و همكاران [47] تركيب محدب دو هدف طولانيترين زمان تكميل كارها و تعداد كارهاي تأخيري را بعنوان توابع كمينهسازي در مسألهء جريان كارگاهي تركيبي درنظر گرفتند. پناهي و توكليمقدم [48] كمينه سازي همزمان دو هدف شامل طولانيترين زمان تكميل كارها و مجموع تأخيرها را در مسألهء كارگاه باز درنظر گرفته و از الگوريتم بهينهسازي جمعيت مورچگان تركيبي جهت حل آن در زمان قابل قبول استفاده كردند. رشيدي و همكاران [49] طولانيترين زمان تكميل و طولانيترين تأخير از موعد تحويل را بطور همزمان در مسألهء جريان كارگاهي تركيبي شامل ماشينهاي موازي نامرتبط در هريك از ايستگاههاي سيستم جريان كارگاهي مورد بررسي قرار دادند. چانگ و همكاران [50] هدفهاي طولانيترين زمان تكميل كارها و طولانيترين تأخير را بعنوان دو هدف همزمان در مسألهء جريان كارگاهي درنظر گرفتند.
مرادي و زنديه [51] كمينهسازي طولانيترين زمان تكميل را در سيستم توليدي ماشينهاي موازي را بهمراه كمينهسازي عدم دسترسي ناشي از نگهداري و تعميرات بررسي و از روشهاي فرا ابتكاري تركيبي جهت حل آن بهره بردند. توكليمقدم و همكاران [52] تعداد كارهاي تأخيردار و مجموع زمانهاي تكميل كارها را بطور همزمان در مسألهء ماشينهاي موازي نامرتبط با استفاده از الگوريتمهاي فرا ابتكاري بهينه نمودند.
2-3- مجاز نبودن بريدگي كارها
در بخش قبل به تحقيقات انجام شده با شرط مجاز نبودن بريدگي كارها اشاره شد. دراينجا فقط جهت حفظ دستهبندي، تكرار ميكنيم كه از جمله مواردي كه مسألهء كارگاه باز را با درنظر گرفتن شرط مذكور بررسي نمودند ميتوان تحقيق ليا [37]، برِيت و همكاران [42] و اِستراسويچ [45،44] را نام برد. بعلاوه، ليا در كار ديگر خود [53] كارگاه باز را مجدداً با شرط مجاز نبودن بريدگي كارها بررسي نمود. جانگواتاناكيت و همكاران [47] نيز شرط مذكور را در مسألهء جريان كارگاهي تركيبي درنظر گرفتند. مرادي و زنديه [51] نيز كه بدنبال كمينه كردن احتمال خرابي ماشينها در سيستم ماشينهاي موازي از طريق انجام بموقع فعاليتهاي نگهداري و تعميرات پيشگيرانه بودند، محدوديت مجاز نبودن بريدگي كارها را درنظر گرفتهاند.
2-4- نگهداري و تعميرات دورهاي و محدوديت عدم دسترسي ماشينها
نگهداري و تعميرات دورهاي نوع خاصي از نگهداري تعميرات پيشگيرانه است كه توقفات و عدم دسترسيِ ماشينها را بصورت از پيش تعيين شده در پي دارد. شين و ليااُ [26] محدوديتهاي دردسترس بودن ماشينها و توانايي پردازش كارها را بطور همزمان در مسألهء زمانبندي ماشينهاي موازي با سرعتهاي يكسان موردنظر قرار دادند. بدين معني كه ماشينها در طول دوره برنامهريزي بطور پيوسته قابل استفاده نيستند و هر كار ميتواند توسط ماشينهاي خاصي پردازش شود. آنها از تكنيك جريان شبكه براي فرمولبندي اين مسأله بصورت يك سري مسألههاي جريان بيشينه استفاده كردند. كلر و همكاران [32] يك زمان از پيش تعيين شدهء دردسترس نبودن ماشين در مسألهء تك ماشينه درنظرگرفته و دو روش ابتكاري براي حل آن ارائه دادند.
مرادي و همكاران [40] نگهداري و تعميرات پيشگيرانه را بعنوان محدوديت در دسترس بودن ماشينها در مسألهء كار كارگاهي انعطافپذير در نظر گرفته و استراتژيهاي مختلف نگهداري و تعميرات پيشگيرانه را تشريح نمودند. برِيت و همكاران [41] مسألهء كارگاه باز دو ماشينه را با شرط وجود يك زمان توقف از پيش تعيين شده روي يكي از ماشينها بررسي كرده و يك الگوريتم ابتكاري ارائه دادند. آنها همچنين در كار بعدي خود [42] چند زمان توقف از پيش تعيين شده را براي هر دو ماشين درنظر گرفته و مجدداً از الگوريتمهاي ابتكاري جهت حل تقريبي مسأله بهره بردند.
مرادي و زنديه [51] بمنظور بيشينه شدن قابليت اطمينان سيستم بدنبال ادغام فرآيند نگهداري و تعميرات پيشگيرانه در مسألهء ماشينهاي موازي بنحوي هستند كه كمترين زمان عدم دسترسي ماشينها ايجاد شود. هسو و همكاران [54] دو رويكرد متفاوت نگهداري و تعميرات دورهاي را بطور همزمان در مسألهء زمانبندي تك ماشين مورد بررسي قرار دادند. رويكردهاي نگهداري و تعميرات دورهاي در مسألهء موردنظر آنها بدينترتيب است كه ماشين پس گذشت مدت زمان مشخص (T) و يا پس از پردازش تعداد مشخصي كار (K) بمنظور انجام فرآيند نگهداري و تعميرات متوقف ميشود. بديهي است هر يك از دو شرط مذكور زودتر رخ دهد موجب توقف ماشين خواهد شد. همچنين، آنها كارها را بدون بريدگي درنظر گرفتند.
لي [55] زمان از پيش تعيين شدهء عدم دسترسي ماشينها را در مسألهء جريان كارگاهي دو ماشينه درنظر گرفته و سه حالت براي كارها متصور است: كارهايي كه درصورت بريده شدن حين پردازش ميتوانند در زمان ديگري از همان نقطهء قطع شده پردازش شوند، كارهايي كه درصورت بريده شدن حين پردازش بخشي از آنها در زمان ديگري پردازش ميشوند و كارهايي كه درصورت بريده شدن حين پردازش تمام كار از ابتدا بايد پردازش شود. وي پيچيدگي مسأله را بررسي كرده و يك الگوريتم برنامهريزي پويا با زمان حل شبه چندجملهاي براي آن ارائه داد. سان و لي [56] دو ماشين موازي يكسان را كه در آن بدليل كاهش احتمال خرابي ماشينها يك حداكثر زمان مشخص براي پردازش پيوستهء آنها درنظر گرفته شده، بررسي كردند.
ما و همكاران [57] خلاصهاي از مسألههاي زمانبندي با محدوديت عدم دسترسي ماشينها ناشي از فعاليتهاي نگهداري و تعميرات پيشگيرانه ارائه دادند. بعلاوه، آنها بطور مختصر به تشريح پيچيدگي مسألهها، روشهاي حل دقيق و تقريبي در محيطهاي زمانبندي مختلف شامل تك ماشين، ماشينهاي موازي، جريان كارگاهي، كارگاه باز و كار كارگاهي با معيارهاي اندازهگيري متفاوت پرداختند.
دِفِرشا و چِن [58] نوع خاصي از عدم دسترسي ماشينها را در كار كارگاهي تركيبي متصور شدند. بدينترتيب كه ماشينها بدلايلي همچون انجام كارهاي باقيمانده از دورهء قبليِ برنامهريزي، در ابتداي دورهء فعلي دردسترس نخواهند بود. آنها محدوديت مذكور را زمان آزاد شدن ماشين ناميدند كه مشابه آن براي كارها در سيستمهاي پويا درنظر گرفته ميشود. همچنين، آنها يك مدل برنامهريزي خطي مختلط ارائه دادند.
آلااوي و آرتيبا [59] بهينهسازي چندين تابع هدف براساس كار در جريان ساخت و موعد تحويل را در مسألهء زمانبندي جريان كارگاهي تركيبي با درنظر گرفتن محدوديتهاي نگهداري و تعميرات مورد بررسي قرار دادند. همچنين، آنها زمانهاي آمادهسازي، تميزكاري (كه مشابه جداسازي است) و حمل و نقل را درنظر گرفتند.
2-5- زمانهاي حمل و نقل
حمل و نقل و جابجايي مواد، كالاها، كارها، مسافران و غيره از مهمترين زيرشاخههاي مديريت استراتژيك بوده و معمولاً يافتن مدلي مناسب براي آن از چالشهاي پيش روي مديران در هر سازمان است. هرچند كه در محيطهاي كوچك عدم توجه به اين مقوله سيستم را با مشكل مواجه نكند ولي با هرچه بزرگتر شدن سيستم، هزينههاي ناشي از اين عدم توجه ميتواند جبران ناپذير باشد. بعنوان مثال، درنظر نگرفتن جابجاييها در يك سيستم توليدي ممكن است منجر به تداخل جريان مواد و درنتيجه بالا رفتن ميزان توقفها و انتظارها شود. از طرفي، توجه به حمل و نقل و لحاظ نمودن آن در برنامهريزيها و بويژه برنامههاي زمانبندي علاوه بر روانتر كردن جريان مواد و كاهش اختلالات ناشي از آن، تأثير بسزايي در كاهش هزينهها خواهد داشت. هرچند كه مسألهء حمل و نقل خود به تنهايي زمينهء مهم و گستردهاي از تحقيقات را شامل ميشود ولي ما در اين بخش به معرفي چند تحقيق كه آن را در مسألههاي زمانبندي درنظر گرفتهاند اكتفا ميكنيم.
اِستراسويچ [44] در مسألهء كارگاه باز دو ماشينه يك فاصلهء زماني بين اتمام پردازش فعاليت مربوط به يك كار روي ماشيني و شروع فعاليت بعدي همان كار روي ماشين ديگر متصور شد كه بدليل وجود حمل و نقلي كه در شرايط واقعي اتفاق ميافتد آن را زمانهاي حمل ونقل ناميد. همچنين، وي اشاره ميكند كه در كاربردهاي شيميايي و متالورژيك اين زمانهاي حمل و نقل معادل زمانهاي فرآيندهاي گرم كردن و يا سرد كردن هستند.
