نوع مقاله : مقاله پژوهشی
نویسندگان
1 کارشناس ارشد دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان، اصفهان، ایران
2 استاد دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان، اصفهان، ایران
3 استادیار دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان، اصفهان، ایران
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
Purpose: In recent years, significant energy consumption and facing global warming have led to concern worldwide. Therefore, governments have turned to deterrent actions such as imposing daily tariffs in different intervals to tackle energy consumption. This article addresses unrelated parallel machine energy-efficient scheduling problems by considering sequence-independent setup times and energy consumption tariffs. The objective function is that jobs should be assigned to machines and processed in different intervals so that the cost of consumed energy becomes as less as possible. It should be noted that the assumed sequence-independent setup times are addressed in two different modes, setup times jointed to processing time and setup times disjointed from processing time.
Design/methodology/approach: To optimize the total energy consumption cost in unrelated parallel machine scheduling problems with sequence-independent setup times jointed to processing time and disjointed from processing time, mixed-integer linear programming (MILP) models have been proposed from two different points of view. The first model has been formulated according to the predecessor jobs of a special job, while the second model has been conducted based on the immediate predecessor job. Also, a fix and relax heuristic (FRH) algorithm has been conducted to solve large-scale instances. All mathematical models and the heuristic algorithm have been coded in the Visual C# 2017 environment and implemented using the CPLEX 12.8 Concert Technology on a PC with 32GB RAM and Intel Corei7 4.0 GHz CPU (4 cores). Also, a sizeable number of instances have been solved to evaluate the efficiency of mathematical models and the heuristic algorithm and to ensure their accuracy.
Findings: According to numerical analysis, both mathematical models solved the instances of up to 20 jobs and 80 machines optimally for sequence-independent setup-times jointed to processing time, and sequence-independent disjointed from processing time problems. However, generally speaking, the mathematical model based on predecessor jobs was more efficient than another mathematical model, especially in terms of run time. Moreover, the proposed fix and relax-based heuristic algorithm solved instances of up to 20 machines and 190 jobs for the disjointed setup times problem, and up to 20 and 220 instances for the jointed setup times problem. It should be noted that all instances were generated analogously to the literature.
Research limitations/implications: A vast number of exogenous factors contributed to the scheduling problems in the real world, which can disturb the scheduling process easily, frequent power outages, machine breakdown, and operator absence. Besides, considering all the real world's possibilities raises extreme complexity in problems. Therefore, similar to other studies, some assumptions were considered as follows:
machines are always available at all times;
idle is allowable for machines;
the energy consumption rate of various machines is different for each job;
each machine's energy consumption rate during processing and setups is different for each job, it is assumed as constant;
preemption is not allowed in the job's processing and setups;
all jobs are available at the beginning of the planning horizon; and
each machine can process or do the setup for only one job at a time.
Practical implications: Given that unrelated parallel machines are one of the most practical scheduling environments, this article can be effective in production sites and operation lines that contain such a kind of machine. Besides, unrelated parallel machines cover identical and related parallel machines. Consequently, this paper is the building blocks of cost-effective and environmentally friendly scheduling programs. Also, the application of unrelated parallel machines is not merely restricted to production problems. In other words, unrelated parallel machine scheduling problems can be used in other real-world cases, such as airplane scheduling and elevator scheduling.
Originality/value - In this paper, unrelated parallel machine energy-efficient scheduling has been addressed considering sequence-independent setup times. Since it was a common belief that sequence-independent setup times could be included in processing times, sequence-independent setup times have been neglected so far. However, in this innovative study for the first time, an unrelated parallel machine energy efficient problem was investigated with sequence-independent setup times. Mathematical programming models and a heuristic algorithm were proposed for such a practical problem.
کلیدواژهها [English]
انرژی ازلحاظ حفظ پایداری زندگی و جامعه، اهمیت زیادی دارد. با توجه به اعلام سازمان جهانی انرژی، تا سال 2040، تقاضای جهانی برای انرژی 37% افزایش خواهد یافت (وو[i] و چه[ii]، 2019).
راههای مختلفی برای کاهش هزینههای انرژی وجود دارد؛ بهعنوان نمونه، جایگزینکردن وسایل فرسوده که مقدار مصرف آنها بیش از حد استاندارد است با وسایلی که مصرف انرژی کمتری دارد. این جایگزینی به هزینۀ زیادی نیاز دارد و بنابراین در اکثر موارد امکانپذیر نیست. در این مقاله روشی دیگر ارائه میشود که به هزینۀ زیادی نیاز ندارد و تنها با یک برنامهریزی مناسب اجرایی است. زمانبندی کارای انرژی (EES[iii])، روشی است که در این مقاله برای مصرف کارای انرژی از آن استفاده میشود. در صنایع مختلف، ماشینآلات زیادی وجود دارد که کارهای مشابه را با سرعتهای متفاوت انجام میدهد که با نام ماشینهای موازی غیر مرتبط[iv] شناخته میشود. سرعتهای مختلف ماشینهای موازی غیر مرتبط، باعث ایجاد مصرف انرژی متفاوت آنها میشود؛ ازاینرو، پیداکردن یک توالی و زمانبندی مناسب که کارهای با میزان مصرف انرژی متفاوت را بر ماشینها قرار دهد، اهمیت زیادی دارد.
یکی از فرضیات مهم در مسائل زمانبندی، درنظرگرفتن زمانهای آمادهسازی بهمنظور واقعیترشدن تصمیمات است. زمانهای آمادهسازی، شامل زمانهای آمادهسازی ماشین، پردازش و آمادهسازی قطعات لازم برای پردازش محصول اصلی است که عملاً شامل آمادهکردن تجهیزات، قراردادن محصول در مکان مدنظر، آمادهکردن و بستن فیکسچرها و تمیزکاری پیش از پردازش است. در بسیاری از مواقع، آمادهسازی هر کار مستقل از توالی در نظر گرفته میشود و بنابراین میتوان آن را به مدتزمان پردازش اضافه کرد؛ اما با وجود مصرف انرژی، این فرض صحیح نیست؛ زیرا در مسائل کارای انرژی در دست بررسی، میزان مصرف انرژی ماشینها هنگام انجام آمادهسازیها، میتواند با میزان مصرف انرژی ماشینها هنگام پردازش کارها متفاوت باشد؛ بنابراین نمیتوان آمادهسازی یک کار را با زمان پردازش آن جمع کرد. ازاینرو باید زمان آمادهسازی هر کار، بهصورت یک مؤلفۀ جداگانه از زمان پردازش آن در نظر گرفته شود تا بتوان مقدار انرژی مصرفشده را بهدرستی محاسبه کرد.
از طرف دیگر، یکی از رایجترین شیوههای محاسبۀ قیمت انرژی، درنظر گرفتن آن بهصورت تعرفهای (TOU[v]) است؛ به این معنی که افق زمانی، به تعداد معینی دوره تقسیمبندی میشود که هزینۀ مصرف انرژی در هرکدام از دورهها متفاوت است؛ بنابراین اگر در این شرایط اقدام به پردازش کارها شود، لازم است زمانبندی طوری صورت گیرد که هدف بهینهسازی انرژی محقق شود. با توجه به مطالب ذکرشده در این مقاله، یک مسئلۀ زمانبندی ماشینهای موازی غیر مرتبط، با زمانهای آمادهسازی مستقل از توالی بررسی میشود که هدف آن، کمینهکردن کل هزینۀ انرژی مصرفی است. این مسئله تاکنون در پیشینۀ موضوع مشاهده نشده است؛ بنابراین سعی میشود، این خلأ در این مقاله برطرف شود. در ادامۀ مقاله در بخش دوم، به مرور پیشینۀ مرتبط با زمانهای آمادهسازی در ماشینهای موازی غیر مرتبط و همچنین زمانبندی کارای انرژی در ماشینهای موازی پرداخته میشود. در بخش سوم به تعریف مسئله و بیان فرضیات پرداخته میشود. مدلهای برنامهریزی عدد صحیح مختلط مسائل موردبررسی، در بخش چهارم ارائه خواهد شد. در بخش پنجم به ارائۀ الگوریتم ابتکاری برای هرکدام از مسائل پرداخته میشود. نتایج محاسباتی حاصل از اجرای مدلها و الگوریتمهای ابتکاری نیز در بخش پنجم ارائه خواهد شد. در انتها مطالب، نتیجهگیری و جمعبندی و پیشنهادهایی برای تحقیقات آتی ارائه میشود.
با توجه به اهمیت زیاد بهینهسازی مصرف انرژی در اکثر محیطهای زمانبندی، مطالعاتی دربارۀ بهبود مصرف انرژی صورت گرفته است. مطالعاتی را که برای این قسمت، انتخاب و بررسی شده است، در سه دستۀ زیر قسمتبندی میشود:
الهوردی[vi] و سروش[vii] (2008) انواع آمادهسازیها، کاربرد آنها و اهمیت درنظر گرفتن آنها را در زمانبندی معرفی کردند؛ همچنین آنها در این پژوهش، به معرفی زمانهای آمادهسازی، اعم از مستقل از توالی و وابسته به توالی در محیطهای تکماشین، ماشینهای موازی و کارگاه گردشکاری پرداختند. والادا[viii] و رویز[ix] (2012) برای مسئلۀ زمانبندی ماشینهای موازی غیر مرتبط با زمانهای آمادهسازی وابسته به توالی و هدف کمینهکردن مجموع دیرکرد و زودکرد وزندار کل، دو نوع مدل برنامهریزی ریاضی را تحت عناوین مدل دواندیسه و سهاندیسه ارائه کردند. آنها با انجام آزمایشهای عددی نشان دادند، در ابعاد حدی، مدل دواندیسه نسبتبه مدل سهاندیسه عملکرد بهتری دارد؛ همچنین برای حل مسائل در ابعاد بزرگتر نیز، یک الگوریتم ژنتیک ارائه کردند.
جیا[x] و همکاران (2017) برای اولین بار از الگوریتم بهینهسازی اجتماع مورچگان[xi]، برای حل مسئلۀ پردازش دستهای کارها بر ماشینهای موازی، با اهداف کمینهکردن مقدار انرژی مصرفشده و دامنۀ عملیات، با درنظر گرفتن سیاست تعرفۀ مصرف انرژی استفاده کردند. بهمنظور نشاندادن کارایی الگوریتم ارائهشده، آنها نتایج حاصل از انجام آزمایشهای عددی بر دادههای تصادفی را با نتایج بهدستآمده از الگوریتم NSGA[xii]-Ⅱ مقایسه کردند؛ همچنین نقاط مرز پارتو را نیز به دست آوردند. الگوریتم آنها قادر به حل مسائل با 100 کار، 5 ماشین و 12 دوره است.
تان[xiii] و همکاران (2018) مسئلۀ زمانبندی کارای انرژی برای پردازش دستهای کارها، بر ماشینهای موازی با سیاست تعرفۀ مصرف انرژی را بهصورت بهینه حل کردند. چنگ[xiv] و همکاران (2017) نیز مدل ارائهشده توسط دینگ[xv] و همکاران (2015) را بهبود دادند. ژوو[xvi] و همکاران (2018) مسئلۀ پردازش کارهای دستهای را بر ماشینهای موازی، با اهداف کمینهکردن مقدار انرژی مصرفشده و دامنۀ عملیات، با سیاست درنظر گرفتن تعرفۀ انرژی بررسی کردند. آنها با بهکارگیری الگوریتم تکامل دیفرانسیلی، مسائل تا 300 کار، 5 ماشین و 6 دوره را حل کردند و نقاط مرز پارتو را نیز به دست آوردند. وو و چه (2019) مسئلۀ زمانبندی کارای انرژی برای ماشینهای موازی غیر مرتبط را بررسی کردند. آنها با بهکارگیری الگوریتم تکامل دیفرانسیلی ممتیک (MDE[xvii])، مسائل با 7000 کار و 200 ماشین را حل کردند. شایان ذکر است، آنها از سیاست انرژی متفاوت کارها بهمنظور بهینهسازی مصرف انرژی استفاده کردند و نقاط مرزی پارتو را نیز به دست آوردند.
رمضانیان[xviii] و همکاران (2019) مسئلۀ زمانبندی کارای انرژی کارگاه گردشکاری جایگشتی را با زمانهای آمادهسازی وابسته به توالی بررسی کردند. آنها برای این مسئله، یک مدل ریاضی عدد صحیح مختلط دوهدفه ارائه کردند که توابع هدف آن، کمینهکردن دامنۀ عملیات و مقدار انرژی مصرفشده است؛ همچنین در این مقاله با انجام مطالعۀ موردی بیان کردند که روش آنها میتواند بهطور متوسط، 15% مصرف انرژی را کاهش دهد. جیانگ[xix] و وانگ[xx] (2019) نیز مسئلۀ زمانبندی کارای انرژی کارگاه گردشکاری جایگشتی را با زمانهای آمادهسازی وابسته به توالی بررسی کردند. آنها علاوه بر انرژی مصرفشده برای انجام آمادهسازی و پردازش کارها، انرژی مصرفشده برای انتقال کارها از انبار مواد اولیه به اولین ماشین و از آخرین ماشین به انبار محصول نهایی، انرژی لازم برای انتقال کارها بین ماشینها و همچنین انرژی مصرفشده هنگام بیکاری ماشین را نیز در نظر گرفتند. نحوۀ درنظر گرفتن انرژی هنگام انجام آمادهسازیها در پژوهش جیانگ و وانگ (2019)، به این صورت است که ماشینها برای انجام آمادهسازی با میزانی متفاوت از پردازش کارها انرژی مصرف میکنند. آنها علاوه بر مدل ریاضی، برای این مسئله یک الگوریتم چندهدفۀ بهبودیافتۀ تکاملی، مبتنی بر تجزیه (IMOEAD[xxi]) نیز ارائه کردند. آزمایشهای عددی در پژوهش آنها برای نمونههای کوچک، بر دادههای واقعی صورت گرفته است و برای نمونههای بزرگ نیز، از دادههای تصادفی استفاده کردهاند.
ژو[xxii] و همکاران (2020) مسئلۀ زمانبندی کارای انرژی تکدستهای را با زمانهای آزادسازی، بهصورت تعرفهای بررسی کردند. توابع هدف مدنظر در این مقاله، شامل کمینهکردن هزینۀ انرژی کل و دامنۀ عملیات بوده است. برای این مسئله، ژو و همکاران (2020) یک مدل ریاضی و همچنین یک الگوریتم فراابتکاری را برای بهدست آوردن مرز پارتو ارائه کردند. در همان سال اوزتوپ[xxiii] و همکاران (2020)، مسئلۀ دو هدفۀ زمانبندی کارای انرژی کارگاه گردشکاری جایگشتی را بررسی کردند. در این پژوهش فرض بر این است که هر ماشین میتواند در سرعتهای مختلف، کارها را پردازش و انرژی مصرف کند. توابع هدف مدنظر در این مقاله، شامل کمینهکردن کل انرژی مصرفی و زمان جریان کل است. آنها علاوه بر مدل ریاضی، چندین الگوریتم ابتکاری نیز ارائه کردند که قادر به حل نمونههای با 20 ماشین و 50 کار است. سایر پژوهشهای انجامشده دربارۀ موضوع زمانبندی کارای انرژی، همراه با مشخصههای اصلی آنها مانند محیط زمانبندی، نوع زمانهای آمادهسازی، نحوۀ درنظرگرفتن انرژی و ارائۀ مدل ریاضی در جدول 1 نیز ارائه شده است.
جدول 1- خلاصۀ نوآوری مقالات پیشینۀ موضوع
|
مرجع |
نوآوری |
||||
|
ماشینهای موازی غیر مرتبط |
ارائۀ مدل ریاضی |
ارائۀ الگوریتم ابتکاری یا فراابتکاری |
نوع آمادهسازی |
تعرفۀ مصرف انرژی بهصورت دورهای |
|
|
والادا و رویز (2012) |
ü |
ü |
ü |
وابسته به توالی |
- |
|
دینگ و همکاران (2015) |
ü |
ü |
ü |
- |
ü |
|
زیدی و محمدحسینی (2015) |
ü |
ü |
ü |
- |
- |
|
آوالوس روزالس و همکاران (2015) |
ü |
ü |
ü |
وابسته به توالی |
- |
|
چه و همکاران (2017) |
ü |
ü |
ü |
- |
ü |
|
چنگ و همکاران (2017) |
ü |
ü |
- |
- |
ü |
|
ژو و همکاران (2018) |
ü |
ü |
ü |
- |
ü |
|
وانگ و همکاران (2018) |
- |
- |
ü |
- |
ü |
|
تان و همکاران (2018) |
ü |
ü |
- |
- |
ü |
|
فانجول-پیرو و همکاران (2019) |
ü |
ü |
ü |
وابسته به توالی |
- |
|
رمضانیان و همکاران (2019) |
- |
ü |
ü |
وابسته به توالی |
- |
|
ژو و لیو (2019) |
- |
ü |
ü |
وابسته به توالی |
- |
|
ابیکرم و همکاران (2019) |
ü |
ü |
- |
- |
- |
|
وو و چه (2019) |
ü |
- |
ü |
- |
- |
|
صابری و همکاران (2020) |
ü |
ü |
ü |
- |
ü |
|
ژانگ و همکاران (2021) |
- |
- |
ü |
وابسته به توالی |
- |
|
مقالۀ حاضر |
ü |
ü |
ü |
مستقل از توالی |
ü |
مقالۀ حاضر را میتوان توسعۀ پژوهش صابری و همکاران (2020) در نظر گرفت که در آن فرض آمادهسازی کارها بهمنظور تطبیق بیشتر با شرایط دنیای واقعی، اضافه شده است. به این ترتیب نوآوری این مقاله، درنظر گرفتن فرض زمان آمادهسازی مستقل از توالی در محیط ماشینهای موازی، در حالت وجود تعرفۀ متفاوت مصرف انرژی در بازههای زمانی مختلف است. در ادامه برای این مسئله، مدل ریاضی و همچنین الگوریتم ابتکاری ارائه میشود.
هدف اصلی مقاله، بررسی مسئلۀ زمانبندی کارای انرژی ماشینهای موازی غیر مرتبط با زمانهای آمادهسازی مستقل از توالی است؛ به این معنی که برای مسئلۀ نامبرده، مدلهای ریاضی و همچنین الگوریتم ابتکاری ارائه شود که کارها به ماشینها طوری تخصیص پیدا کند و روی هر ماشین چیده شود که مقدار کل هزینۀ انرژی مصرفشده برای پردازش و انجام آمادهسازی کارها حداقل شود.
مسئلۀ فوق از آنجا مطرح میشود که در محیطهای کارگاهی، عدم توجه به تخصیص و تعیین توالی مناسب کارها روی ماشینها و در عین وجود زمان آمادهسازی برای کارها در روی ماشینها و بدون توجه به تعرفۀ متفاوت مصرف انرژی در بازههای زمانی مختلف، میتواند به هزینههای زیاد مصرف انرژی برای تولیدکننده منجر شود. ازاینرو، بررسی این مسئله میتواند به کاهش هزینههای تولید و قیمت تمامشده کمک کند. بر این اساس فرض میشود، تعداد معینی کار و تعدادی ماشین موازی غیر مرتبط وجود دارد که کارها باید روی ماشینها پردازش شود. هر کار برای انجام پردازش، به آمادهسازی مستقل از توالی نیاز دارد. ماشینها برای پردازش کارها و همچنین انجام آمادهسازی به انرژی نیاز دارند. میزان مصرف انرژی برای آمادهسازی و پردازش هر کار روی هر ماشین متفاوت است. نحوۀ درنظر گرفتن قیمت انرژی در این مقاله بهصورت تعرفهای است؛ همچنین یک ضربالاجل برای اتمام کلیۀ کارها در نظر گرفته شده است، این ضربالاجل، در قالب تعیین تعداد مشخصی دوره با هزینۀ مصرف انرژی معین بیان شده است. زمانهای آمادهسازی موردبررسی در این پژوهش، در دو حالت منفصل از پردازش و متصل به پردازش بررسی میشود. در حالت آمادهسازی منفصل از پردازش، ممکن است فاصلهای بین آمادهسازی و پردازش یک کار قرار گیرد؛ البته در برخی حالات در دنیای واقع نیاز است، اتمام آمادهسازی و شروع پردازش به هم متصل باشد و وقفهای بین آنها نباشد که در ادامه از آن با عنوان آمادهسازی متصل به پردازش یاد میشود. بهطور کلی در این مقاله، دو نوع مسئلۀ زمانبندی کارای انرژی ماشینهای موازی غیر مرتبط با زمانهای آمادهسازی منفصل از پردازش (PDS[xxiv]) و مستقل از توالی متصل به پردازش (PJS[xxv]) بررسی میشود.
فرضیات مسائل بهصورت زیر است:
برای تعیین پیچیدگی مسائل موردبررسی، اگر مقدار آمادهسازیها برابر صفر فرض شود، آنگاه هرکدام از مسائل PDS و PJS به مسئلۀ بدون آمادهسازی کاهش مییابد. با توجه به اینکه دینگ و همکاران (2015) نشان دادند این مسئله به شدت NP- hard است؛ بنابراین مسائل PDS و PJS نیز به شدت NP- hard هستند.
برای هرکدام از مسائل PDS و PJS، دو مدل برنامهریزی عدد صحیح مختلط ارائه شده است که در ادامه توضیح داده میشود. مدلهای مسئلۀ PDS بهصورت PDSM_1 و PDSM_2 نامگذاری میشوند و مدلهای مسئلۀ PJS با انجام اصلاحات لازم بر مدلهای متناظر در مسئلۀ PDS ایجاد و بهترتیب PJSM_1 و PJSM_2 نامیده میشوند. پارامترها و متغیرهای تصمیم مورد استفاده، برای ارائۀ این مدلها بهصورت زیر هستند:
|
N |
تعداد کارها |
|
|
M |
تعداد ماشینها |
|
|
K |
تعداد دورهها |
|
|
|
مدتزمان پردازش کار j روی ماشین i |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
مدتزمان آمادهسازی کار j روی ماشین i |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
هزینۀ مصرف انرژی در دورۀ k |
k= 1, 2, …, K |
|
|
طول دورۀ k |
k= 1, 2, …, K |
|
|
میزان مصرف انرژی پردازش کار j روی ماشین i |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
میزان مصرف انرژی آمادهسازی کار j روی ماشین i |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
اگر کار j روی ماشین i پردازش شود، برابر 1 و در غیر این صورت برابر صفر |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
اگر قسمتی از پردازش کار j در دورۀ k انجام شود، برابر 1 و در غیر این صورت برابر صفر |
k= 1, 2, …, K; j= 1, 2, …, N
|
|
|
اگر قسمتی از آمادهسازی کار j در دورۀ k انجام شود، برابر 1 و در غیر این صورت برابر صفر |
k= 1, 2, …, K; j= 1, 2, …, N
|
|
|
اگر روی ماشین یکسان، کار j قبل از کار h پردازش شود، برابر یک و در غیر این صورت برابر صفر |
j= 1, 2, …, N; h= 1, 2, …, N; j h |
|
|
قسمتی از مدتزمان پردازش کار j روی ماشین i در دورۀ k |
i= 1, 2, …, M; j= 1, 2, …, N k= 1, 2, …, K |
|
|
قسمتی از مدتزمان آمادهسازی کار j روی ماشین i در دورۀ k |
i= 1, 2, …, M; j= 1, 2, …, N k= 1, 2, …, K |
تابع هدف و محدودیتهای مدل PDSM_1 که براساس رابطۀ تقدم و تأخر بین کارها ارائه میشود، مطابق روابط (1) تا (18) است.
|
(PDSM_1) |
|||
|
(1) |
|
|
Min |
|
|
|
s.t. |
|
|
(2) |
j= 1, 2, …, N |
|
|
|
(3) |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
|
(4) |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
|
(5) |
i= 1, 2, …, M; k= 1, 2, …, K |
|
|
|
(6) |
j= 1, 2, …, N; h= 1, 2, …, N; j i= 1, 2, …, M |
|
|
|
(7) |
j= 1, 2, …, N; h= 1, 2, …, N; j k= 2, 3, …, K |
|
|
|
(8) |
k= 2, 3, …, K; j= 1, 2, …, N |
|
|
|
(9) |
k= 1, 2, …, K; j= 1, 2, …, N |
|
|
|
(10) |
k= 1, 2, …, K; j= 1, 2, …, N |
|
|
|
(11) |
k= 1, 2, …, K; j= 1, 2, …, N |
|
|
|
(12) |
k= 1, 2, …, K; j= 1, 2, …, N |
|
|
|
(13) |
k= 2, 3, …, K-1; j= 1, 2, …, N |
|
|
|
(14) |
k= 1, 2, …, K-2; j= 1, 2, …, N |
|
|
|
(15) |
k= 2, 3, …, K-1; j= 1, 2, …, N |
|
|
|
(16) |
k= 1, 2, …, K-2; j= 1, 2, …, N |
|
|
|
(17) |
i= 1, 2, ..., M; k= 1, 2, ..., K j= 1, 2, …, N; h= 1, 2, …, N; j |
|
|
|
(18) |
i= 1, 2, ..., M; j= 1, 2, ..., N k= 1, 2, ..., K |
|
|
در مدل PDSM_1، رابطۀ (1) تابع هدف مسئله است و نشاندهندۀ مقدار کل هزینۀ انرژی مصرفی است که باید حداقل شود. رابطۀ (2) تضمین میکند، هر کار باید دقیقاً به یک ماشین تخصیص داده شود. برای اینکه تکههای مختلف پردازش و آمادهسازی هر کار در دورههای مختلف، فقط به یک ماشین تخصیص پیدا کند، روابط (3) و (4) منظور شده است؛ همچنین روابط (3) و (4) بیان میکنند، جمع قسمتهای مختلف پردازش و آمادهسازی هر کار در دورههای مختلف، باید برابر مدتزمان پردازش و آمادهسازی آن کار روی ماشین مربوطه باشد. رابطۀ (5) تضمین میکند، میزان اشغال هر دوره نباید از طول آن دوره تجاوز کند. رابطۀ (6) بیان میکند، تقدم بین کارها با ماشینی هماهنگ باشد که به آن تخصیص داده میشود؛ به این معنی که یک کار موقعی میتواند قبل از کار دیگری پردازش شود که هر دو به یک ماشین تخصیص پیدا کند. رابطۀ (7) بیان میکند، اگر روی ماشین i کار j قبل از کار h انجام شود، آنگاه در همۀ دورههای قبل از کار j نباید هیچ قسمتی از پردازش و آمادهسازی کار h انجام شود؛ به عبارت دیگر، برای اینکه بین آمادهسازی و پردازش یک کار، بخشی از آمادهسازی یا پردازش کار دیگری قرار نگیرد، روابط (6) و (7) منظور شدهاند. همچنین بهمنظور اینکه آمادهسازی هر کار قبل از پردازش آن انجام شود، رابطۀ (8) منظور شده است.
روابط (9) و (10) بهترتیب بیان میکنند، اگر قسمتی از پردازش یک کار در دورهای انجام شود، آنگاه متغیر مربوط به تخصیص آن کار، به آن دوره مقدار یک میگیرد و اگر هیچ قسمتی از پردازش آن در دورهای انجام نشد، مقدار صفر اختیار میکند. بهطور مشابه روابط (11) و (12) نیز بیان میکنند، اگر قسمتی از آمادهسازی یک کار در دورهای انجام شود، آنگاه متغیر مربوط به تخصیص آمادهسازی آن کار به آن دوره برابر یک میشود و در غیر این صورت، مقدار صفر اختیار میکند. رابطۀ (13) بیان میکند، اگر قسمتی از پردازش کار j در دورههای k-1 و k+1 انجام شد، آنگاه باید پردازش کار jتمام دوره kرا پوشش دهد. رابطۀ (14) بیان میکند، اگر قسمتی از پردازش کار j در دورهای انجام شد و در دورۀ بعدی انجام نشد، آنگاه نباید هیچ جزئی از پردازش کار j در دورههای بعدی انجام شود؛ به بیان دیگر میتوان گفت، روابط (13) و (14) باعث جلوگیری از انقطاع پردازش کارها میشوند. به طریق مشابه، روابط (15) و (16) از انقطاع آمادهسازی جلوگیری میکنند. روابط (17) و (18) نشاندهندۀ نوع و دامنۀ متغیرهای تصمیم هستند. مقدار پارامتر در روابط (14) و (16)، برابر K-k-1 در نظر گرفته شده است.
برای ارائۀ مدل PDSM_2 به تمام پارامترها و متغیرهای مورد استفاده در مدل PDSM_1 نیاز است؛ با این تفاوت که در مدل PDSM_2 به جای متغیر از متغیر استفاده میشود که تعریف آن بهصورت زیر است:
|
|
اگر روی ماشین i کار j بلافاصله قبل از کار h پردازش شود، برابر یک و در غیر این صورت برابر صفر است. |
j= 1, 2, …, N; h= 1, 2, …, N j i= 1, 2, …, M |
مدل PDSM_2 براساس تقدم و تأخر، بلافاصله قبل و یا بعد ارائه میشود و بنابراین هر کار، باید دارای یک کار بلافاصله قبل باشد و این امکان برای کار اولی فراهم نیست که روی هر ماشین قرار میگیرد؛ بنابراین در مدل PDSM_2 علاوه بر کارهای اصلی، به یک کار مجازی نیاز است که با اندیس 0 نشان داده میشود. فرمولبندی مدل PDSM_2 به قرار زیر است:
|
(PDSM_2) |
|||
|
(19) |
|
|
Min |
|
|
|
s.t. |
|
|
(16) ،(15) ،(14) ،(13) ،(12) ،(11) ،(10) ،(9) ،(8)، (5) ،(4) ،(3) ،(2) |
|||
|
(20) |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
|
(21) |
i= 1, 2, …, M; h= 1, 2, …, N |
|
|
|
(22) |
i= 1, 2, …, M |
|
|
|
(23) |
j= 0, 1, …, N; h= 1, 2, …, N j k= 2, 3, …, K |
|
|
|
(24) |
j= 1, 2, …, N; h= 1, 2, …, N; j ; i= 1, 2, …, M |
|
|
|
(25) |
i= 1, 2, ..., M; j= 1, 2, ..., N k= 1, 2, ..., K |
|
|
|
(26) |
i= 1, 2, …, M; j= 1, 2, …, N |
|
|
برای اینکه هر کار دارای یک کار بلافاصله قبل و یک کار بلافاصله بعد باشد، بهترتیب روابط (20) و (21) منظور شدهاند. رابطۀ (22) برای اطمینان از این در نظر گرفته شده است که بعد از کار مجازی حداکثر یک کار، بهعنوان اولین کار روی هر ماشین پردازش شود. روابط (24)، (25) و (26) نشاندهندۀ نوع و دامنۀ متغیرهای تصمیم مدل PDSM_2 هستند. شایان ذکر است، با توجه به ساختار مدل (روابط (20) و (21)) از آن جهت که مقدار متغیرهای صفر و یک است، مقدار متغیرهای نیز صفر و یک خواهد شد؛ بنابراین در رابطۀ (26) متغیر بهصورت پیوسته بین صفر و یک در نظر گرفته شده است. مدلهای برنامهریزی عدد صحیح مختلط مسئلۀ PJS که PJSM_1 و PJSM_2 نامیده میشوند، با اضافهکردن هر دو رابطة (27) و (28) به مدلهای PDSM_1 و PDSM_2 به دست میآیند.
|
(27) |
j= 1, 2, …, N k= 2, 3, …, K-1 |
|
|
(28) |
j= 1, 2, …, N k= 1, 2, …, K-2 |
|
رابطۀ (27) بیان میکند، اگر قسمتی از آمادهسازی کار j در دورۀ k-1 انجام شود و قسمتی از پردازش آن در دورۀ k+1 صورت گیرد، آنگاه باید تمام دورۀ kتوسط آمادهسازی و پردازش کار j اشغال شده باشد. رابطۀ (28) بیان میکند، اگر قسمتی از آمادهسازی کار j در دورهای انجام شد؛ ولی هیچ بخشی از پردازش آن در دورۀ بعد انجام نشد، آنگاه در تمام دورههای بعد، نباید هیچ بخشی از پردازش کار j انجام شود. به بیان دیگر، روابط (27) و (28) این امکان را فراهم میکنند که بتوان پردازش هر کار را بدون وقفه، بعد از اتمام آمادهسازی آن شروع کرد.
شایان ذکر است، در مدلهای ارائهشده در بالا، هر رابطهای را که متغیرهای مربوط به مدتزمان آمادهسازی، شامل متغیرهای و ، در آنها وجود دارد، میتوان نوآوری مقالۀ حاضر در نظر گرفت.
با توجه به، شدت NP- hard بودن مسائل مورد بررسی، در این بخش یک الگوریتم ابتکاری مبتنی بر تثبیت و آزادسازی مدل ریاضی، با نام FRH[xxvi]، توسعه داده شده است. الگوریتم FRH ارائهشده، از دو مرحلۀ اصلی تشکیل شده است. در مرحلۀ اول الگوریتم مشخص میشود، کدام کارها باید روی کدام ماشین پردازش شود. در مرحلۀ دوم الگوریتم، محیط زمانبندی مسئله از ماشینهای موازی غیر مرتبط، به محیط تکماشین تغییر پیدا میکند و به تعداد ماشینهای موجود، مسئلۀ تکماشین حل خواهد شد تا با رعایت محدودیتهای مدل، توالی کارهای حاصل از مرحلۀ اول، طوری روی هر ماشین تعیین شود که مقدار کل هزینۀ انرژی مصرفشده، حداقل شود. در Error! Reference source not found. شبه کد مرحلۀ اول الگوریتم FRH برای مسائل PDS و PJS نمایش داده شده است. در قسمت نتایج محاسباتی، نشان داده خواهد شد که مدلهای PDSM_1 و PJSM_1 عملکرد بهتری را نسبتبه مدلهای PDSM_2 و PJSM_2 دارند؛ بنابراین الگوریتم ابتکاری FRH بر مبنای مدلهای PDSM_1 و PJSM_1 توسعه داده شده است.
|
گام اول: |
حل آزادشدۀ مدل PDSM_1 (PJSM_1) با درنظر گرفتن تمام متغیرهای دودویی بهصورت پیوسته. |
|
گام دوم: |
تثبیت تمامی متغیرهای بهدستآمده از گام اول که مقدار یک دارند. |
|
گام سوم: |
حل مدل PDSM_1 (PJSM_1) با درنظر گرفتن متغیرهای بهصورت صفر یا یک و سایر متغیرها بهصورت پیوسته. |
|
گام چهارم: |
تخصیص کارها به ماشینها بر اساس متغیرهای بهدستآمده از گام سوم. |
شکل 1- شبه کد مرحله اول الگوریتم FRH
برای حل مسائل تکماشین، مدل ریاضی مسائل زمانبندی کارای انرژی، با زمانهای آمادهسازی وابسته به توالی منفصل از پردازش و متصل به پردازش در حالت تکماشین، بهترتیب با PDSM_1S و PJSM_1S نمایش داده میشوند. این مدلها با حذف اندیس ماشین از متغیرها و پارامترهای مدل بهسادگی قابل بازنویسی هستند.
نکتۀ درخور توجه در مرحلۀ دوم الگوریتم FRH، تعیین مقادیر تعداد دورههایی است که باید گسسته در نظر گرفته شود و دیگری تعداد دورههایی است که باید تثبیت شود. اگر تعداد دورههایی که بهصورت عدد صحیح در نظر گرفته میشود زیاد باشد، مدتزمان اجرای مدلها بیشتر میشود. از طرف دیگر اگر تعداد دورههای عدد صحیح در نظرگرفتهشده با تعداد دورههای تثبیتشده برابر باشد، خطای الگوریتم افزایش پیدا میکند (صابری علیآباد[xxvii] و همکاران، 2020).
از آنجایی که منطق پیوستهبودن، مطابق روابط (13) و (14) مدل ریاضی PDSM_1، حداقل باید برابر سه دورۀ متوالی باشد، تعداد دورههای تثبیت، برابر سه دوره در نظر گرفته شده است. از طرف دیگر برای افزایش سرعت اجرا، تعداد دورههای صفر یا یک برابر، یکی کمتر از دو برابر تعداد دورههای تثبیتشده در نظر گرفته شده است. شایان ذکر است مطالب گفتهشده فقط برای یک مسئلۀ تکماشین است؛ بنابراین لازم است که مقادیر توابع هدف مسائل تکماشین با همدیگر جمع شوند تا مقدار کل هزینۀ انرژی مصرفشده به دست آید. در شکل 2، شبه کد مرحلۀ دوم الگوریتم FRH برای مسئلۀ زمانبندی کارای انرژی تکماشین، با آمادهسازیهای مستقل از توالی منفصل از پردازش نمایش داده شده است.
|
گام اول: |
قرار دهید A=5، B=3 و . |
|
گام دوم: |
تمامی متغیرهای ، و پیوسته در نظر گرفته شوند. |
|
گام سوم: |
مقدار متغیرهای ، و برای دورههای {A-4, A-3, A-2, A-1, A} k بهصورت صفر و یک در نظر گرفته شوند. |
|
گام چهارم: |
مدل PDSM_1S را حل کنید. |
|
گام پنجم: |
مقادیر و را برای دورههای { B-2, B-1, B} k تثبیت کنید. اگر پردازش یا آمادهسازی کاری که در انتهای دورۀ B قرارگرفته بهطور کامل انجام نشده بود، مقدار را برابر تعداد دورههایی قرار دهید که پردازش یا آمادهسازی این کار بعد از دورۀ B در آنها بهطور کامل قرار میگیرد، در غیر این صورت را برابر صفر قرار دهید. سپس قرار دهید . |
|
گام ششم: |
مقدار را برای کارهای j, h , j را نیز تثبیت کنید که حداقل یکی از متغیرهای مربوط به پردازش یا آمادهسازی آنها تثبیت شده است. |
|
گام هفتم: |
قرار دهید A= Min {K, A+ ، B= Min {K, B+ |
|
گام هشتم: |
اگر A≥ K به گام 9 بروید و در غیر این صورت به گام 3 بازگردید. |
|
گام نهم: |
پایان |
شکل 2- شبه کد مرحلۀ دوم الگوریتم FRH
در این بخش با انجام آزمایشهای عددی، عملکرد روشهای ارائهشده برای هرکدام از مسائل مورد بررسی، ارزیابی میشود. تمامی مدلهای ارائهشده در محیط برنامهنویسی Visual C# 2017، کدنویسی شده که با استفاده از قابلیت Concert Technology حلکنندۀ CPLEX 12.8، در رایانهای دارای 4 هسته CPU با مشخصات ,32GB RAM Intel corei7 4.0 GHz، با محدودیت زمانی 3600 ثانیه برای هر نمونه اجرا شده است.
دادههای مورد نیاز برای تولید نمونههای تصادفی، مانند مدتزمان پردازش کارها، میزان مصرف انرژی ماشینها هنگام پردازش کارها و تعرفۀ مصرف انرژی، مشابه پیشینۀ موضوع (دینگ و همکاران (2015)؛ چنگ و همکاران (2017) و صابری علیآباد و همکاران (2020)) در نظر گرفته شده است. زمانهای آمادهسازی، مطابق بکتور[xxviii] و ساراچ[xxix] (2019) در سه سطح کوچک، بزرگ و متوسط بهصورت تصادفی از توزیع یکنواخت گسسته در بازههای ]25 ،5[، ]50 ،25[ و ]50 ،5[ تولید میشوند که بهترتیب آمادهسازی، نوع 1، نوع 2 و نوع 3 نامیده میشوند. میزان مصرف انرژی زمانهای آمادهسازی، بهصورت ضرایب تصادفی از میزان مصرف انرژی پردازش کارها، مطابق رابطۀ (29) تولید شده است.
|
(29) |
|
در رابطۀ (29) مقدار پارامتر بهصورت تصادفی در بازههای ]0 ،0[، ]5/0 ،0[ و ]1 ،0[ در نظر گرفته شده است. ضربالاجل اتمام کلیۀ کارها که با B نشان داده شده، بهعنوان حد بالای دامنۀ عملیات در نظر گرفته شده است (دینگ و همکاران، 2015). این ضربالاجل با درنظر گرفتن مدتزمانهای آمادهسازی با انجام اصلاحات لازم، مشابه دینگ و همکاران (2015) و مطابق رابطۀ (30) محاسبه شده است.
|
(30) |
|
همچنین دو نوع تعرفه برای مصرف انرژی در نظر گرفته شده است (دینگ و همکاران (2015)؛ چنگ و همکاران (2017) و صابری علیآباد و همکاران (2020)) که نوع اول مربوط به کشور چین و نوع دوم مربوط به کشورهای اروپایی است. در تعرفۀ کشور چین که با TOU1 نمایش داده میشود، هر روز به شش دورۀ مختلف تقسیم میشود و در تعرفۀ کشورهای اروپایی، هر روز به 24 دوره تقسیم میشود و با TOU2 نشان داده میشود. تعداد ماشینهای در نظر گرفتهشده برابر 5، 10 و 20 ماشین است (دینگ و همکاران (2015)؛ چنگ و همکاران (2017) و صابری علیآباد و همکاران (2020)). تعداد کارها نیز از دو برابر تعداد ماشینها شروع میشود و افزایش مییابد. به ازای هرکدام از ترکیبات تعرفه، آمادهسازی، تعداد ماشین و تعداد کار 10 نمونۀ تصادفی تولید و حل شده است.
نتایج حاصل از اجرای مدلهای برنامهریزی عدد صحیح مختلط مسئلۀ PDS با دورههای TOU1 و TOU2، بهترتیب در Error! Reference source not found. و جدول 3 آورده شده است. ستون m/n در این جدولها بیانگر تعداد ماشین و تعداد کار است؛ همچنین منظور از ستون #opt، تعداد نمونههایی است که از 10 نمونۀ تولیدشده برای هر ترکیب کار و ماشین بهصورت بهینه حل شده است. میانگین مدتزمان صرفشده برای حل نمونهها نیز، برحسب ثانیه در ستون T(s) آورده شده است. در این ستونها مدتزمانهای کمتر از یک ثانیه با « » نشان داده شده است. در ردیفهای مربوط به نمونههای حلنشده، علامت «-» درج شده است. نتایج مدلهای مسئلۀ PJS با دورههای TOU1 و TOU2 بهترتیب در جدول 4 و جدول 5 آورده شده است.
جدول 2- نتایج مدلهای ریاضی برای مسئلۀ PDS با دورۀ TOU1
|
Setup1 |
Setup2 |
Setup3 |
||||||||||||
|
PDSM_1 |
PDSM_2 |
PDSM_2 |
PDSM_2 |
PDSM_1 |
PDSM_2 |
|||||||||
|
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
|
10/5 |
10 |
0 |
10 |
0 |
10/5 |
10 |
0 |
10 |
0 |
10/5 |
10 |
0 |
10 |
0 |
|
25/5 |
10 |
7 |
3 |
1 |
15/5 |
10 |
1 |
10 |
2 |
20/5 |
10 |
8 |
1 |
7 |
|
35/5 |
6 |
332 |
- |
- |
20/5 |
10 |
174 |
2 |
145 |
30/5 |
1 |
602 |
- |
- |
|
20/10 |
10 |
0 |
10 |
0 |
25/5 |
1 |
267 |
- |
- |
20/10 |
10 |
0 |
10 |
1 |
|
40/10 |
10 |
5 |
10 |
6 |
20/10 |
10 |
3 |
10 |
3 |
30/10 |
10 |
3 |
10 |
7 |
|
55/10 |
5 |
675 |
- |
- |
25/10 |
10 |
70 |
10 |
108 |
40/10 |
6 |
135 |
2 |
252 |
|
40/20 |
10 |
3 |
10 |
5 |
30/10 |
10 |
516 |
1 |
54 |
40/20 |
10 |
31 |
10 |
53 |
|
65/20 |
10 |
218 |
10 |
179 |
35/10 |
3 |
193 |
- |
- |
55/20 |
10 |
440 |
10 |
651 |
|
85/20 |
6 |
589 |
- |
- |
40/20 |
2 |
96 |
2 |
157 |
65/20 |
2 |
866 |
2 |
1284 |
جدول 3- نتایج مدلهای ریاضی برای مسئلۀ PDS با دورۀ TOU2
|
Setup1 |
Setup2 |
Setup3 |
||||||||||||
|
PDSM_1 |
PDSM_2 |
PDSM_2 |
PDSM_2 |
PDSM_1 |
PDSM_2 |
|||||||||
|
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
|
10/5 |
10 |
0 |
10 |
2 |
10/5 |
10 |
3 |
10 |
13 |
10/5 |
10 |
3 |
10 |
9 |
|
20/5 |
3 |
1041 |
- |
- |
15/5 |
9 |
1055 |
1 |
2879 |
15/5 |
10 |
378 |
2 |
873 |
|
20/10 |
10 |
103 |
- |
- |
20/10 |
8 |
1467 |
4 |
1478 |
20/5 |
1 |
2764 |
0 |
- |
|
25/10 |
3 |
1354 |
- |
- |
- |
- |
- |
- |
- |
20/10 |
9 |
561 |
1 |
132 |
جدول 4- نتایج مدلهای ریاضی برای مسئلۀ PJS با دورۀ TOU1
|
Setup1 |
Setup2 |
Setup3 |
||||||||||||
|
PJSM_1 |
PJSM_2 |
PJSM_2 |
PJSM_2 |
PJSM_1 |
PJSM_2 |
|||||||||
|
N |
#opt |
T(s) |
#opt |
T(s) |
N |
#opt |
T(s) |
#opt |
T(s) |
n |
#opt |
T(s) |
#opt |
T(s) |
|
10/5 |
10 |
0 |
10 |
0 |
10/5 |
10 |
0 |
10 |
0 |
10/5 |
10 |
0 |
10 |
0 |
|
25/5 |
10 |
2 |
4 |
821 |
15/5 |
10 |
1 |
10 |
2 |
20/5 |
10 |
6 |
9 |
145 |
|
40/5 |
5 |
587 |
- |
- |
20/5 |
10 |
171 |
3 |
501 |
30/5 |
1 |
329 |
- |
- |
|
20/10 |
10 |
0 |
10 |
0 |
25/5 |
4 |
390 |
- |
- |
20/10 |
10 |
0 |
10 |
1 |
|
40/10 |
10 |
3 |
10 |
4 |
20/10 |
10 |
2 |
10 |
2 |
30/10 |
10 |
4 |
10 |
4 |
|
55/10 |
5 |
244 |
- |
- |
25/10 |
10 |
46 |
10 |
67 |
40/10 |
7 |
432 |
2 |
160 |
|
40/20 |
10 |
2 |
10 |
3 |
30/10 |
9 |
192 |
1 |
40 |
40/20 |
10 |
31 |
10 |
29 |
|
65/20 |
10 |
101 |
10 |
106 |
35/10 |
3 |
109 |
- |
- |
55/20 |
10 |
433 |
10 |
648 |
|
90/20 |
6 |
611 |
- |
- |
40/20 |
2 |
53 |
2 |
91 |
65/20 |
2 |
855 |
2 |
1275 |
جدول 5- نتایج مدلهای ریاضی برای مسئلۀ PJS با دورۀ TOU2
|
|
Setup1 |
|
Setup2 |
|
Setup3 |
|||||||||
|
PJSM_1 |
PJSM_2 |
PJSM_2 |
PJSM_2 |
PJSM_1 |
PJSM_2 |
|||||||||
|
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
m/n |
#opt |
T(s) |
#opt |
T(s) |
|
10/5 |
10 |
0 |
10 |
1 |
10/5 |
10 |
1 |
10 |
3 |
10/5 |
10 |
1 |
10 |
2 |
|
20/5 |
4 |
779 |
1 |
480 |
15/5 |
10 |
494 |
10 |
1046 |
20/5 |
2 |
806 |
1 |
192 |
|
20/10 |
10 |
18 |
10 |
97 |
20/10 |
9 |
387 |
9 |
801 |
20/10 |
9 |
100 |
9 |
219 |
|
30/10 |
1 |
1380 |
- |
- |
- |
- |
- |
- |
- |
25/10 |
1 |
351 |
1 |
1849 |
با توجه به جداول 1 و 2، واضح است که مدل PDSM_1 نسبتبه مدل PDSM_2 کارایی بیشتری دارد و قادر به حل تعداد نمونۀ بیشتری بهصورت بهینه است و همچنین از حیث زمان اجرا نیز، مطلوبیت بیشتری دارد. بهطور مشابه در مسئلۀ PJS نیز مدل PJSM_1 نسبتبه مدل PJSM_2 عملکرد بهتری دارد و با مقایسۀ جدولهای 1 و 3 با جداول 2 و 4، میتوان دریافت که تعداد نمونههای حلشده توسط مدلهای ارائهشده برای مسائل PDS و PJS با تعرفههای TOU2، خیلی کمتر از تعداد نمونههای حلشده با تعرفۀ TOU1 است؛ زیرا که در تعرفههای TOU2 هر روز به 24 دورۀ مختلف تقسیم میشود؛ درحالی که در تعرفۀ TOU1، هر روز به 6 دوره تقسیم میشود که این افزایش تعداد دوره در هر روز، باعث افزایش پیچیدگی مسائل و کاهش قدرت حل مدلهای ریاضی میشود.
با توجه به نتایج، آمادهسازی نوع 1 که مقادیر کوچکتری نسبتبه دو نوع دیگر آمادهسازی دارد، نیازمند محاسبات کمتری است و همین امر موجب میشود تا تعداد نمونههای بهینۀ حلشده با آمادهسازی نوع 1، بیشتر از دو نوع دیگر باشد. در بین آمادهسازیهای نوع 2 و نوع 3، بهدلیل اینکه آمادهسازی نوع 3 میتواند اعداد کوچکتری را شامل شود؛ بنابراین محاسبات آن راحتتر است و تعداد نمونههای حلشده از این نوع، نسبت به نوع 2 بیشتر است.
بهطور کلی با توجه به نتایج ارائهشده در جدولهای 1 تا 4، میتوان دریافت که مدتزمان مدلهای حل ریاضی ارائهشده، حساسیت بالایی نسبتبه میزان بزرگی مقادیر آمادهسازی و همچنین تعداد دورهها از خود نشان میدهند؛ به این معنی که افزایش مقدار آمادهسازی، موجب افزایش پیچیدگی مسئله و متعاقباً افزایش مدتزمان حل مدلهای ریاضی ارائهشده میشود. از طرف دیگر، افزایش تعداد دورهها نیز موجب افزایش چشمگیر مدتزمان حل مدلهای ریاضی میشود. ازاینرو توصیه میشود که با توجه به شرایط مسئله، تعداد دورهها را کاهش داد. یکی از راههای کاهش دوره، کاهش افق برنامهریزی است؛ مثلاً به جای اینکه مدیران بخواهند برای یک روز کامل برنامهریزی کنند، روز کاری را به دو شیفت قبل از ظهر و بعد از ظهر تبدیل کنند و در هر نوبت، نصف کارها را زمانبندی و پردازش کنند. شکستن روز کاری به شیفتهای مختلف، اگرچه بهراحتی موجب کاهش تعداد دورهها میشود، بعضاً ممکن است که افزایش هزینه را نیز در پی داشته باشد؛ بنابراین مدیران میتوانند با برقراری موازنه[xxx] بین هزینه و مدتزمان حل مدلهای ریاضی، برنامههای مختلفی ارائه دهند.
در جدول 6 و جدول 7 نتایج الگوریتم FRH برای مسائل PDS و PJS ارائه شده است. خطای الگوریتم FRH برای نمونههایی که جواب بهینۀ آنها موجود بوده، مطابق رابطۀ (31) و برای سایر نمونهها، مطابق رابطۀ (32) محاسبه شده است.
|
(31) |
|
|
(32) |
|
حد پایین در نظر گرفتهشده در رابطۀ (32) برای مسئلۀ PDS بر مبنای آزادسازی خطی، مدل PDSM_1 و برای مسئلۀ PJS بر مبنای آزادسازی خطی، مدل PJSM_1 محاسبه شده است.
جدول 6- نتایج الگوریتم FRH برای مسئلۀ PDS
|
TOU1 |
TOU2 |
|||||||||||||||||
|
Setup1 |
Setup2 |
Setup3 |
Setup1 |
Setup2 |
Setup3 |
|||||||||||||
|
m/n |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
|
10/5 |
10 |
0 |
5/1 |
10 |
0 |
1/2 |
10 |
0 |
1/1 |
10 |
0 |
5/0 |
10 |
0 |
0/2 |
10 |
0 |
7/0 |
|
50/5 |
10 |
743 |
8/2 |
10 |
1074 |
5/1 |
10 |
793 |
0/1 |
10 |
869 |
8/3 |
10 |
900 |
1/2 |
10 |
1076 |
9/2 |
|
90/5 |
9 |
2146 |
5/1 |
- |
- |
- |
- |
- |
- |
5 |
2002 |
8/1 |
- |
- |
- |
- |
- |
- |
|
20/10 |
10 |
0 |
6/1 |
10 |
0 |
7/1 |
10 |
0 |
2/2 |
10 |
0 |
0/0 |
10 |
0 |
7/1 |
10 |
0 |
8/0 |
|
80/10 |
10 |
1503 |
3/4 |
10 |
1861 |
7/2 |
9 |
1732 |
7/0 |
9 |
2124 |
9/3 |
10 |
2607 |
6/1 |
10 |
2436 |
9/1 |
|
130/10 |
7 |
1923 |
3/0 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
40/20 |
10 |
0 |
6/2 |
10 |
0 |
1/2 |
10 |
0 |
4/3 |
10 |
2 |
6/0 |
10 |
3 |
9/2 |
10 |
3 |
7/1 |
|
120/20 |
10 |
1351 |
8/5 |
10 |
1792 |
0/3 |
10 |
1472 |
5/3 |
9 |
1459 |
1/2 |
8 |
2363 |
3/2 |
10 |
2231 |
3/2 |
|
190/20 |
9 |
2566 |
4/1 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
جدول 7- نتایج الگوریتم FRH برای مسئلۀ PJS
|
TOU1 |
TOU2 |
|||||||||||||||||
|
|
Setup1 |
Setup2 |
Setup3 |
Setup1 |
Setup2 |
Setup3 |
||||||||||||
|
m/n |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
#opt |
T(s) |
RPD |
|
10/5 |
10 |
0 |
7/1 |
10 |
0 |
9/0 |
10 |
0 |
7/0 |
10 |
0 |
3/2 |
10 |
0 |
6/1 |
10 |
0 |
7/1 |
|
50/5 |
10 |
298 |
4/3 |
10 |
1444 |
9/1 |
10 |
860 |
1/3 |
10 |
180 |
6/0 |
10 |
886 |
3/1 |
10 |
304 |
2/0 |
|
100/5 |
10 |
2118 |
1/1 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
10 |
22 |
2/4 |
- |
- |
- |
|
20/10 |
10 |
0 |
6/1 |
10 |
0 |
7/1 |
10 |
0 |
9/1 |
10 |
1 |
3/0 |
10 |
115 |
6/1 |
10 |
1 |
5/1 |
|
80/10 |
10 |
11 |
3/4 |
10 |
1489 |
2/2 |
10 |
994 |
4/2 |
10 |
652 |
5/2 |
10 |
7 |
6/0 |
10 |
774 |
7/1 |
|
130/10 |
10 |
2449 |
7/1 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
10 |
380 |
8/3 |
- |
- |
- |
|
40/20 |
10 |
0 |
6/2 |
10 |
0 |
1/1 |
10 |
0 |
9/2 |
10 |
3 |
4/1 |
10 |
1284 |
3/3 |
10 |
1 |
6/0 |
|
120/20 |
10 |
769 |
0/3 |
9 |
1655 |
8/7 |
10 |
77 |
4/2 |
10 |
1722 |
6/2 |
- |
- |
- |
10 |
764 |
4/2 |
|
130/20 |
10 |
1087 |
4/2 |
9 |
2374 |
6/7 |
10 |
991 |
8/1 |
9 |
1824 |
2/2 |
- |
- |
- |
10 |
1180 |
5/0 |
|
220/20 |
8 |
2502 |
5/2 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
با توجه به جداول 5 و 6 میتوان مشاهده کرد، نتایج الگوریتم ابتکاری FRH برای مسائل PDS و PJS مشابه نتایج محاسباتی مدلهای ریاضی است؛ یعنی تعداد نمونههای حلشده با تعرفههای TOU1، به ازای هر سه نوع آمادهسازی، بیشتر از نمونههای حلشده با دورههای TOU2 است؛ همچنین به ازای هر دو نوع تعرفۀ در نظر گرفتهشده، آمادهسازیهای نوع 1، کمترین پیچیدگی و بیشترین تعداد نمونۀ حلشده را دارد. در بین آمادهسازیهای نوع 2 و نوع 3 نیز، تعداد نمونههای حلشده با آمادهسازی نوع 3 بیشتر است؛ همچنین بهوضوح میتوان مشاهده کرد، مدتزمان اجرای الگوریتم با تعرفۀ TOU1، کمتر از زمان اجرای الگوریتم با تعرفۀ TOU2 به ازای آمادهسازی و تعداد ماشین یکسان است.
حداکثر متوسط خطای الگوریتم FRH در میان تمام دستۀ نمونههای ارائهشده در جدولهای 5 و 6 برای مسائل PDS و PJS، بهترتیب برابر 8/5 و 8/7درصد است که گویای مطلوبیت دقت الگوریتم است.
در این مقاله مسئلۀ زمانبندی کارای انرژی ماشینهای موازی غیر مرتبط، با درنظر گرفتن زمانهای آمادهسازی مستقل از توالی بررسی شد. آمادهسازی مورد بررسی نیز، در دو حالت منفصل از پردازش و متصل به پردازش بررسی شد. برای هرکدام از مسائل، دو نوع مدل برنامهریزی عدد صحیح مختلط ارائه و با انجام آزمایشهای عددی گوناگون، نتایج مدلها ارزیابی شد. مدلهای ارائهشده در هر دو حالت آمادهسازی منفصل از پردازش و متصل به پردازش، نمونههای تا 20 ماشین و 80 کار را بهصورت بهینه حل کرده است؛ همچنین در این مقاله، بهمنظور حل مسائل در ابعاد بزرگ، یک الگوریتم ابتکاری مبنی بر تثبیت و آزادسازی نیز ارائه شد که این الگوریتم، بر مبنای تجزیۀ محیط زمانبندی ماشینهای موازی غیر مرتبط، به تعدادی مسئلۀ تکماشین بنا شده بود. الگوریتم ارائهشده برای مسئله با آمادهسازی منفصل از پردازش، قادر به حل نمونههای تا 20 ماشین و 180 کار است و برای مسئلۀ متصل به پردازش، نمونههای با ابعاد 20 ماشین و 220 کار را حل میکند.
ازجمله پیشنهادهایی که میتوان برای تحقیقات آتی ارائه داد، میتوان به بررسی مسئلۀ زمانبندی کارای انرژی ماشینهای موازی غیر مرتبط به زمانهای آمادهسازی مستقل از توالی اشاره کرد که در آن، کارها بهصورت پویا در دسترس قرار میگیرد؛ همچنین با توجه به اینکه بررسی مسائل زمانبندی کارای انرژی با زمانهای آمادهسازی مستقل از توالی، تاکنون در هیچ پژوهشی مشاهده نشده و برای اولینبار در این مقاله، این مسئلۀ مهم بررسی شده است؛ بنابراین بررسی مسئلۀ زمانبندی کارای انرژی با زمانهای آمادهسازی مستقل از توالی، در سایر محیطهای زمانبندی میتواند پیشنهاد دیگری برای مطالعات آتی باشد.
[i] Wu
[ii] Che
[iii]Energy Efficient Scheduling
[iv]unrelated parallel machine
[v]Time of Use
[vi] Allahverdi
[vii] Souroush
[viii] Vallada
[ix] Ruiz
[x] Jia
[xi]Ant Colony
[xii]Non-dominated Sorting Genetic Algorithm
[xiii] Tan
[xiv] Cheng
[xv] Ding
[xvi] Zhou
[xvii]Memetic Differential Evolutionary Algorithm
[xviii] Ramezanian
[xix] Jiang
[xx] Wang
[xxi]Improved Multi-Objective Evolutionary Algorithm based on Decomposition
[xxii] Zhou
[xxiii] Öztop
[xxiv]Processing time Disjointed from Setup times
[xxv]Processing time Jointed to Setup times
[xxvi]Fix and Relax Heuristic
[xxvii] Saberi-Aliabad
[xxviii] Bektur
[xxix] Saraç
[xxx]Trade-off
)