بخشی از پاورپوینت
اسلاید 2 :
اهداف درس این جلسه
حل مساله زمانبندی خطوط مونتاژ با رویکرد برنامهنویسی پویا
اسلاید 3 :
ز) زمانبندی خطوط مونتاژ (Assembly-line scheduling)
فرض کنید کارخانهای خودرو سازی دارای دو خط مونتاژ است
اسلاید 4 :
شاسی خودرو میتواند وارد هرکدام از خطوط مونتاژ شود
در هر ایستگاه اجزایی به آن افزوده میشود و در نهایت فرآیند در پایان خط به اتمام میرسد.
اسلاید 5 :
هر خط تولید شامل n ایستگاه است که با شمارههای j = 1, 2, ., n مشخص میشوند.
jامین ایستگاه در خط iام را (که i، 1 یا 2 است)را با Si,j مشخص میکنیم.
jامین ایستگاه در در خط 1 (S1,j) دقیقا همان کار jامین ایستگاه در خط 2 (S2,j) را انجام میدهد.
ایستگاهها با تکنولوژیهای متفاوت ایجاد شدهاند. بنابراین .
زمان مورد نیاز در ایستگاه Si,j را با ai,j نشان میدهیم.
اسلاید 6 :
ei برابر با زمان مورد نیز برای ورود شاسی به خط iام میباشد.
xi برابر با زمان مورد نیاز برای خروج خودروی تکمیل شده از خط iام میباشد.
اسلاید 7 :
به صورت نرمال هر شاسی وقتی وارد خطی میشود تنها در همان خط کارهایش انجام میشود.
زمان مورد نیاز برای رفتن شاسی از یک ایستگاه به ایستگاه بعدی در همان خط قابل صرفنظرکردن است.
به ندرت برخی سفارشهایی توسط مشتریها به کارخانه داده میشود که میخواهند اتومبیل در اسرع وقت تکمیل شود.
برای چنین درخواستهایی هم باز هم باید n ایستگاه را به ترتیب پشت سر بگذارد ولی مدیر کارخانه امکان دارد خودروی نیمهساز را از یک خط به خط دیگری منتقل کند.
زمان مورد نیاز برای انتقال شاسی از خط i بعد از اینکه ایستگاه Si,j را تمام کرد برابر با ti,j است که
i = 1, 2 و j = 1, 2, ., n - 1
اسلاید 8 :
مساله در اینجا
شاسی چه ایستگاههایی را در خط 1 و 2 انتخاب کند که در حداقل زمان ممکن برای کارخانه تکمیل شود.
اسلاید 9 :
برای این مساله الگوریتم brute-force ای به صورت زیر میتوان متصور شد:
.
که دارای پیچیدگی محاسباتی 2n میباشد.
اسلاید 10 :
بررسی اصل بهینگی
چنانچه سریعترین راه برای رسیدن به ایستگاه jام را داشته باشیم .
از آن سریعترین راه برای رسیدن به S1,j-1 یا S2,j-1 را نیز خواهیم داشت.
اسلاید 11 :
اگر نگاهی به راه حل سریعترین زمان اتمام کار در S1,j بیاندازیم .
میباید از ایستگاه j-1 از خط 1 یا 2 آمده باشد.
بنابراین، سریعترین راه برای اتمام کار در S1,j برابر است با
سریعترین راه اتمام کار در S1,j-1 و سپس مستقیم به S1,j بیاید یا
سریعترین راه اتمام کار تا S2,j-1 سپس انتقال از خط 2 به 1 و سپس زمان ایستگاه S1,j
به همین ترتیب، سریعترین راه برای اتمام کار در S2,j برابر است با
سریعترین راه اتمام کار در S2,j-1 و سپس مستقیم به S1,j بیاید یا
سریعترین راه اتمام کار تا S1,j-1 سپس انتقال از خط 1به 2و سپس زمان ایستگاه S2,j
اسلاید 12 :
فرض کنید fi[j] برابر باشد با سریعترین زمان ممکن برای اینکه شاسی از نقطه شروع به ایستگاه Si,j برسد.
هدف نهایی ما آن است تا شاسی تمامی مراحل ایستگاهی چه در خط 1 و چه در خط 2 را طی کند و به مرحله پایانی برسد:
اسلاید 13 :
برای f1[1] و f2[1] روابط زیر را داریم:
