زمان بندی خط تولید

فرض کنید که یک کارخانه داریم که دو خط تولید داره،هر خط تولید n ایستگاه داره و در هر لحظه فقط یک ایستگاه میتونه میزبان محصول باشه و در هر لحظه فقط یک محصول داخل کل کارخونه(دو خط تولید) ساخته میشه.چیزی که در این دو خط تولید منحصر به فرد هست اینه که هر ایستگاه زمان تولید مخصوص به خودش رو داره و ایستگاه های متناظر ، کار های یکسان رو انجام میدن(مثلا رنگ کردن و یا صافکاری یا ...) و قاعدتا میشه فهمید که گاهی اوقات بهتره یک ایستگاه از یک خط دیگه رو برای تکمیل اون بخش از محصول انتخاب کنیم. جدا از این ها ، هر خط تولید یک مولفه زمانی برای وارد کردن مواد اولیه محصول و خارج کردن محصول نهایی نیاز داره. برای درک بیشتر به این شکل نگاه کنید.

فعلا زیاد سخت نگیرید نسبتا به نامگذاری متغیر ها ، t1 , t2 , t3 ,t4 هزینه های انتقال از یک خط به خط دیگر هستند ، گاهی اوقات این هزینه انتقال به صرفه است و گاهی به صرفه نیست ! مسئله زمانبدی خط تولید از ما می خواد که بهترین ند ها رو برای تولید محصولمون انتخاب کنیم. بعضی ند ها ممکنه هزینه خیلی زیادی داشته باشن ولی در عوض هزینه تغییر مسیر براشون خیلی زیاد باشه و یا برعکس. من صورت سوال رو به صورت خیلی کتابی و تمیز این پایین میزارم :

مسئله زمان‌بندی دو خط تولید (Assembly Line Scheduling)

کارخانه‌ای دارای دو خط تولید موازی (خط ۱ و خط ۲) است که هر کدام دارای $n$ ایستگاه کاری هستند. ایستگاه $j$-ام در خط $i$ را با $S_{i,j}$ نشان می‌دهیم (که $i\in \{1,2\}$ و $1\le j\le n$).

یک محصول برای ساخته شدن باید به ترتیب از ایستگاه‌های $1$ تا $n$ عبور کند. محصول پس از اتمام کار در ایستگاه $S_{i,j}$ می‌تواند:

1. مستقیم به ایستگاه بعدی در همان خط برود ($S_{i,j+1}$) که این کار هزینه اضافی ندارد.
2. با پرداخت هزینه انتقال، به ایستگاه بعدی در خط دیگر برود ($S_{3-i,j+1}$).

ورودی‌های مسئله:

• $n$: تعداد ایستگاه‌ها در هر خط
• $e_1,e_2$: زمان ورود به خط ۱ و خط ۲
• $x_1,x_2$: زمان خروج از خط ۱ و خط ۲
• ماتریس $a$ به ابعاد $2\times n$: زمان لازم برای انجام کار در ایستگاه‌ها (سطر اول برای خط ۱ و سطر دوم برای خط ۲)
• ماتریس $t$ به ابعاد $2\times (n-1)$: زمان انتقال بین خطوط ($t_{1,j}$ زمان انتقال از ایستگاه $S_{1,j}$ به ایستگاه $S_{2,j+1}$ و $t_{2,j}$ زمان انتقال از $S_{2,j}$ به $S_{1,j+1}$)

---

تست کیس‌ها (Test Cases)

تست کیس ۱ (تست نمونه استاندارد)

• تعداد ایستگاه‌ها: $n=6$
• زمان ورود: $e=[2,4]$
• زمان خروج: $x=[3,2]$
• زمان کار در ایستگاه‌ها (ماتریس $a$):

Line 1: [7, 9, 3, 4, 8, 4]
Line 2: [8, 5, 6, 4, 5, 7]

---

خب الان سعی کنید که با استفاده از dp یا بروت فورس و یا روش هایی مثل بک ترکینگ این مسئله رو حل کنید!

ایده خودم برای این سوال

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    int n = 4;
    vector<vector<int>> build = {{1,2,7,4} ,{6,1,4,5}};
    vector<vector<int>> switchh = {{0 , 8 , 6 , 5} , 
    {0,2,3,8}};
    
    vector<int> inp = {5,6};
    vector<int> out = {2,5};

    vector<vector<int>>dp(2 , vector<int>(n));

    dp[0][0] = build[0][0] + inp[0];
    dp[1][0] = build[1][0] + inp[1];

    for(int i = 1 ; i < n;i++){
        dp[0][i] = min(dp[0][i-1] + build[0][i] ,
        dp[1][i-1] + switchh[1][i] + build[0][i]);

        dp[1][i] = min(dp[1][i-1] + build[1][i] ,
        dp[0][i-1] + switchh[0][i] + build[1][i]);


    }
    cout << min(dp[0][n-1] + out[0] , dp[1][n-1] + out[1]) <<endl;

}

ایده من برای حل این مسئله dp از پایین به بالا هست.

ببینید الان ما می خوایم مقدار ایستگاه بعدی رو بدست بیاریم. از دو حالت خارج نیست. یا به خط تولید اول میره یا به خط تولید دوم، ما dp هر دو خط تولید رو بدست میاریم و به این صورت بدست میاد :

اگر از ایستگاهی بیاد که در خط تولید فعلی هست نیاز نیست هزینه ای برای جا به جایی بگیریم در غیر این صورت باید هزینه جابه جایی اعمال بشه.

در نهایت ما دوتا مقدار dp برای ایستگاه آخر بدست میاریم و با در نظر گرفتن مقداری که برای خارج کردن محصول برای هر خط تولید نیاز هست ، ما بهترین خط تولید رو انتخاب می کنیم و کمترین مقدار بدست میاد ، قاعدتا برای ذخیره مسیر باید کمی کار بیشتر انجام بدیم یا از روش های دیگه بریم.پس این دو چالش رو برای شما قرار میدم که حل کنید.سعی می کنم در آینده ، پاسخ این ها رو هم قرار بدم (چون خودم هنوز حل نکردم)

---

تمرین

۱-اگر بخوایم مسیر خط تولید رو ذخیره کنیم باید چیکار کنیم؟ ۲-اگر n خط تولید داشته باشیم باید چیکار کنیم؟

منابع:

geeksforgeeks