
تعداد نشریات | 43 |
تعداد شمارهها | 1,685 |
تعداد مقالات | 13,846 |
تعداد مشاهده مقاله | 32,779,881 |
تعداد دریافت فایل اصل مقاله | 12,962,290 |
زمانبندی یک ماشین پردازش انباشته در راستای تحقق تولید بهنگام با در نظر گرفتن موعد تحویل نزدیک | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
پژوهش در مدیریت تولید و عملیات | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مقاله 6، دوره 15، شماره 1 - شماره پیاپی 36، فروردین 1403، صفحه 89-112 اصل مقاله (520.31 K) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
نوع مقاله: مقاله پژوهشی | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
شناسه دیجیتال (DOI): 10.22108/pom.2024.136793.1500 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
طاها کشاورز* 1؛ حمید رضا زرآبادی پور2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1استادیار گروه مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه سمنان، سمنان، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2کارشناس ارشد گروه مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه یزد، یزد، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
توسعه و پیچیدگی بازارهای جدید از یکسو و محدودیتهای اقتصادی از سوی دیگر، سبب شدهاند تا توجه به دو اصل ارائۀ خدمات مطلوب و کاهش هزینهها به ضرورتی اجتنابناپذیر تبدیل شوند. نگرش تولید بهنگام، ازجمله رویکردهای مناسب برای موازنۀ میان دو اصل یادشده است. همچنین، طی دو دهۀ اخیر، به موضوع تعیین توالی و زمانبندی عملیات در سیستمهای تولید انباشتهای بهطور وسیعی توجه شده است. دستگاه پردازش انباشتهای، همزمان یک انباشته را از کارها پردازش میکند و این امر سبب کاهش زمان تنظیم دستگاه و همچنین تسهیل در امر مدیریت جریان مواد میشود. هدف پژوهش حاضر، کمینهسازی مجموع وزنی تعجیل و تأخیر کارهایی با اندازۀ غیر یکسان بر ماشین پردازش انباشته، با لحاظکردن موعد تحویل نزدیک به زمان شروع زمانبندی و در راستای تحقق تولید بهنگام است. در این تحقیق دو رویکرد برای انباشتهسازی کارها، یکی مبتنی بر یک روش ابتکاری و دیگری مبتنی بر حل یک مدل ریاضی، بررسی شده است؛ سپس توالی انباشتهها به کمک یک الگوریتم برنامهریزی پویا برای تحقق تولید بهنگام، تعیین شده است. همچنین یک الگوریتم ابتکاری و یک الگوریتم فراابتکاری بر مبنای الگوریتم ازدحام ذرات برای حل کامل مسئله ارائه شده است. نتایج محاسباتی حاکی از آن است که متوسط انحراف نسبی الگوریتم ازدحام ذرات پیشنهادی، کمتر از ۱درصد و مقدار این شاخص برای الگوریتم ابتکاری ارائهشده ۷۸/۱درصد است. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
کلیدواژهها | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ماشین پردازش انباشته؛ تولید بهنگام؛ موعد تحویل نزدیک؛ برنامهریزی پویا؛ الگوریتم ابتکاری؛ الگوریتم ازدحام ذرات | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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] (۲۰۲۲) طی یک مقالۀ مروری، پیشینۀ موضوع زمانبندی پردازش انباشته را بهصورت جامع بررسی کردهاند. آنها پژوهشهای گذشته را با توجه به محیط ماشینآلات و نوع تابع هدف دستهبندی و دربارۀ روندهای تحقیقات آتی بحث کردهاند. i. جدول 1- مقایسۀ تحقیق حاضر با دیگر تحقیقات شاخص در این حوزه1. Table 1- Comparison of the current research with other leading research in this field
با نگاهی هرچند اجمالی دربارۀ پیشینۀ موضوع، درمییابیم که بررسی همزمان مسئلههای تولید بهنگام و پردازش انباشته تاکنون کمتر بررسی شده است. بهتازگی پارسا و همکاران (۲۰۱۷) پژوهشی را در زمینۀ این دو حوزه، با در نظر گرفتن موعد تحویل دور[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 پیشنهادی شامل نحوۀ بهروزکردن سرعت و موقعیت ذرات همانند یک الگوریتم ازدحام ذرات در حالت عمومی آن است که بهجهت اختصار از ذکر آنها پرهیز میشود. ۴- یافتهها قدم اول برای تولید مسائل نمونه، تعیین مقادیر برای پارامترهای مورد نیاز این مسائل است. برای ایجاد این مسائل از روش به کار گرفته شدۀ پارسا و همکاران (۲۰۱۷) استفاده شده است. در جدول ۲ نحوۀ تولید مقادیر استفادهشده در این پژوهش نشان داده شده است. موعد تحویل مشترک کارها نیز با توجه به روش پیشنهادی هووگوین و ون د ولد (۱۹۹۱) بهصورت تصادفی یکنواخت در بازۀ تولید شده است. ii.iii. جدول 2- پارامترهای مسائل نمونه1. Table 2- Parameters of the instance problemsبرای اعتبارسنجی الگوریتم برنامهریزی پویا، جوابهای به دست آمده از این روش با نتایج حل مدل ریاضی ارائهشدۀ پارسا و همکاران (۲۰۱۷) مقایسه شده است. نکتۀ حائز اهمیت آن است که احتمالاً مدل ریاضی در هر مرحله از تکرارهای خود، انباشتههای جدیدی را برای بهینهسازی معیار عملکرد تولید میکند، اما انباشتهها در الگوریتم برنامهریزی پویا ثابتاند و تنها یک مرتبه ساخته میشوند. از همین روی در جدول ۳ ظرفیت انباشته و اندازۀ کارها یکسان فرض شده است تا مقایسه در حالت کاملاً برابر ارزیابی شود که البته این فرض تناقضی با هیچیک از مفروضات مطرحشده ندارد و تنها حالت خاصی از مسئله است. در تمامی این نمونهها، اندازۀ انباشته و کارها برابر 40 فرض شده است. iv. جدول ۳- اعتبارسنجی الگوریتم برنامهریزی پویا1. Table 3- Validation of the dynamic programming algorithm
در نتایج حاصل از جدول ۳ نشان داده شده است که در صورت یکسانبودن انباشتهها، جواب الگوریتم برنامهریزی پویا دقیقاً با جواب حاصل از حل مدل ریاضی برابر است. در ادامه نتایج حاصل از حل مسائل نمونه و مقایسۀ جوابهای به دست آمده از الگوریتمهای پیشنهادی با الگوریتم برنامهریزی پویا ارائه میشود. بهمنظور ارزیابی الگوریتمهای پیشنهادی از شاخص درصد انحراف نسبی (RPD) مطابق رابطۀ (۱۸) استفاده شده است.
در رابطۀ فوق، نشاندهندۀ مقدار تابع هدف جواب حاصل از الگوریتم پیشنهادی و بیانگر مقدار تابع هدف به دست آمده از الگوریتم برنامهریزی پویاست. در هر رده دو نمونه و درمجموع ۶۰ نمونه مسئله بهصورت تصادفی تولید و به کمک الگوریتمهای پیشنهادی حل شده است. عملکرد الگوریتم ابتکاری (HA_IE) و الگوریتم ترکیبی ازدحام ذرات (PSO_IE) بهصورت مجزا، نسبتبه الگوریتم برنامهریزی پویا (DP) مقایسه و نتایج در جدول ۴ گزارش شده است. v. جدول ۴- سنجش عملکرد الگوریتمهای پیشنهادی1. Table 4- Evaluating the performance of the proposed algorithms
زمان حل الگوریتمهای پیشنهادی برحسب ثانیه، به تفکیک در جدول ۵ ارائه شده است.
vi.vii. جدول ۵- زمان انجام محاسبات با الگوریتمها برحسب ثانیه1. Table 5- Computational time of the algorithms (s)
۵- بحث برای مقایسۀ آماری نتایج به دست آمده از حل مسائل مختلف بهوسیلۀ سه الگوریتم پیشنهادی، که در جدول ۴ نشان داده شده است، از آزمون تحلیل واریانس یک طرفه استفاده میکنیم. بر این اساس، چنانچه مقدار عبارت P-value، برای تک عامل بررسیشده (هر الگوریتم یک سطح از عامل فرض میشود) از سطح معناداری آزمون ( ) کمتر باشد، فرض صفر آزمون یعنی برابری میانگین نتایج به دست آمده از حل مسئله به سه روش، رد میشود و در غیر این صورت دلیلی بر تفاوت نتایج الگوریتمها وجود نخواهد داشت. برای انجام این آزمون، نرمافزار Minitab 17 به کار گرفته و نتایج حاصل در جدول ۶ گزارش شده است. viii. جدول ۶- تحلیل واریانس نتایج الگوریتمها به ازای1. Table 6- Analysis of variance based on results of algorithms ( 0.05)
با توجه به نتایج آماری به دست آمده از جدول ۶، بهوضوح مشخص میشود که فرض برابری میانگین حاصل از حل مسائل با استفاده از سه الگوریتم ردشدنی نیست. بر همین اساس الگوریتمهای پیشنهادی، عملکرد مشابهی با الگوریتم برنامهریزی پویا دارند. تحلیل نتایج مربوط به زمان حل الگوریتمها، که در جدول ۵ ارائه شد، نیز حاکی از آن است که حل مسئله بهوسیلۀ الگوریتمهای HA_IE و PSO_IE در بیشتر موارد در کسری از ثانیه انجامشدنی است. هرچند الگوریتم برنامهریزی پویا به تلاش محاسباتی بیشتری برای یافتن جواب بهینه نیاز دارد و زمان حل با این الگوریتم هنگامی که تعداد انباشتهها زیاد شود، بهصورت چشمگیری افزایش مییابد. بر همین اساس و با توجه به نتایج آماری جدول ۶، الگوریتمهای ابتکاری پیشنهادی با صرف زمان کمتر از عملکرد مناسبی برخوردارند و در عمل از این الگوریتمها برای کاربردهای واقعی و در ابعاد بزرگ استفاده میشود. در ادامه تأثیر روش انباشتهسازی را تحلیل میکنیم. روش استفادهشده به این شرح است که ابتدا مدل ریاضی بخش ۳-۲ حل میشود و انباشتههایی با حداقل زمان تکمیل آخرین انباشته ( ) تعیین میشوند، سپس با استفاده از الگوریتم برنامهریزی پویا، توالی بهینۀ این انباشتهها به دست میآید. در مقابل از الگوریتم ابتکاری ارائهشده در بخش ۳-۱ برای تشکیل انباشتهها استفاده و نتایج با حالت قبل مقایسه میشود تا میزان تفاوت این دو رویکرد مشخص شود. برای مقایسۀ تأثیر نحوۀ انباشتهسازی و همچنین تغییر اندازۀ کارها بر جواب مسئله، آزمایشی با شرایط جدول 7 انجام شده است. در این آزمایش، تعداد 20 مسئلۀ تصادفی بهوسیلۀ الگوریتم برنامهریزی پویا حل شده است. برای سنجش اثربخشی این عوامل و برهمکنش میان آنها از تحلیل واریانس دو طرفه استفاده شده است. ix. جدول ۷- مقادیر پارامترهای مسائل نمونه1. Table 7- Parameters value of the instance problems
نتایج حاصل از تحلیل آماری، در جدول ۸ نشان داده شده است. در خروجی نرمافزار، اگر مقدار مشخصشده با P-Value برای هر عامل و اثر متقابل آنها کمتر از مقدار معناداری ( ) باشد، آنگاه فرض صفر آزمون یعنی اثر اصلی حاصل از تغییر عوامل (نحوۀ انباشتهسازی و اندازۀ کارها) و اثر متقابل آنها بر مقدار پاسخ (مقدار تابع هدف) در آزمون رد میشود. براساس نتایج به دست آمده از تحلیل واریانس دوطرفه، تغییر نحوۀ انباشتهسازی با دو روش یادشده، دارای تأثیر کمی در جواب به دست آمده است. به بیان دیگر در نمونههای آزمایششده، انباشتههای ساختهشده براساس قاعدۀ LPT، تفاوت چشمگیری با انباشتههای تولیدشده به کمک مدل ریاضی معرفیشده ندارند؛ اما در مقابل تغییر اندازۀ کارها قویاً بر جواب مؤثر است. همچنین اثر متقابل میان این دو عامل نیز وجود ندارد. بنابراین الگوریتم ابتکاری پیشنهادی برای انباشتهسازی از کارایی لازم برخوردار است و در ابعاد بزرگ مسئله، که امکان حل دقیق آن وجود ندارد، بهعنوان یک جایگزین مناسب از آن استفاده میشود. x. جدول ۸- نتایج آزمون آماری برای سنجش تأثیر نحوۀ انباشتهسازی و اندازۀ کارها به ازای1. Table 8- Results of statistical test for evaluating the effect of batching and job size ( 0.05)
۶- نتیجهگیری در این پژوهش، مسئلۀ زمانبندی یک ماشین پردازندۀ انباشته با اندازۀ کارهای غیریکسان و معیار کمینهسازی مجموع وزنی تأخیر و تعجیل کارها با در نظر گرفتن موعد تحویل نزدیک بررسی شد. همچنین الگوریتمی مبتنی بر رویکرد برنامهریزی پویا توسعه و الگوریتمهای ابتکاری مبتنی بر بهبود فردی برای حل مسئله پیشنهاد شد. همچنین روش ترکیبی مبتنی بر الگوریتم ازدحام ذرات برای حل مسئله در ابعاد بزرگ توسعه داد شد. در پایان با بررسی نمونۀ مسئلههای متفاوت، عملکرد الگوریتمها با یکدیگر مقایسه شد. بررسی نتایج به دست آمده از حل مسائل نمونه، عملکرد خوبی برای الگوریتمهای پیشنهادی در یافتن جواب مسئله، در زمان پذیرفتنی را نشان میدهد. همچنین بررسی دو روش بررسیشده برای انباشتهسازی کارها، یکی مبتنی بر یک روش ابتکاری و دیگری به کمک حل یک مدل ریاضی، نشان داد که تفاوت چشمگیری بین این دو روش وجود ندارد. بنابراین در صورت لزوم بدون از دست رفتن کیفیت جواب، از روش ابتکاری استفاده میشود که زمان حل کوتاهتری دارد. همچنین یک الگوریتم برنامهریزی پویا برای تعیین توالی انباشتهها با هدف تحقق تولید بهنگام ارائه شد. در ادامه یک الگوریتم ابتکاری و یک الگوریتم فراابتکاری بر مبنای الگوریتم ازدحام ذرات برای حل کامل مسئله ارائه شد. الگوریتم برنامهریزی پویا به تلاش محاسباتی زیادی نیاز دارد و زمان حل با این الگوریتم هنگامی که تعداد انباشتهها زیاد شود، بهصورت چشمگیری افزایش مییابد. هرچند نتایج به دست آمده حاکی از آن است که الگوریتمهای ابتکاری پیشنهادی با صرف زمان کمتر از عملکرد مناسبی برخوردارند و در عمل از این الگوریتمها برای کاربردهای واقعی و در ابعاد بزرگ استفاده میشود. متوسط انحراف نسبی الگوریتم ازدحام ذرات پیشنهادی کمتر از ۱درصد و مقدار این شاخص برای الگوریتم ابتکاری ارائهشده ۷۸/۱درصد است. حوزۀ زمانبندی دربارۀ ماشینهای پردازندۀ انباشته و ادغام آن با موضوع تولید بهنگام، با توجه به نیاز روزافزون صنایع به افزایش سرعت و کاهش هزینهها ازجمله حوزههای مطالعاتی کاربردی و جذاب است. بر همین اساس زمینههای مطالعاتی برای انجام، با گسترش ایدههایی چون تغییر مفروضات اساسی مسئله نظیر وجود زمان دسترسی برای کارها، تغییر نوع ماشین پردازندۀ انباشته به حالت سری و موارد دیگر، پیشنهاد میشود. توسعۀ روشهایی برای یافتن حد پایین مسئله و سپس استفاده از این روشها در بدنۀ الگوریتمهای حل دقیق مسئله، یکی دیگر از زمینههای مطالعاتی برای آینده است. در نظر گرفتن تعرفههای متفاوت برای هزینههای انرژی طی ساعات مختلف روز، پیشنهاد کاربردی دیگری است که جای مطالعه دارد. همچنین بررسی مسئله با در نظر گرفتن الزامات زیستمحیطی مانند کاهش انتشار دی اکسید کربن، ازنظر کاربردهای عملی جذاب است.
[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) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Baker, K. R., & Scudder, G. D. (1990). Sequencing with earliness and tardiness penalties: a review. Operations Research, 38(1), 22-36. http://www.jstor.org/stable/171295 Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & Van De Velde, S. L. (1998). Scheduling a batching machine. Journal of scheduling, 1(1), 31-54. https://doi.org/10.1002/(SICI)1099-1425(199806)1:1%3C31::AID-JOS4%3E3.0.CO;2-R Fowler, J. W., & Mönch, L. (2022). A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research, 298(1), 1-24. https://doi.org/10.1016/j.ejor.2021.06.012 Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics, 5(1), 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X Hall, N. G., Kubiak, W., & Sethi, S. P. (1991). Earliness–tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Operations Research, 39(5), 847-856. https://doi.org/10.1287/opre.39.5.847 Hoogeveen, H., & van de Velde, S. (1991). Scheduling around a small common due date. European Journal of Operational Research, 55(2), 237-242. https://doi.org/10.1016/0377-2217(91)90228-N Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61-65. https://doi.org/10.1016/0167-6377(86)90104-5 Jayanthi, S., & Anusuya, S. (2017). Minimization of Total Weighted Earliness and Tardiness using PSO for One Machine Scheduling. International Journal of Pure and Applied Mathematical Sciences, 10(1) , 35-44. Kong, M., Wang, W., Deveci, M., Zhang, Y., Wu, X., & Coffman, D. M. A. (2023). Novel carbon reduction engineering method-based deep Q-learning algorithm for energy-efficient scheduling on a single batch-processing machine in semiconductor manufacturing. International Journal of Production Research, 1-24. https://doi.org/10.1080/00207543.2023.2252932 Kuo, I.-H., Horng, S.-J., Kao, T.-W., Lin, T.-L., Lee, C.-L., Terano, T., & Pan, Y. (2009). An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model. Expert systems with applications, 36(3), 7027-7032. https://doi.org/10.1016/j.eswa.2008.08.054 Li, Z., Chen, H., Xu, R., & Li, X. (2015). Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes. Computers & Industrial Engineering, 87(1), 590-599. https://doi.org/10.1016/j.cie.2015.06.008 Mönch, L., Unbehaun, R., & Choung, Y. I. (2006). Minimizing earliness–tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint. OR Spectrum, 28(2), 177-198. https://doi.org/10.1007/s00291-005-0013-4 Nearchou, A. C., & Omirou, S. L. (2013). A particle swarm optimization algorithm for scheduling against restrictive common due dates. International Journal of Computational Intelligence Systems, 6(4), 684-699. https://doi.org/10.1080/18756891.2013.802874 Parsa, N. R., Karimi, B., & Husseini, S. M. (2017). Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system. Computers & Operations Research, 80(1), 173-183. https://doi.org/10.1016/j.cor.2016.12.001 Pessoa, A. A., Bulhões, T., Nesello, V., & Subramanian, A. (2022). Exact approaches for single machine total weighted tardiness batch scheduling. INFORMS Journal on Computing, 34(3), 1512-1530. https://doi.org/10.1287/ijoc.2021.1133 Queiroga, E., Pinheiro, R. G. S., Christ, Q., Subramanian, A., & Pessoa, A. A. (2021). Iterated local search for single machine total weighted tardiness batch scheduling. Journal of Heuristics, 27(3), 353-438. https://doi.org/10.1007/s10732-020-09461-x Sen, T., Sulek, J. M., & Dileepan, P. (2003). Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey. International journal of production economics, 83(1), 1-12. https://doi.org/10.1016/S0925-5273(02)00265-7 Tian, Z., & Zheng, L. (2024). Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches. European Journal of Operational Research, 312(2), 512-524. https://doi.org/10.1016/j.ejor.2023.07.012 Trindade, R. S., de Araújo, O. C. B., & Fampa, M. (2021). Arc-flow approach for single batch-processing machine scheduling. Computers & Operations Research, 134, 1-16. https://doi.org/10.1016/j.cor.2021.105394 Trindade, R. S., de Araújo, O. C. B., Fampa, M. H. C., & Müller, F. M. (2018). Modelling and symmetry breaking in scheduling problems on batch processing machines. International journal of production research, 56(22), 7031-7048. https://doi.org/10.1080/00207543.2018.1424371 Yang, F., Davari, M., Wei, W., Hermans, B., & Leus, R. (2022). Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families. European Journal of Operational Research, 303(2), 602-615. https://doi.org/10.1016/j.ejor.2022.03.027 Zhang, H., Wu, F., & Yang, Z. (2021). Hybrid approach for a single-batch-processing machine scheduling problem with a just-in-time objective and consideration of non-identical due dates of jobs. Computers & Operations Research, 128, 105194. https://doi.org/10.1016/j.cor.2020.105194 Zheng, X., & Chen, Z. (2024). An improved deep Q-learning algorithm for a trade-off between energy consumption and productivity in batch scheduling. Computers & Industrial Engineering, 188, 109925. https://doi.org/10.1016/j.cie.2024.109925 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
آمار تعداد مشاهده مقاله: 226 تعداد دریافت فایل اصل مقاله: 175 |