نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 استادیار گروه مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه سمنان، سمنان، ایران
2 کارشناس ارشد گروه مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه یزد، یزد، ایران
چکیده
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Purpose: The development and complexity of new markets, on the one hand, and economic constraints, on the other hand, have made it an inevitable necessity to pay attention to the two principles of providing a desirable and reliable level of service to customers and reducing supply and maintenance costs. Therefore, the need to study the methods that enable the production system to deal with these issues is felt more than ever. Just-In-Time production strategy has been mentioned as one of the appropriate approaches to balance between the two principles. On the other hand, the issue of sequencing and scheduling of operations in batch processing systems has been widely considered in the last two decades. A batch processing machine can process a batch of jobs simultaneously, which reduces the machine's set-up time and facilitates material flow management. This study aims to minimize the total weighted earliness and tardiness penalties of jobs with non-identical sizes on the batch processing machine, considering that the due date is tight.
Design/methodology/approach: Mathematical programming has been used to model the problem. A mixed integer linear programming model has been proposed for the research problem. Since the problem is shown to be NP-hard, heuristic and meta-heuristic methods have been developed to find near-optimal solutions for industrial-sized instances. Also, a dynamic programming approach has been proposed to find the optimal scheduling of a predetermined batch of jobs.
Findings: The dynamic programming algorithm requires a high computational effort, and the solution time by this algorithm increases significantly when the number of jobs increases. However, the obtained results indicated that the proposed heuristic algorithms lead to good performance with less time and in practice, such algorithms can be used for real applications and large-size instances. The average relative deviation of the proposed particle swarm algorithm is less than 1%, and the value of this index for the proposed heuristic algorithm is 1.78%.
Research implications: Examining the two investigated methods for batching the jobs, one based on a heuristic algorithm and the other with the help of solving a mathematical model, indicated no significant difference between these two methods. Therefore, if necessary, the heuristic algorithm with less computational effort can be used without losing the quality of the solution.
Practical implications: According to the findings, developing efficient heuristic and meta-heuristic algorithms for batch processing machine scheduling in just-in-time production systems can reduce production costs.
Originality/value: For the first the heuristic and meta-heuristic algorithms were proposed for the problem of scheduling a batch processing machine considering a tight due date in a just-in-time production system. A dynamic programming approach was also proposed for the first time to find the optimal scheduling of a predetermined batch of jobs.
کلیدواژه‌ها [English]
1- مقدمه
تاکنون بسیاری از محققان به‌علت کاربرد وسیع مسائل مربوط به زمان‌بندی ماشین‌های پردازش انباشته، به این موارد توجه کرده‌اند. از همین روی، تحقیقات پیشین در بر گیرندۀ طیف گسترده‌ای از مطالب‌اند. در این بخش سعی شده است تا چشم‌اندازی از تلاش‌های انجام‌شده در جهت شناخت و مطالعه دربارۀ این موضوع ارائه شود. به‌طور کلی بسیاری از پژوهش‌های انجام‌شده در این زمینه، مربوط به ارائۀ الگوریتم‌هایی برای یافتن مقدار بهینه یا نزدیک به بهینۀ معیار عملکرد بوده است.
بیش از پنجاه سال از نخستین تحقیقات در حوزۀ زمان‌بندی ماشین‌ها می‌گذرد. نخستین کوشش‌ها در این زمینه، بیشتر معطوف به کمینه‌سازی زمان تکمیل و هزینۀ تأخیر بوده است. به‌کارگیری روش‌های ابتکاری به‌منظور یافتن جواب نزدیک به بهینه در زمان پذیرفتنی و اهمیت این تئوری در مدیریت زمان و منابع در صنایع، باعث شد تا این موضوع در اواخر دهۀ 60 میلادی به موضوع مهمی برای پژوهشگران این حوزه بدل شود (سن و همکاران[i]، ۲۰۰۳). نخستین بار کانت در پژوهشی مسئلۀ حداقل‌سازی مجموع هزینه‌های تأخیر و تعجیل را در حالتی بررسی کرد که برای تمامی کارها موعد تحویل یکسان وجود دارد (بیکر و شودر[ii]، ۱۹۹۰). هوگوین و ون د ولد[iii] (۱۹۹۱) با لحاظ‌کردن موعد تحویل نزدیک در مسئلۀ حداقل‌سازی تابع مجموع وزنی تعجیل و تأخیر، توالی مجموعه‌ای از کارها را تعیین کردند. در این مسئله، دستگاه تنها توانایی پردازش یک کار را داشت. آنها همچنین ثابت کردند که حتی اگر تمامی وزن‌ها یکسان باشد، مسئلۀ بررسی‌شده NP-hard است. هال و همکاران[iv] (۱۹۹۱) نشان دادند مسئلۀ حداقل‌سازی هزینه‌های تعجیل و تأخیر با موعد تحویل نزدیک به زمان شروع زمان‌بندی NP-hard است. نیرچو و امیرو[v] (۲۰۱۳) با بهره‌گیری از الگوریتم ازدحام ذرات[vi] (PSO)، مجموع هزینه‌های تعجیل و تأخیر را برای n کار دارای موعد تحویل نزدیک، به حداقل‌سازی کردند. همچنین نشان دادند در 82% موارد، الگوریتم پیشنهادی از عملکرد مناسبی برخوردار است. جایانتی و آنوسویا[vii] (۲۰۱۷) برای حل مسئلۀ حداقل‌سازی مجموع وزنی تعجیل و تأخیر، از الگوریتم بهینه‌سازی ازدحام ذرات بهره جستند. در این الگوریتم، ذره با کمترین مقدار در ابتدای توالی قرار می‌گیرد و این روند برای دیگر کارها نیز ادامه دارد. در پایان تحلیلی بر نتایج انجام شده است که برآیند آن برتری الگوریتم PSO را در حل این مسئله نشان داده است.
اولین کوشش علمی برای بررسی زمان‌بندی مسئلۀ پردازش انباشته را ایکورا و گیمبل[viii] (۱۹۸۶) انجام دادند. آنها الگوریتمی را برای حداقل‌سازی معیار زمان پایان عملیات ( ) برای محیط تک ماشین با در نظر گرفتن زمان پردازش ثابت، در هنگامی ارائه کردند که موعدهای تحویل و زمان‌های دسترسی سازگارند ( ) لی و همکاران[ix] (۲۰۱۵) مسئلۀ حداقل‌سازی تعجیل و تأخیر را با فرض اندازۀ غیریکسان کارها بررسی کردند. آنها یک الگوریتم ابتکاری را برای انباشتهسازی و یک الگوریتم ژنتیک ترکیبی را برای تعیین توالی انباشته‌ها ارائه کردند. پارسا و همکاران[x] (۲۰۱۷) ضمن در نظر گرفتن موعدهای تحویل یکسان و در فاصلۀ دور نسبت به زمان حال برای کارها در شرایط پردازش انباشته، مسئلۀ حداقل‌سازی مجموع تعجیل و تأخیر را بهصورت یک مدل برنامه‌ریزی عدد صحیح بیان و در ادامه از یک الگوریتم برنامه‌ریزی پویا برای یافتن توالی انباشته‌ها استفاده کردند. آنها در پایان نتیجه گرفتند الگوریتم‌های انباشتهسازی مبتنی بر قاعدۀ طولانی‌ترین زمان پردازش[xi] (LPT)، بهترین عملکرد را در میان دیگر الگوریتم‌های ابتکاری به دست آورده است. ژانگ و همکاران[xii] (۲۰۲۱) مسئلۀ زمان‌بندی روی تک ماشین پردازندۀ انباشته را با در نظر گرفتن اهداف تولید بهنگام بررسی کردند. آنها ضمن استخراج ویژگی‌های جواب بهینه، یک الگوریتم ترکیبی مبتنی بر الگوریتم ژنتیک را پیشنهاد داده‌اند.
ترینداده و همکاران[xiii] (۲۰۲۱) یک مدل‌سازی جدید مبتنی بر گراف برای مسئلۀ کمینه‌کردن زمان تکمیل آخرین کار را در محیط پردازش انباشته ارائه کرده‌اند. آزمایش‌های محاسباتی آنها حاکی از برتری مدل پیشنهادی‌شان نسبت‌به مدل‌های موجود است. قیروگا و همکاران[xiv] (۲۰۲۱) برای حل مسئلۀ زمان‌بندی انباشته با هدف حداقل‌کردن مجموع وزن‌دار تأخیرها، یک الگوریتم ابتکاری مبتنی بر جست‌وجوی را محلی ارائه کرده‌اند. به‌تازگی پسوا و همکاران[xv] (۲۰۲۲) یک روش دقیق مبتنی بر مدل‌سازی زمان-گسسته[xvi] را برای همین مسئله پیشنهاد داده‌اند. آنها به کمک روش پیشنهادی، مسائلی با حداکثر ۱۰۰ کار را بهصورت بهینه حل کردند. یانگ و همکاران[xvii] (۲۰۲۲) مسئلۀ زمان‌بندی پردازش انباشته را با خانواده‌های ناسازگار و تابع هدف مجموع وزن‌دار زمان تکمیل کارها را در نظر گرفته‌اند. آنها برای حل مسئله، چندین مدل‌سازی و یک الگوریتم شاخه و ارزش[xviii] را توسعه داده‌اند. نتایج آنها حاکی از آن است که مسائلی با حداکثر ۱۵۰ کار را الگوریتم شاخه و ارزش پیشنهاد‌شده حل میشود. کونگ و همکاران[xix] (۲۰۲۳) موضوع کاهش انتشار کربن را در حوزۀ مسائل زمان‌بندی تولید انباشته در محیط تولید نیمه‌هادی‌ها بررسی کرده‌اند. تیان و ژنگ[xx] (2024) مسئلۀ زمان‌بندی یک ماشین پردازش انباشته را وقتی بررسی کرده‌اند که قیمت برق مصرفی طی ساعات مختلف روز متفاوت است. آنها یک نحوۀ مدل‌سازی جدید را برای مسئله و چندین رویکرد حل را برای کاهش هزینه‌های برق مصرفی ارائه کرده‌اند. متعاقباً ژنگ و چن[xxi] (2024) یک الگوریتم بهبود‌یافته را برای برقراری تعادل بین مصرف انرژی و بهره‌وری تولید در محیط تولید انباشته ارائه کرده‌اند. فاولر و مونخ[xxii] (۲۰۲۲) طی یک مقالۀ مروری، پیشینۀ موضوع زمان‌بندی پردازش انباشته را بهصورت جامع بررسی کرده‌اند. آنها پژوهش‌های گذشته را با توجه به محیط ماشین‌آلات و نوع تابع هدف دسته‌بندی و دربارۀ روندهای تحقیقات آتی بحث کرده‌اند.
|
نویسندگان |
انباشته |
کار |
موعد تحویل |
روش حل |
تابع هدف (min) |
|
هووگوین و ون د ولد (۱۹۹۱) |
ü |
نزدیک |
برنامه‌ریزی پویا |
|
|
|
نیرچو و امیرو (۲۰۱۳) |
ü |
دور |
الگوریتم PSO |
|
|
|
جایانتی و آنوسویا (۲۰۱۷) |
ü |
نزدیک |
الگوریتم PSO |
|
|
|
لی و همکاران (۲۰۱۵) |
ü |
دور |
الگوریتم ژنتیک |
|
|
|
پارسا و همکاران (۲۰۱۷) |
ü |
دور |
برنامه‌ریزی پویا و ابتکاری |
|
|
|
تحقیق حاضر |
ü |
نزدیک |
برنامه‌ریزی پویا و ابتکاری |
|
با نگاهی هر‌چند اجمالی دربارۀ پیشینۀ موضوع، درمی‌یابیم که بررسی هم‌زمان مسئله‌های تولید بهنگام و پردازش انباشته تاکنون کمتر بررسی شده است. به‌تازگی پارسا و همکاران (۲۰۱۷) پژوهشی را در زمینۀ این دو حوزه، با در نظر گرفتن موعد تحویل دور[xxiii] یا فرصت‌دار انجام دادند، حال آنکه موعد تحویل در عمل نزدیک به زمان آغاز زمان‌بندی است که در این صورت شرایط حل مسئله نیز دستخوش تغییر میشود. از همین روی در این پژوهش، زمان‌بندی پردازش انباشته برای تحقق اهداف تولید بهنگام، با لحاظ‌کردن موعد تحویل نزدیک به زمان حال، به‌عنوان شکاف تحقیقاتی موجود در پیشینۀ موضوع بررسی میشود. شایان ذکر است که در نظر گرفتن موعد تحویل نزدیک به‌جای دور در مسائل زمان‌بندی، باعث پیچیدگی بسیار بیشتر مسئله خواهد شد. حتی در ساده‌ترین حالت که مسئلۀ زمان‌بندی تک‌ماشینه است، وقتی موعد تحویل نزدیک به‌جای دور در نظر گرفته میشود، مسئله از حالت ساده به یک مسئلۀ NP-hard تبدیل میشود. همچنین در نظر گرفتن موعدهای تحویل غیرمشترک برای کارها، مسئله را به‌شدت پیچیده‌تر می‌کند که خارج از چارچوب کار مطرح‌شده در این مقاله است.
2- تعریف مسئله
در این بخش مشخصه‌ها، مفروضات و شرایط بهینگی مسئله بیان شده است. دستگاه پردازش انباشته، ماشینی با قابلیت پردازش هم‌زمان چندین کار و یا به‌عبارتی پردازش یک انباشته از کارهاست. در انباشتهسازی موازی، زمان پردازش انباشته ( )، برابر زمان بزرگ‌ترین کار موجود در انباشته است. معیار عملکرد نیز در راستای تحقق تولید بهنگام، حداقل‌سازی مجموع وزنی تعجیل و تأخیر در نظر گرفته و با رابطۀ مشخص شده است. در رابطۀ مذکور و به ترتیب زمان تکمیل و وزن کار j ام است و d موعد تحویل مشترک برای تمامی کارها قلمداد میشود. فرض میشود موعد تحویل به ابتدای افق برنامه‌ریزی نزدیک است. همچنین رابطۀ شکل دیگری از بیان این معیار عملکرد است که در آن و است. دیگر مفروضات در مدل بررسی‌شده به شرح زیر است:
۱. تعداد کار وجود دارد که همگی سازگار و متعلق به یک خانواده‌اند؛
۲. هر کار برای پردازش به میزان واحد از ظرفیت ماشین نیاز دارد. به پارامتر اندازۀ کار گفته میشود؛
۳. همۀ کارها در لحظۀ صفر در دسترس‌اند؛
۴. زمان مورد نیاز برای پردازش کار معلوم و برابر است؛
۵. ظرفیت ماشین برابر B است و تمامی کارها اندازه‌ای کوچک‌تر یا مساوی ظرفیت ماشین دارند؛
۶. توقف پردازش روی یک انباشته ممکن نیست و پس از شروع پردازش بر دستگاه، هیچ کاری به انباشته اضافه یا از آن کم نمی‌شود؛
۷. موعد تحویل کارها یکسان و برابر d است. موعد تحویل نزدیک[xxiv] در نظر گرفته میشود.
شایان ذکر است موعد تحویل نزدیک مواقعی مطرح میشود که فاصلۀ زمانی تا تحویل سفارش‌ها به مشتری یا مشتریان به‌گونه‌ای است که حتی اگر کار در ابتدای افق برنامه‌ریزی تولید شروع شود، باز هم بخشی از سفارش‌ها با تأخیر مواجه خواهند شد. در مقابل اگر تا زمان موعد تحویل سفارش‌ها، به‌اندازۀ کافی مهلت وجود داشته باشد که همۀ سفارش‌ها بدون تأخیر تولید شود، آنگاه با حالت موعد تحویل دور یا مهلت‌دار مواجه خواهیم بود. براساس نمادگذاری استاندارد مسائل زمان‌بندی (گراهام و همکاران[xxv]، ۱۹۷۹)، مسئلۀ مدنظر در این پژوهش با نماد 1 مشخص و بیان میشود.
با توجه به پژوهش براکر و همکاران[xxvi] (۱۹۹۸)، تمامی مسائل پردازش انباشته‌ای که معیار عملکرد مبتنی بر موعد تحویل دارند، از‌نظر پیچیدگی محاسباتی در طبقۀ NP-hard قرار دارند. از همین روی مسئلۀ بررسی‌شده در این پژوهش نیز NP-hard است.
برخی از شرایط و ویژگی‌های هر زمان‌بندی بهینه برای مسئله، با مفروضات ذکر‌شده در فوق به شرح زیر است (مونخ و همکاران[xxvii]، ۲۰۰۶):
چنانچه در توالی ارائه‌شده برای انباشته‌ها، انباشته‌ای وجود داشته باشد که قبل از موعد تحویل شروع و بعد از موعد تحویل تکمیل شود، انباشتۀ میانی[xxviii] نامیده میشود. در صورت وجود انباشتۀ میانی، اولین انباشته در زمان‌بندی بهینه حتماً در زمان صفر شروع میشود و بازۀ زمان‌بندی بهصورت است.
۳- روش‌شناسی پژوهش
با توجه به NP-hard بودن مسئلۀ بررسی‌شده در این پژوهش، در این بخش الگوریتم‌هایی را برای حل کارایی مسئله بررسی می‌کنیم. به‌طور کلی حل مسئلۀ بررسی‌شده دو مرحلۀ اصلی دارد:
مرحلۀ اول: تشکیل انباشته و تعیین زمان پردازش هر انباشته براساس بزرگ‌ترین زمان پردازش کارهای موجود در آن؛
مرحلۀ دوم: تعیین توالی انباشته‌های تشکیل‌شده برای پردازش بر دستگاه.
در ادامه با توجه به مبانی نظری و مفروضات مطرح‌شده در بخش قبل، ابتدا الگوریتم‌هایی را برای ایجاد انباشته‌ها بررسی می‌کنیم و سپس رویکردهایی برای تعیین توالی انباشته‌های تشکیل‌شده ارائه می‌کنیم. در انتها یک الگوریتم ابتکاری مبتنی بر روش بهبود فردی و همچنین الگوریتم ترکیبی ازدحام ذرات را برای حل کامل مسئله پیشنهاد می‌کنیم.
۳-۱- الگوریتم ابتکاری برای انباشتهسازی
برای یافتن یک زمان‌بندی موجه، ابتدا باید کارها را درون انباشته‌ها قرار داد و سپس توالی قرارگیری انباشته‌ها را روی ماشین تعیین کرد. با توجه به نتایج به دست آمده از پژوهش پارسا و همکاران (۲۰۱۷)، به‌طور کلی الگوریتم‌های ابتکاری مبتنی بر قاعدۀ طولانی‌ترین زمان پردازش برای مسئلۀ حداقل‌سازی مجموع وزنی تعجیل و تأخیر انباشته‌ها جواب بهتری نسبت‌به دیگر الگوریتم‌های ابتکاری ایجاد می‌کنند. از همین روی برای تولید انباشته، از الگوریتم ابتکاری مبتنی بر قاعدۀ LPT به شرح زیر استفاده میشود:
گام 1. کارها به ترتیب نزولی زمان پردازش مرتب میشوند. در صورتی که دو کار دارای زمان پردازش یکسان باشند، براساس ترتیب نزولی اندازه‌شان مرتب میشوند؛
گام 2. اولین کار در ابتدای لیست، انتخاب و در اولین انباشته با ظرفیت خالی قرار می‌گیرد. اگر اندازۀ کار منتخب به‌گونه‌ای بود که در هیچ انباشته‌ای قرار نمی‌گرفت، به یک انباشتۀ جدید تخصیص داده می‌شد. به این روش، قاعدۀ First Fit گفته میشود. گام ۲ تا اختصاص تمام کارها به انباشته‌ها تکرار میشود.
مراحل الگوریتم ابتکاری انباشتهسازی در شکل ۱ نشان داده شده است.
|
شروع |
|
کارها را به ترتیب نزولی زمان پردازششان مرتب کن. |
|
کاری را انتخاب کن که در ابتدای لیست کارها قرار دارد. |
|
با توجه به ظرفیت باقی‌ماندۀ انباشته‌های موجود، کار انتخاب‌شده را در اولین انباشته با ظرفیت کافی قرار بده. |
|
کار انتخاب‌شده را از ابتدای لیست حذف کن. |
|
یک انباشتۀ جدید ایجاد کن و کار انتخاب‌شده را به آن اختصاص بده. |
|
آیا کار انتخاب‌شده در یکی از انباشته‌های موجود جا گرفت؟ |
|
پایان |
|
بله |
|
خیر |
|
بله |
|
خیر |
|
آیا لیست کارها خالی است؟ |
شکل ۱- مراحل اجرای الگوریتم ابتکاری انباشتهسازی
Fig. 1- Flowchart of batch formation algorithm
۳-۲- انباشتهسازی به روش حل مدل ریاضی با هدف کمینه‌سازی زمان تکمیل آخرین انباشته
از‌جمله عوامل مؤثر در رسیدن به جواب بهینه، تشکیل انباشته‌های مناسب از کارهاست. روش انباشتهسازی در الگوریتم ابتکاری این پژوهش، مبتنی بر قاعدۀ LPT است. اما در این بخش، انباشتهسازی از‌طریق حل مدل ریاضی زیر انجام میشود. کاهش تعداد متغیرها در ازای ثابت‌کردن جای انباشته‌ها در توالی، اصلی‌ترین ویژگی این مدل است. با توجه به اینکه کمینه‌سازی معیار عملکرد زمان تکمیل آخرین انباشته ( ) که معادل است، وابسته به ترتیب قرارگیری انباشته‌ها نیست، ثابت‌کردن جای انباشته در توالی، سبب بروز مشکل نمی‌شود. به عبارت دیگر در مسائل زمان‌بندی انباشته با تابع هدف ، تنها کافی است دربارۀ نحوۀ تشکیل انباشته‌ها تصمیم‌گیری شود و پس از تشکیل انباشته‌ها، هر ترتیبی از آنها دارای یکسانی برابر مجموع زمان پردازش انباشته‌ها خواهد بود.
در مسئلۀ بررسی‌شده در این تحقیق ( )، تشکیل انباشتۀ مناسب و جابه‌جایی انباشته‌ها در توالی، عوامل اصلی کمینه‌سازی معیار عملکردند. به همین دلیل امکان حل مدل ریاضی مسئله با معیار عملکرد از این طریق وجود ندارد. بنابراین بعد از تعیین انباشته‌ها از این روش که به حداقل‌شدن زمان تکمیل آخرین انباشته منجر میشود، مجموع وزن‌دار تأخیر و تعجیل‌ها با استفاده از الگوریتم‌های پیشنهادی کمینه میشود.
در این بخش برای انباشتهسازی، از مدل ریاضی ارائه‌شدۀ ترینداده و همکاران (۲۰۱۸) استفاده شده است. به کمک این مدل، انباشته‌ها به‌نحوی تشکیل میشوند که کمینه شود. برای بیان مدل ریاضی، فرض کنید کارها به‌گونه‌ای مرتب شده‌اند که . اگر کار به انباشتۀ اختصاص یابد، متغیر تصمیم صفر و یک مقدار یک خواهد گرفت و در غیر این صورت، صفر خواهد بود. متغیر تنها به ازای تعریف میشود و به عبارت دیگر کار تنها در صورتی به انباشتۀ اختصاص می‌یابد که باشد. انباشتۀ هم در صورتی تشکیل میشود که کار به آن تخصیص یابد. با این نحوۀ تعریف متغیر تصمیم، هم تقارن[xxix] در مدل ریاضی از بین می‌رود و هم تعداد متغیرهای صفر و یک از به کاهش می‌یابد. نکتۀ مهم‌تر این است که این مفروضات به جواب‌هایی منجر میشود که در آن زمان پردازش انباشتۀ k، در صورت استفاده، برابر با خواهد بود؛ زیرا کار k به‌طور حتم به انباشتۀ k اختصاص داده شده است و همچنین کاری است که طولانی‌ترین زمان پردازش را بین کارهای اختصاص‌یافته به آن انباشته دارد. به کمک این متغیرهای تصمیم، مدل ریاضی تشکیل انباشته‌ها بهصورت زیر خواهد بود.
عبارت (۱) بیان‌کنندۀ تابع هدف و معادل کمینه‌سازی زمان تکمیل آخرین انباشته است. دستۀ محدودیت (۲) برای اطمینان از اینکه هر کار دقیقاً به یک انباشته اختصاص می‌یابد، به مدل اضافه شده است. این موضوع که اندازۀ انباشته‌ها نباید از ظرفیت ماشین تجاوز کند، به کمک دسته محدودیت (۳) در نظر گرفته شده است. دسته محدودیت (۴) تضمین می‌کند که تنها در صورت تشکیل انباشتۀ k، این امکان وجود خواهد داشت که کاری به آن تخصیص یابد. عبارت (۵) نیز نوع متغیرهای تصمیم مدل را بیان می‌کند. آزمایش‌های محاسباتی نشان می‌دهد به کمک مدل ریاضی فوق، مسائلی با ۱۰۰ کار یا کمتر روی کامپیوترهای شخصی امروزی به‌راحتی حل میشود.
۳-۳- تعیین توالی انباشته‌ها به کمک الگوریتم برنامه‌ریزی پویا
برنامه‌ریزی پویا الگوریتمی بسیار قدرتمند است که در آن مسئلۀ اصلی از‌طریق تقسیم‌شدن، به مجموعه‌ای از زیرمسئله‌ها حل میشود. حل مسئله با شروع از کوچک‌ترین زیرمسئله شروع میشود و با یافتن جواب‌هایی برای مسائل کوچک در رسیدن ساده‌تر به جواب مسائل بزرگ‌تر ادامه می‌یابد تا زمانی که کل مسئله حل شود. در این بخش یک الگوریتم برنامه‌ریزی پویا را برای تعیین توالی بهینۀ پردازش انباشته‌ها روی ماشین ارائه می‌کنیم. فرض کنید کارها به روشی به انباشته‌ها اختصاص یافته‌اند و تعداد انباشته در اختیار است که توالی پردازش آنها باید مشخص شود. مدت پردازش انباشتۀ را و وزن آن را در نظر بگیرید. با توجه به اینکه موعد تحویل نزدیک است، اولین انباشته در زمان‌بندی بهینه، حتماً در زمان صفر شروع میشود و انباشته‌ها در فاصلۀ زمانی قرار می‌گیرند. همچنین ممکن است انباشته‌ای با شرایط انباشتۀ میانی در زمان‌بندی بهینه وجود داشته باشد. لم زیر، جزییات بیشتری را دربارۀ مشخصات زمان‌بندی بهینه بیان می‌کند.
لم ۱. در زمان‌بندی بهینه، انباشته‌هایی که پیش از موعد تحویل یا هم‌زمان با آن تکمیل میشوند، به ترتیب غیر نزولی تنظیم شده‌اند و انباشته‌هایی که پس از موعد تحویل یا هم‌زمان با آن شروع میشوند، به ترتیب غیر صعودی مرتب شده‌اند. به عبارت دیگر، بدون در نظر گرفتن انباشتۀ میانی، انباشته‌هایی که نسبت وزن به زمان پردازش بیشتری دارند، نزدیک‌تر به موعد تحویل قرار می‌گیرند و هر چقدر از موعد تحویل دور می‌شویم (چه قبل و چه پس از آن)، نسبت وزن به زمان پردازش انباشته‌ها کاهش می‌یابد.
اثبات: با فرض خلف و به کمک انجام جابه‌جایی جفتی دو انباشتۀ مجاور، لم ۱ اثبات میشود. دو انباشتۀ مجاور و را در نظر بگیرید که در زمان‌بندی بهینۀ پیش از موعد تحویل تکمیل میشوند. فرض کنید در زمان‌بندی بهینۀ ، ابتدا انباشتۀ و سپس بلافاصله پس از آن انباشتۀ قرار دارد. را زمان تکمیل انباشتۀ در زمان‌بندی در نظر بگیرید. واضح است که در این صورت زمان تکمیل انباشتۀ برابر خواهد بود. اگر باشد (فرض خلف)، آنگاه با جابه‌جایی جفتی این دو انباشتۀ مجاور و ثابت نگه داشتن توالی بقیۀ انباشته‌ها، زمان‌بندی دیگری به نام به دست می‌آید که مقدار تابع هدف آن کمتر از تابع هدف زمان‌بندی خواهد بود؛ زیرا هزینۀ دو انباشتۀ و در زمان‌بندی معادل و این هزینه در زمان‌بندی برابر است. با توجه به اینکه هزینۀ دیگر انباشته‌ها در هر دو زمان‌بندی و یکسان است، بنابراین تفاوت هزینۀ آنها با برابر است که با توجه به فرض خلف مقداری مثبت است؛ در‌نتیجه زمان‌بندی آن بهینه این نیست که با فرض ما در تناقض است. اثبات برای انباشته‌های پس از موعد تحویل بهصورت مشابه انجام‌شدنی است.
با توجه به لم ۱ و برای تشریح الگوریتم برنامه‌ریزی پویا، فرض کنید انباشته‌ها به ترتیب غیر کاهشی نسبت وزن به زمان پردازششان مرتب شده‌اند؛ به عبارت دیگر . مطابق لم ۱ انتظار داریم انباشته‌های با اندیس کوچک‌تر، دورتر از موعد تحویل و انباشته‌های با اندیس بزرگ‌تر، نزدیک‌تر به موعد تحویل قرار بگیرند. انباشتۀ را انباشتۀ میانی در نظر بگیرید و را معادل مقدار بهینۀ هزینۀ زمان‌بندی c انباشتۀ اول تحت این شرایط قرار دهید که در آن باید مجموع زمان پردازش انباشته‌هایی برابر باشد که پیش از موعد تحویل قرار می‌گیرند. به عبارت دیگر این انباشته باید در بازۀ و قرار بگیرند. انباشته‌هایی که در بازۀ قرار می‌گیرند، دارای تعجیل و انباشته‌های بازۀ دوم دارای تأخیر خواهند بود. رابطۀ بازگشتی برنامه‌ریزی پویا بهصورت زیر بیان میشود:
با فرض آنکه انباشتۀ اول زمان‌بندی‌شده باشند و با توجه به لم ۱، انباشتۀ ام یا باید در انتهای بازۀ اول، یعنی یا در ابتدای بازۀ دوم قرار بگیرد. رابطۀ بازگشتی (۹) هر دو حالت را بررسی و کمترین مقدار را انتخاب می‌کند. رابطۀ (۷) همان رابطۀ (۹) است، در حالتی که بازۀ انباشته‌های دارای تعجیل، یعنی بازۀ به‌اندازۀ کافی فضا برای جای‌دادن انباشتۀ را نداشته و در‌نتیجه فقط بررسی حالت دوم ضروری خواهد باشد. رابطۀ (۸) نیز به همین صورت به حالتی مربوط است که بازۀ انباشته‌های دارای تأخیر، یعنی بازۀ فضای کافی نداشته باشد و انباشتۀ فقط قبل از موعد تحویل قرار بگیرد. رابطۀ (۶) هم به انباشتۀ میانی مربوط است که هزینۀ آن بعداً محاسبه خواهد شد.
روابط بازگشتی فوق ماشین را در بازۀ بیکار نگه می‌دارند تا انباشتۀ میانی در این بازه قرار بگیرد. هزینۀ نهایی با افزودن هزینۀ انباشتۀ میانی ( ) از رابطۀ زیر محاسبه میشود:
جواب بهینه از‌طریق رابطۀ به دست می‌آید. شرایط اولیه نیز بهصورت زیر است:
با توجه به روابط بازگشتی الگوریتم برنامه‌ریزی پویا، تعداد محاسبات لازم و در‌نتیجه زمان لازم برای یافتن جواب بهینه از ردۀ است. پس از تشکیل انباشته‌ها، از الگوریتم برنامه‌ریزی پویای شرح داده شده در این بخش برای تعیین توالی بهینۀ انباشته‌ها استفاده میشود؛ برای مثال یک روش ابتکاری مناسب برای تشکیل انباشته‌ها به کار برده و سپس از برنامه‌ریزی پویا برای تعیین بهترین توالی انباشته‌های تشکیل‌شده استفاده میشود.
۳-۴- ارائۀ یک الگوریتم ابتکاری برای حل مسئله
در این بخش یک الگوریتم ابتکاری را برای حل مسئله ارائه می‌کنیم. در این الگوریتم ابتدا انباشته‌ها به روشی ابتکاری تشکیل و توالی آنها مشخص میشود، سپس جواب تولید‌شده به کمک یک روش بهبود‌دهنده تا جای ممکن، بهبود می‌یابد. در این پژوهش از روش بهبود فردی[xxx] (IE) استفاده شده است که یک روش ساده و پرکاربرد در جست‌وجوی همسایگی‌های یک جواب برای بهبود آن است.
۳-۴-1- روش بهبود فردی
روش بهبود فردی یک روش جست‌وجوی همسایگی است که در آن مجموعه همسایه‌های جواب فعلی، شامل همسایه‌های به طول دو است (کو و همکاران[xxxi]، ۲۰۰۹). فرض کنید و دو بردار مربوط به توالی بهصورت و باشند، چنانچه تعداد مؤلفه‌های متفاوت در این دو جواب k باشد، گفته میشود در یک همسایگی به طول k قرار دارد و برعکس.
در روش IE، ابتدا یک جواب اولیه تولید و سپس در هر مرحله تعدادی جواب همسایه به طول دو ایجاد و مقدار تابع هدف، به ازای جواب‌های همسایۀ جواب جاری محاسبه و مقایسه میشود، در صورتی که بهبودی حاصل شد، جواب همسایه جایگزین جواب فعلی مسئله میشود.
با توجه به اینکه که در مسئلۀ زمان‌بندی ماشین‌های پردازش انباشته، با جابه‌جایی کارهای درون یک انباشته، زمان پردازش انباشته تغییری نمی‌کند، از همسایه‌های ایجادشده به این وسیله صرف‌نظر میشود. از طرفی اگر کارهای انباشته‌های غیریکسان با یک دیگر جابه‌جا شوند، مجموعه‌ای بزرگ از جواب‌ها ایجاد میشود که بسیاری از این جابه‌جایی‌ها به جواب مشابه منجر میشود، از همین روی این نوع جابه‌جایی نیز نادیده گرفته میشود. بنابراین در روش پیشنهادی این پژوهش، تنها معاوضۀ مکان انباشته‌ها در توالی با هم لحاظ میشود. الگوریتم IE، برای حل مسئله از یک جواب اولیه شروع می‌کند. مطابق الگوریتم پیشنهادی در این پژوهش، ابتدا یک الگوریتم ابتکاری، جواب اولیۀ مناسبی را برای الگوریتم IE تولید می‌کند و سپس الگوریتم IE با جابه‌جایی در توالی انباشته‌ها، کیفیت جواب اولیه را تا حد امکان ارتقا می‌دهد. مزیت الگوریتم IE، برای حل مسئلۀ بررسی‌شده در این پژوهش، سهولت در اجرا و قدرت بالای این الگوریتم در بررسی جواب‌های ممکن است.
۳-۴-2- الگوریتم ابتکاری پیشنهادی برای تولید جواب اولیه (HA_IE)
در هر زمان‌بندی بهینه، انباشته‌هایی که قبل یا مقارن با موعد تحویل تکمیل میشوند (مجموعۀ E)، به ترتیب صعودی نسبت هستند و انباشته‌هایی که پس از موعد تحویل شروع و تکمیل میشوند (مجموعه T)، به ترتیب نزولی نسبت قرار دارند. بر این اساس اگر انباشته‌ها به ترتیب صعودی نسبت مرتب شوند، آنگاه اولین انباشته با کمترین مقدار نسبت ، باید در یکی از موقعیت‌های اول یا آخر برنامۀ زمان‌بندی بهینه قرار گیرد. به بیان بهتر، پس از آنکه ترتیب اولیه برای انباشته‌ها براساس افزایش نسبت مشخص شد، اولین انباشته انتخاب و بررسی میشود. آیا قرار‌گرفتن آن در اولین موقعیت، هزینۀ کمتری ایجاد می‌کند یا در آخرین موقعیت؟ سپس انباشتۀ اول در موقعیتی قرار می‌گیرد که هزینۀ کمتری ایجاد کند. پس از اختصاص انباشتۀ اول، روند تعیین توالی برای دیگر انباشته‌ها نیز بر همین اساس خواهد بود. به‌دلیل آنکه موعد تحویل نزدیک (Tight) است و بعد از چند تکرار ممکن است فضای خالی کافی قبل از آن وجود نداشته باشد، بنابراین برای تکرارهایی که در این شرایط صدق می‌کنند، فقط از فضای خالی سمت راست موعد تحویل استفاده میشود (شکل ۲). در پایان شکل بردار توالی، براساس نسبت ، مشابه ˄ خواهد بود.
شکل ۲- نحوۀ قرارگیری انباشته‌ها پس از موعد تحویل
Fig. 2- Arrangement of the batches after the due date
۳-۴-۳- بهبود جواب به کمک الگوریتم IE
در این بخش، چگونگی بهبود کیفیت توالی اولیه به کمک الگوریتم IE تشریح میشود. ایجاد همسایگی در الگوریتم IE، مبتنی بر این شرط است که در زمان‌بندی بهینه حتماً شکل بردار توالی براساس نسبت انباشته‌ها، مشابه ˄ است. بنابراین جابه‌جایی در بردار توالی تنها متناسب با حفظ این شرط انجام میشود و اگر جابه‌جایی چنین شرطی نداشت، اصلاً بررسی نمی‌شود. در ابتدا اولین و دومین انباشته انتخاب میشود، جای آنها در بردار توالی جابه‌جا و در صورت نیاز مقدار معیار عملکرد به ازای این تغییر محاسبه میشود. در مرحلۀ بعد معاوضۀ میان انباشتۀ اول و سوم انجام میشود. روند جابه‌جایی در بردار توالی و محاسبۀ مقدار عملکرد تا آخرین انباشتۀ بردار توالی ادامه می‌یابد. در مرحلۀ بعد از میان کلیه جابه‌جایی‌ها، بهترین جابه‌جایی شناسایی و جابه‌جایی مربوط به آن در بردار توالی اعمال میشود. این روند بعد از این مرحله برای دیگر انباشته‌ها تکرار خواهد شد.
مراحل اجرای الگوریتم پیشنهادی بهصورت زیر است:
۳-۱. انباشته‌ای انتخاب میشود که در ابتدای لیست قرار دارد؛
۳-۲. اولین مکان خالی سمت چپ و آخرین مکان خالی سمت راست موعد تحویل برای تخصیص انباشته بررسی میشود؛ سپس انباشته به موقعیتی اختصاص می‌یابد که هزینۀ کمتری داشته باشد. انباشتۀ اختصاص‌یافته از لیست حذف میشود.
۳-3. اگر هنوز به انتهای لیست نرسیده‌ایم، به گام ۳-۱ برمی‌گردیم.
۴-۱. توالی اولیۀ و مقدار معیار عملکرد به ازای آن محاسبه و برابر قرار داده میشود؛
۴-۲. در توالی به دست آمده از مرحلۀ قبل، مکان دو انباشته معاوضه و در صورت برقراری شرایط لم ۱، توالی مربوطه برابر و مقدار معیار عملکرد در این توالی برابر قرار داده میشود.
۴-۳. اگر رابطۀ برقرار باشد، آنگاه: و .
مراحل اجرای الگوریتم در شکل ۳ نشان داده شده است.
۳-۵- الگوریتم ترکیبی ازدحام ذرات و بهبود فردی (PSO_IE)
در این بخش الگوریتم پیشنهادی مبتنی بر ترکیب الگوریتم‌های بهینه‌سازی ازدحام ذرات (PSO) و بهبود فردی (IE) را معرفی می‌کنیم. با توجه به عملکرد مناسب الگوریتم PSO به‌عنوان یک الگوریتم فراابتکاریِ جمعیت‌محور در حل مسائل زمان‌بندی پردازش انباشته (فاولر و مونخ، ۲۰۲۲)، در این پژوهش از این الگوریتم استفاده شده است. در روش پیشنهادی این بخش، ابتدا الگوریتم PSO، جواب اولیه‌ای برای الگوریتم IE تولید می‌کند و سپس الگوریتم IE با جابه‌جایی در توالی انباشته‌ها، کیفیت جواب‌ها را تا حد امکان ارتقا می‌دهد.
در الگوریتم بهینه‌سازی ازدحام ذرات، بردار بعدی ، موقعیت ذرۀ ام در تکرار ام را مشخص می‌کند و بهصورت بردار تعریف میشود. مؤلفه‌های بردار موقعیت نیز، بیانگر مقدار مؤلفۀ ام در ذرۀ ام و تکرار ام است. الگوریتم ازدحام ذرات با دریافت تعدادی جواب اولیه، شروع به جست‌وجو در فضای شدنی مسئله و جواب‌هایی را به همان شکل اولیه تولید می‌کند. مقادیر اولیه برای مؤلفه‌های بردار موقعیت، از رابطۀ (۱۵) به دست می‌آیند:
شکل ۳ – مراحل اجرای الگوریتم پیشنهادی
Fig. 2- Flowchart of the proposed algorithm
در رابطۀ (۱۵)، عبارات و حدود بالا و پایین اولیه‌ای‌اند که بهصورت پارامتر ورودی الگوریتم تعریف میشوند. همچنین عبارت یک مقدار تصادفی دارای توزیع یکنواخت را در بازۀ اختیار می‌کند. هر ذره برای حرکت‌کردن در فضا، به یک سرعت نیاز دارد. بردار بعدی سرعت ذرۀ ام در تکرار ام را مشخص می‌کند و بهصورت تعریف میشود. مؤلفه‌های بردار سرعت نیز بیانگر مقدار مؤلفۀ ام در ذرۀ ام و تکرار ام است. با افزودن سرعت به موقعیت ذرات، موقعیت‌های جدیدی برای هر ذره در نظر گرفته میشود. برای مقداردهی اولیۀ مؤلفه‌های بردار سرعت از رابطۀ (۱۶) استفاده میشود.
|
(۱۶) |
|
در رابطۀ (۱۶) عبارات و حدود بالا و پایین اولیه‌ای‌اند که برای سرعت ذرات تعریف میشوند. اصولاً الگوریتم ازدحام ذرات برای مسائلی استفاده میشود که فضای حل آنها پیوسته باشد؛ اما در مسئلۀ زمان‌بندی تک ماشین پردازش انباشته با معیار عملکرد حداقل‌سازی تأخیر و تعجیل، همانند بیشتر مسائل زمان‌بندی فضای حل گسسته است. مهم‌ترین مسئله در اجرای الگوریتم PSO برای مسائل زمان‌بندی، پیدا‌کردن یک رابطۀ مناسب بین موقعیت ذرات در الگوریتم PSO و توالی کارها در مسئلۀ زمان‌بندی است. برای انجام این امر، بردار موقعیت ذرات، یک بردار (تعداد کارها) بعدی در نظر گرفته میشود و سپس کارها به ترتیب صعودی مقدار موقعیتشان مرتب میشوند. این قاعده کمترین مقدار موقعیت[xxxii] (SPV) نامیده میشود (جایانتی و آنوسویا، ۲۰۱۷). پس از مشخص‌شدن ترتیب کارها، با توجه به اولویت کارها از قاعدۀ First Fit برای تخصیص کارها به انباشته‌ها استفاده میشود و سپس به کمک الگوریتم IE و با جابه‌جایی توالی انباشته‌ها، کیفیت جواب‌ها تا حد امکان ارتقا می‌یابد.
در الگوریتم PSO استاندارد جواب‌های اولیه بهصورت تصادفی ایجاد میشود؛ اما برای تضمین کیفیت جواب‌های اولیه، در این پژوهش از جواب الگوریتم ابتکاری استفاده میشود که در بخش 3-۴ نیز به‌عنوان یکی از جواب‌ها توضیح داده شده است. در این زمینه نگاشت‌هایی وجود دارند که برای تبدیل توالی کارها به مقادیر پیوستۀ موقعیت ذرات استفاده میشوند. نگاشت زیر برای این تبدیل به کار می‌رود و به کمک آن کاری که در اولویت ام قرار دارد، به مؤلفۀ مکانی نگاشت میشود:
|
(۱۷) |
|
دیگر جزییات الگوریتم PSO_IE پیشنهادی شامل نحوۀ به‌روز‌کردن سرعت و موقعیت ذرات همانند یک الگوریتم ازدحام ذرات در حالت عمومی آن است که به‌‌جهت اختصار از ذکر آنها پرهیز میشود.
۴- یافته‌ها
قدم اول برای تولید مسائل نمونه، تعیین مقادیر برای پارامترهای مورد نیاز این مسائل است. برای ایجاد این مسائل از روش به کار گرفته شدۀ پارسا و همکاران (۲۰۱۷) استفاده شده است. در جدول ۲ نحوۀ تولید مقادیر استفادهشده در این پژوهش نشان داده شده است. موعد تحویل مشترک کارها نیز با توجه به روش پیشنهادی هووگوین و ون د ولد (۱۹۹۱) بهصورت تصادفی یکنواخت در بازۀ تولید شده است.
برای اعتبارسنجی الگوریتم برنامه‌ریزی پویا، جواب‌های به دست آمده از این روش با نتایج حل مدل ریاضی ارائه‌شدۀ پارسا و همکاران (۲۰۱۷) مقایسه شده است. نکتۀ حائز اهمیت آن است که احتمالاً مدل ریاضی در هر مرحله از تکرارهای خود، انباشته‌های جدیدی را برای بهینه‌سازی معیار عملکرد تولید می‌کند، اما انباشته‌ها در الگوریتم برنامه‌ریزی پویا ثابت‌اند و تنها یک مرتبه ساخته میشوند. از همین روی در جدول ۳ ظرفیت انباشته و اندازۀ کارها یکسان فرض شده است تا مقایسه در حالت کاملاً برابر ارزیابی شود که البته این فرض تناقضی با هیچ‌یک از مفروضات مطرح‌شده ندارد و تنها حالت خاصی از مسئله است. در تمامی این نمونه‌ها، اندازۀ انباشته و کارها برابر 40 فرض شده است.
|
40
|
|||||
در نتایج حاصل از جدول ۳ نشان داده شده است که در صورت یکسان‌بودن انباشته‌ها، جواب الگوریتم برنامه‌ریزی پویا دقیقاً با جواب حاصل از حل مدل ریاضی برابر است.
در ادامه نتایج حاصل از حل مسائل نمونه و مقایسۀ جواب‌های به دست آمده از الگوریتم‌های پیشنهادی با الگوریتم برنامه‌ریزی پویا ارائه میشود. به‌منظور ارزیابی الگوریتم‌های پیشنهادی از شاخص درصد انحراف نسبی (RPD) مطابق رابطۀ (۱۸) استفاده شده است.
|
(۱۸) |
|
در رابطۀ فوق، نشان‌دهندۀ مقدار تابع هدف جواب حاصل از الگوریتم پیشنهادی و بیانگر مقدار تابع هدف به دست آمده از الگوریتم برنامه‌ریزی پویاست. در هر رده دو نمونه و در‌مجموع ۶۰ نمونه مسئله بهصورت تصادفی تولید و به کمک الگوریتم‌های پیشنهادی حل شده است. عملکرد الگوریتم ابتکاری (HA_IE) و الگوریتم ترکیبی ازدحام ذرات (PSO_IE) بهصورت مجزا، نسبت‌به الگوریتم برنامه‌ریزی پویا (DP) مقایسه و نتایج در جدول ۴ گزارش شده است.
|
اندازۀ کارها |
تعداد کارها |
متوسط نتایج |
|
درصد انحراف نسبی (RPD) |
|||
|
DP |
HA_IE |
PSO_IE |
|
HA_IE |
PSO_IE |
||
|
|
20 |
1476 |
1484 |
1479 |
|
5/0 |
2/0 |
|
40 |
7375 |
7658 |
7432 |
|
8/3 |
7/0 |
|
|
60 |
16012 |
16458 |
16250 |
|
7/2 |
4/1 |
|
|
100 |
19852 |
20026 |
19937 |
|
8/0 |
4/0 |
|
|
200 |
207339 |
208922 |
208550 |
|
7/0 |
5/0 |
|
|
|
20 |
693 |
716 |
693 |
|
3/3 |
0/0 |
|
40 |
4505 |
4528 |
4510 |
|
5/0 |
1/0 |
|
|
60 |
10950 |
11192 |
11042 |
|
2/2 |
8/0 |
|
|
100 |
28890 |
29229 |
29103 |
|
1/1 |
3/0 |
|
|
200 |
134623 |
135888 |
135395 |
|
9/0 |
5/0 |
|
|
|
20 |
2195 |
2279 |
2236 |
|
8/3 |
8/1 |
|
40 |
8889 |
9096 |
8998 |
|
3/2 |
2/1 |
|
|
60 |
20343 |
20749 |
20589 |
|
9/1 |
2/1 |
|
|
100 |
45773 |
46536 |
46234 |
|
6/1 |
0/1 |
|
|
200 |
206861 |
219551 |
218830 |
|
1/6 |
7/5 |
|
|
|
20 |
890 |
890 |
890 |
|
0/0 |
0/0 |
|
40 |
2246 |
2250 |
2246 |
|
1/0 |
0/0 |
|
|
60 |
4955 |
4975 |
4963 |
|
4/0 |
1/0 |
|
|
100 |
8664 |
8711 |
8681 |
|
5/0 |
1/0 |
|
|
200 |
10574 |
10844 |
10778 |
|
5/2 |
0/2 |
|
زمان حل الگوریتم‌های پیشنهادی بر‌حسب ثانیه، به تفکیک در جدول ۵ ارائه شده است.
|
اندازۀ کارها |
تعداد کارها |
الگوریتم HA_IE |
الگوریتم PSO_IE |
الگوریتم برنامه‌ریزی پویا |
|
|
20 |
028/0 |
03/0 |
243/1 |
|
40 |
057/0 |
064/0 |
507/2 |
|
|
60 |
54/0 |
6/0 |
852/3 |
|
|
100 |
6/0 |
7/0 |
967/8 |
|
|
200 |
62/1 |
2 |
551/70 |
|
|
|
20 |
026/0 |
035/0 |
88/0 |
|
40 |
047/0 |
052/0 |
928/0 |
|
|
60 |
08/0 |
094/0 |
274/1 |
|
|
100 |
164/0 |
182/0 |
76/6 |
|
|
200 |
874/0 |
9/0 |
585/48 |
|
|
|
20 |
035/0 |
05/0 |
377/0 |
|
40 |
603/0 |
071/0 |
546/7 |
|
|
60 |
156/0 |
212/0 |
031/16 |
|
|
100 |
218/0 |
27/0 |
485/23 |
|
|
200 |
578/1 |
81/1 |
66 |
|
|
|
20 |
007/0 |
0083/0 |
248/0 |
|
40 |
016/0 |
021/0 |
343/0 |
|
|
60 |
031/0 |
046/0 |
78/0 |
|
|
100 |
07/0 |
078/0 |
842/2 |
|
|
200 |
233/0 |
274/0 |
29/7 |
۵- بحث
برای مقایسۀ آماری نتایج به دست آمده از حل مسائل مختلف به‌وسیلۀ سه الگوریتم پیشنهادی، که در جدول ۴ نشان داده شده است، از آزمون تحلیل واریانس یک طرفه استفاده می‌کنیم. بر این اساس، چنانچه مقدار عبارت P-value، برای تک عامل بررسی‌شده (هر الگوریتم یک سطح از عامل فرض میشود) از سطح معناداری آزمون ( ) کمتر باشد، فرض صفر آزمون یعنی برابری میانگین نتایج به دست آمده از حل مسئله به سه روش، رد میشود و در غیر این صورت دلیلی بر تفاوت نتایج الگوریتم‌ها وجود نخواهد داشت. برای انجام این آزمون، نرم‌افزار Minitab 17 به کار گرفته و نتایج حاصل در جدول ۶ گزارش شده است.
|
P-Value |
F-Value |
میانگین مربعات خطا (Adj MS) |
مجموع مربعات خطا (Adj SS) |
درجۀ آزادی (DF) |
منبع تغییرات |
|
۹۹۹/۰ |
۰۰/۰ |
۵۱۱۴۱۹۰ |
۱۰۲۲۸۳۸۰ |
۲ |
الگوریتم |
|
|
|
۴۴۲۴۷۶۸۰۳۵ |
۱۱+E۵۲۲۱۲/۲ |
۵۷ |
خطا |
|
|
|
|
۱۱+E۵۲۲۲۲/۲ |
۵۹ |
کل |
با توجه به نتایج آماری به دست آمده از جدول ۶، به‌وضوح مشخص میشود که فرض برابری میانگین حاصل از حل مسائل با استفاده از سه الگوریتم ردشدنی نیست. بر همین اساس الگوریتم‌های پیشنهادی، عملکرد مشابهی با الگوریتم برنامه‌ریزی پویا دارند.
تحلیل نتایج مربوط به زمان حل الگوریتم‌ها، که در جدول ۵ ارائه شد، نیز حاکی از آن است که حل مسئله به‌وسیلۀ الگوریتم‌های HA_IE و PSO_IE در بیشتر موارد در کسری از ثانیه انجام‌شدنی است. هر‌چند الگوریتم برنامه‌ریزی پویا به تلاش محاسباتی بیشتری برای یافتن جواب بهینه نیاز دارد و زمان حل با این الگوریتم هنگامی که تعداد انباشته‌ها زیاد شود، بهصورت چشمگیری افزایش می‌یابد. بر همین اساس و با توجه به نتایج آماری جدول ۶، الگوریتم‌های ابتکاری پیشنهادی با صرف زمان کمتر از عملکرد مناسبی برخوردارند و در عمل از این الگوریتم‌ها برای کاربردهای واقعی و در ابعاد بزرگ استفاده میشود.
در ادامه تأثیر روش انباشتهسازی را تحلیل می‌کنیم. روش استفادهشده به این شرح است که ابتدا مدل ریاضی بخش ۳-۲ حل میشود و انباشته‌هایی با حداقل زمان تکمیل آخرین انباشته ( ) تعیین میشوند، سپس با استفاده از الگوریتم برنامه‌ریزی پویا، توالی بهینۀ این انباشته‌ها به دست می‌آید. در مقابل از الگوریتم ابتکاری ارائه‌شده در بخش ۳-۱ برای تشکیل انباشته‌ها استفاده و نتایج با حالت قبل مقایسه میشود تا میزان تفاوت این دو رویکرد مشخص شود. برای مقایسۀ تأثیر نحوۀ انباشتهسازی و همچنین تغییر اندازۀ کارها بر جواب مسئله، آزمایشی با شرایط جدول 7 انجام شده است. در این آزمایش، تعداد 20 مسئلۀ تصادفی به‌وسیلۀ الگوریتم برنامه‌ریزی پویا حل شده است. برای سنجش اثربخشی این عوامل و برهم‌کنش میان آنها از تحلیل واریانس دو طرفه استفاده شده است.
|
پارامتر |
مقدار |
|
تعداد کل کار ( ) |
۲۰ |
|
اندازۀ کارها ( ) |
توزیع یکنواخت ، توزیع یکنواخت |
|
زمان پردازش کارها ( ) |
توزیع یکنواخت |
|
ظرفیت انباشته ( ) |
40 |
|
نحوۀ انباشتهسازی |
روش 1. استفاده از مدل ریاضی، روش 2. استفاده از الگوریتم ابتکاری انباشتهسازی |
|
سطح معناداری ( ) |
05/0 |
نتایج حاصل از تحلیل آماری، در جدول ۸ نشان داده شده است. در خروجی نرم‌افزار، اگر مقدار مشخص‌شده با P-Value برای هر عامل و اثر متقابل آنها کمتر از مقدار معناداری ( ) باشد، آنگاه فرض صفر آزمون یعنی اثر اصلی حاصل از تغییر عوامل (نحوۀ انباشتهسازی و اندازۀ کارها) و اثر متقابل آنها بر مقدار پاسخ (مقدار تابع هدف) در آزمون رد میشود.
براساس نتایج به دست آمده از تحلیل واریانس دوطرفه، تغییر نحوۀ انباشتهسازی با دو روش یاد‌شده، دارای تأثیر کمی در جواب به دست آمده است. به بیان دیگر در نمونه‌های آزمایش‌شده، انباشته‌های ساخته‌شده براساس قاعدۀ LPT، تفاوت چشمگیری با انباشته‌های تولید‌شده به کمک مدل ریاضی معرفی‌شده ندارند؛ اما در مقابل تغییر اندازۀ کارها قویاً بر جواب مؤثر است. همچنین اثر متقابل میان این دو عامل نیز وجود ندارد. بنابراین الگوریتم ابتکاری پیشنهادی برای انباشتهسازی از کارایی لازم برخوردار است و در ابعاد بزرگ مسئله، که امکان حل دقیق آن وجود ندارد، به‌عنوان یک جایگزین مناسب از آن استفاده میشود.
|
P-Value |
F-Value |
میانگین مربعات خطا (MS) |
مجموع مربعات خطا (SS) |
درجۀ آزادی (DF) |
منبع تغییرات |
|
۵۳۱/۰ |
۴۱/۰ |
۴۶۱ |
۴۶۱ |
۱ |
نحوۀ انباشتهسازی |
|
۰۰۰/۰ |
۴۸/۸۲ |
۹۲۴۸۰ |
۹۲۴۸۰ |
۱ |
اندازۀ کارها |
|
۹۵۸/۰ |
۰۰/۰ |
۳ |
۳ |
۱ |
نحوۀ انباشتهسازی*اندازۀ کارها |
|
|
|
۱۱۲۱ |
۱۷۹۴۰ |
۱۶ |
خطا |
|
|
|
|
۱۱۰۸۸۴ |
۱۹ |
کل |
۶- نتیجه‌گیری
در این پژوهش، مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با اندازۀ کارهای غیریکسان و معیار کمینه‌سازی مجموع وزنی تأخیر و تعجیل کارها با در نظر گرفتن موعد تحویل نزدیک بررسی شد. همچنین الگوریتمی مبتنی بر رویکرد برنامه‌ریزی پویا توسعه و الگوریتم‌های ابتکاری مبتنی بر بهبود فردی برای حل مسئله پیشنهاد شد. همچنین روش ترکیبی مبتنی بر الگوریتم ازدحام ذرات برای حل مسئله در ابعاد بزرگ توسعه داد شد. در پایان با بررسی نمونۀ مسئله‌های متفاوت، عملکرد الگوریتم‌ها با یکدیگر مقایسه شد. بررسی نتایج به دست آمده از حل مسائل نمونه، عملکرد خوبی برای الگوریتم‌های پیشنهادی در یافتن جواب مسئله، در زمان پذیرفتنی را نشان می‌دهد. همچنین بررسی دو روش بررسی‌شده برای انباشتهسازی کارها، یکی مبتنی بر یک روش ابتکاری و دیگری به کمک حل یک مدل ریاضی، نشان داد که تفاوت چشمگیری بین این دو روش وجود ندارد. بنابراین در صورت لزوم بدون از دست رفتن کیفیت جواب، از روش ابتکاری استفاده میشود که زمان حل کوتاه‌تری دارد. همچنین یک الگوریتم برنامه‌ریزی پویا برای تعیین توالی انباشته‌ها با هدف تحقق تولید بهنگام ارائه شد. در ادامه یک الگوریتم ابتکاری و یک الگوریتم فراابتکاری بر مبنای الگوریتم ازدحام ذرات برای حل کامل مسئله ارائه شد. الگوریتم برنامه‌ریزی پویا به تلاش محاسباتی زیادی نیاز دارد و زمان حل با این الگوریتم هنگامی که تعداد انباشته‌ها زیاد شود، بهصورت چشمگیری افزایش می‌یابد. هر‌چند نتایج به دست آمده حاکی از آن است که الگوریتم‌های ابتکاری پیشنهادی با صرف زمان کمتر از عملکرد مناسبی برخوردارند و در عمل از این الگوریتم‌ها برای کاربردهای واقعی و در ابعاد بزرگ استفاده میشود. متوسط انحراف نسبی الگوریتم ازدحام ذرات پیشنهادی کمتر از ۱درصد و مقدار این شاخص برای الگوریتم ابتکاری ارائه‌شده ۷۸/۱درصد است.
حوزۀ زمان‌بندی دربارۀ ماشین‌های پردازندۀ انباشته و ادغام آن با موضوع تولید بهنگام، با توجه به نیاز روزافزون صنایع به افزایش سرعت و کاهش هزینه‌ها از‌جمله حوزه‌های مطالعاتی کاربردی و جذاب است. بر همین اساس زمینه‌های مطالعاتی برای انجام، با گسترش ایده‌هایی چون تغییر مفروضات اساسی مسئله نظیر وجود زمان دسترسی برای کارها، تغییر نوع ماشین پردازندۀ انباشته به حالت سری و موارد دیگر، پیشنهاد میشود. توسعۀ روش‌هایی برای یافتن حد پایین مسئله و سپس استفاده از این روش‌ها در بدنۀ الگوریتم‌های حل دقیق مسئله، یکی دیگر از زمینه‌های مطالعاتی برای آینده است. در نظر گرفتن تعرفه‌های متفاوت برای هزینه‌های انرژی طی ساعات مختلف روز، پیشنهاد کاربردی دیگری است که جای مطالعه دارد. همچنین بررسی مسئله با در نظر گرفتن الزامات زیست‌محیطی مانند کاهش انتشار دی اکسید کربن، از‌نظر کاربردهای عملی جذاب است.
[i] Sen et al.
[ii] Baker and Scudder
[iii] Hoogeveen and van de Velde
[iv] Hall et al.
[v] Nearchou and Omirou
[vi] Particle Swarm Optimization (PSO)
[vii] Jayanthi and Anusuya
[viii] Ikura and Gimple
[ix] Li et al.
[x] Parsa et al.
[xi] Longest Processing Time (LPT)
[xii] Zhang et al.
[xiii] Trindade et al.
[xiv] Queiroga et al.
[xv] Pessoa et al.
[xvi] Time-indexed formulation
[xvii] Yang et al.
[xviii] Branch and price
[xix] Kong et al.
[xx] Tian and Zheng
[xxi] Zheng and Chen
[xxii] Fowler and Mönch
[xxiii] Loose due date
[xxiv] Tight due date
[xxv] Graham et al.
[xxvi] Brucker et al.
[xxvii] Mönch et al.
[xxviii] Straddling Batch
[xxix] Symmetry
[xxx] Individual Enhancement
[xxxi] Kuo et al.
[xxxii] Shortest Position Value (SPV)
)