نوع مقاله : مقاله پژوهشی
نویسنده
استادیار، دانشکده مدیریت و مهندسی صنایع، دانشگاه صنعتی شاهرود، شاهرود، ایران
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسنده [English]
Abstract: Distributing the production activities among the supply chain facilities with regard to the considered criteria can have a significant impact on the productive management. In this paper, a comprehensive mathematical model for reentrant permutation flow shop scheduling via considering a preventive maintenance and distributed jobs on different facilities is proposed. The uncertainty of the time of preventive maintenance operation is handled using robust optimization technique based on the uncertainty budget approach. Job assignment to production facilities and job scheduling are determined in the proposed model by considering multiple objectives include Cmax minimization, production cost minimization, and average tardiness. Due to the NP-hard nature of the proposed flow shop scheduling problem, a new hybrid meta-heuristic based on the novel adaptive large neighborhood search and the simulated annealing is adopted. The obtained results from an extensive numerical experimentation indicate the efficiency of the proposed model and solution algorithm to tackle the proposed problem.
Introduction: In certain manufacturing industries, it has been observed that the classical assumption of flow shop scheduling, stating that each job visits each machine exactly once, is occasionally violated. The prime example can be noticed in the high-tech industries, i.e. semiconductor wafer fabrication in which the operation processes of the jobs are performed by re-visiting some workstations (Gupta & Sivakumar, 2006). The scheduling problem of this nature of processing is categorized as a distinct flow shop with reentrant line configuration, called reentrant flow shop scheduling (RFS) (Katragjini et. al., 2015). The significance of RFS is the processing layers l. Each layer begins from the first workstation and completes on the last workstation. It means that once a job finished a layer of a set of operations, it will repeat its process to the next layer starting on the first workstation until all operations are completed. The RFS scheduling has been an active research area and attracted a considerable attention since the past decade due to the development and improvement of high-tech industry. The complexity of RFS cannot be circumvented since it involves more operations than the classical flow shop. Moreover, the cyclic operations where the jobs with higher layers may overlap other jobs in the same work station are essential to be considered. As a result, these complexities have triggered the development of the efficient scheduling approaches to improve the system performance. Various researchers surveyed the scheduling techniques in semiconductor manufacturing and providing the global view on reentrant scheduling problems. Another form of RFS is reentrant permutation flow shop (RPFS) where at each level no passing is permitted, that is, not only the machine sequence the same for all jobs, but also the job sequence is the same for each machine (Rifai et al., 2016). Despite the enormous literature on the RFS, most studies -if not all- base their research on the assumption that the process only involves a single production line. Some studies exploredthe problem on hybrid RFS where the production stages have more than one machines available to process the jobs. Nevertheless, hybrid RFS is based on the single production line. Nowadays, single factory firms are less common, with multi-plant companies and supply chains taking a more important role in practice. Several literatures mentioned that multiple production lines with more than one production center, named as distributed manufacturing system, enables companies to achieve higher product quality, lower production costs and lower management risks. However, existing studies focused more on the economic field anddistributed finite capacity scheduling is seldom tackled.
Materials and Methods:In this section, a novel hybrid meta-heuristic via considering the specific assumptions of the flow shop problem as a NP-hard problem is proposed. The proposed solution algorithm incorporates adaptive large neighborhood search and the simulated annealing algorithms. Various new construction and deconstruction neighborhood structures are applied in the proposed adaptive large neighborhood search algorithm. Details of the proposed algorithm is presented in Fig.1.
Results and Discussion: The results of the proposed solution algorithm assessment are presented based on the two common performance assessment criteria which are proposed in the literature after 10 times runs of the applied solution algorithms. These criteria are the average number of obtained Pareto solution at each iteration of the algorithm and average number of Pareto solutions which are not dominated by solutions from other compared algorithms. In addition, computational time is considered as a third criteria for performance assessment of the proposed solution algorithm (See Table 1). Obtained results indicate the superiority of the proposed solution algorithm.
Fig. 1- Peseudo code of the proposed solution algorithm
Table 1- Performance assessment of the proposed solution algorithm
Compared Alg.
Proposed Alg.
Pro.
Compared Alg.
Proposed Alg.
Pro.
1
2
3
1
2
3
1
2
3
1
2
3
0.7270
39.30
72.01
0.4129
25.95
57.12
15
0.6120
18.71
3392.26
0.5114
13.80
3019.18
75
0.6991
34.43
180.23
0.5972
28.80
152.11
30
0.6523
18.01
5900.74
0.5304
11.20
5631.07
90
0.9009
48.23
479.19
0.6543
38.10
398.06
45
0.6914
15.23
6801.69
0.5713
11.83
6594.29
105
0.9207
47.3
1308.21
0.7810
36.30
1200.47
60
Conclusion: In this study, a comprehensive optimization model for an extended reentrant permutation flow shop scheduling via considering a preventive maintenance and distributed jobs on different facilities is proposed. To enhance the applicability of the proposed model, uncertainty of the time of preventive maintenance operation is handled using robust optimization technique based on the uncertainty budget approach. In the proposed mathematical model, multiple objectives include Cmax minimization, production cost minimization, and average tardiness are considered. The aim of the proposed model is to determine the job assignment to production facilities and job scheduling. A new hybrid meta-heuristic based on the novel adaptive large neighborhood search and the simulated annealing is applied as a consequence of the NP-hard nature of the proposed flow shop scheduling problem,. The obtained results from an extensive numerical experimentation indicate the efficiency of the proposed model and solution algorithm to tackle the proposed problem.
References
Gupta, A. K., & Sivakumar, A. I. (2006). “Job Shop Scheduling Techniques In Semiconductor Manufacturing”. Int. J. Adv. Manuf. Technol, 27(11), 1163-1169.
Katragjini, K., Vallada, E., & Ruiz, R. (2015). “Rescheduling Flowshops Under Simultaneous Disruptions”. Paper presented at the 6th IESM Conference, Seville, Spain.
Rifai, A. P., Nguyen, H. T., & Dawal, S. Z. M. (2016). “Multi-Objective Adaptive Large Neighborhood Search For Distributed Reentrant Permutation Flow Shop Scheduling”. Applied Soft Computing, 40(1), 42–57.
کلیدواژهها [English]
مقدمه
در مدلهای سنتی برنامهریزی و زمانبندی توالی عملیات جریان کارگاهی، بهطورمعمول فرض بر آن است که هر کار تنها یکبار از یک ماشین عبور میکند (پیندو[i]، 2008). این در حالی است که با توسعۀ فرایندهای تولید و پیچیدهشدن آن بهویژه در صنایع تولیدی با فناوری سطح بالا همچون تولید ویفر نیمهرسانا (وارگاس-ویلامیل و بیورا[ii]، 2001)، تولید صفحات کریستال مایع (چوی، کیم و لی[iii]، 2011)، مدارهای چاپی (بیسپو و تایور[iv]، 2001) و یا حتی در حوزههای کاربردی مانند پردازش سیگنال (زو، یین، چنگ، وو و گو[v]، 2014) و خدمات نگهداری و تعمیرات (لین، لی و هو[vi]، 2013)، امکان بازگشت دوبارۀ کارها به ماشین وجود خواهد داشت. به این نوع از مسائل برنامهریزی، مسائل جریان کارگاهی دوباره واردشونده گفته میشود (ریفی، گوین و داوال[vii]، 2016). در جریان کارگاهی دوباره واردشونده، انجام فرایند کارها با مجموعهای از لایههای انجام کار تعریف میشود (شامل عملیات کاری) که از ماشین ابتدایی تا ماشین پایانی شروع میشود. هر کار باید پس از پایان یک لایه، دیگر لایههای لازم را پشت سر گذارد (کوپتا و سیواکومار[viii]، 2006). در نظر گرفتن امکان مراجعۀ دوبارۀ کارها به ماشین باعث افزایش پیچیدگی مدلسازی و برنامهریزی مسأله جریان کارگاهی نسبت به حالت کلاسیک آن خواهد شد. مسأله جریان کارگاهی دوباره واردشونده نیز باتوجهبه توالی انجام کارها روی ماشینها به دو دستۀ عمومی و جایگشتی تقسیم میشود (ریفی، گوین و داوال7، 2016). درحالت جایگشتی، توالی انجام کارها روی ماشینها برای تمامی کارها یکسان است. این حالت نیز در بسیاری صنایع با فناوری سطح بالا نظیر تولید نیمهرساناها دارای کاربرد خواهد بود. از سوی دیگر باتوجهبه پیچیدگی الزامات فضای تصمیمگیری برنامهریزی و زمانبندی کارها در دنیای واقعی، نیاز است تا درراستای ارتقاءِ اثربخشی برنامهها، دیگر تصمیمات مرتبط مانند برنامهریزی نگهداری و تعمیرات ماشینها نیز در نظر گرفته شود (رویز، گارسیا-دیاز و ماروتو[ix]، 2007). از سوی دیگر درطی سالهای اخیر روند پراکندهکردن فرایندهای تولید در تسهیلات مختلف در سطح زنجیره تأمین با هدف کاهش قیمت تولید، ارتقاءِ کیفیت تولید، کاهش ریسک تولید و نزدیکی بیشتر به بازارهای هدف توسعه یافته است. این امر باعث شده است تا مسأله زمانبندی تولید در سطح زنجیره تأمین مطرح شود و تصمیمات مرتبط با پیکرهبندی شبکه همچون انتخاب تسهیلات تولید بر آن تأثیرگذار باشند (مون، کیم و هور[x]، 2002). پراکنده و توزیعکردن فعالیتهای تولید در طی سالهای اخیر بهشدت توجه سازمآنهای در حال رقابت در بازارهای جهانی را بهخود جلب کرده است (نادری و رویز[xi]، 2014). این در حالی است که در دنیای واقعی بسیاری از پارامترهای کلیدی برای تصمیمسازی در شرایط عدمقطعیت هستند و نیاز است تا تأثیر آنها در فرایند برنامهریزی در نظر گرفته شود (کسپرسکی، کورپیسز و زیلینسکی[xii]، 2012). لحاظنکردن عدمقطعیت در فرایند برنامهریزی باعث کاهش کارایی و اثربخشی تصمیمات در مرحلۀ اجرا خواهد شد. علاوه بر آن تصمیمگیری همزمان تخصیص کارها به تسهیلات و تعیین توالی آنها بر پیچیدگیهای این مسأله در مقایسه با مسأله کلاسیک برنامهریزی جریان کارگاهی میافزاید (نادری و رویز11، 2014). باتوجهبه جنبههای متعدد و درعینحال متنوع، مسأله برنامهریزی و زمانبندی جریان کارگاهی که اشاره شد، نیاز است تا در فرایند ارزیابی با تعیین معیارهای ارزیابی مناسب، اثربخشی تصمیمات را بهخوبی ارتقاء داد؛ ازاینرو متأثیر از بسیاری الزامات در دنیای واقعی، مدلهای چندهدفه و نیاز به معرفی جوابهای مناسب با در نظر گرفتن چند تابع هدف بهصورت همزمان، توسعه یافته است (ینیسی و یاقماهان[xiii]، 2014).
در این مقاله، مدلی جامع برای زمانبندی جریان کارگاهی جایگشتی دوباره واردشونده با سه معیار ارزیابی، ارائه شده است. برای افزایش اثربخشی برنامهریزی، محدودیتهای منبع در اختیار در شرایط اِعمال تعمیرات و نگهداری پیشگیرانه روی ماشینها در نظر گرفته شده است. علاوه بر آن، بهدلیل پیچیدگی زیاد ماشینها در فرایند تولید محصولات فناورانه و اثرگذاری این سطح بالای تکنولوژی بر فرایند تعمیرپذیری ماشینها، عدمقطعیت زمان تعمیر ماشینها نیز با استفاده از رویکرد برنامهریزی استوار بودجهای لحاظ شده است. درنهایت، باتوجهبه پیچیدگیهای زیاد مدل ارائهشده، روش حل کارایی با الگوریتم فرا ابتکاری ترکیبی توسعهیافته ارائه و ارزیابی شده است.
دیگر بخشهای مقاله بهصورت ذیل ارائه شده است. در بخش 2، مبانی نظری و پیشینۀ پژوهش زمانبندی جریان کارگاهی جایگشتی دوباره واردشونده بررسی شده است. در بخش3، مسأله پژوهش و مدل ریاضی آن ارائه شده است. در بخش 4، الگوریتم حل ترکیبی جدید پیشنهادشده، بررسی شده است. مسائل نمونۀ بررسی و تنظیم پارامترهای الگوریتم حل در بخش5 ارائه شده است. نتایج محاسباتی در حل مسأله نمونه و اعتبارسنجی روش حل پیشنهادی نیز در بخش 5 ارائه شده است. درنهایت جمعبندی و پیشنهادها برای انجام پژوهشهای آتی در بخش 6 ارائه شده است.
مبانی نظری و پیشینۀ پژوهش
نخستین بار گریو[xiv] و همکارانش (1983)، مسأله برنامهریزی جریان کارهای دوباره واردشونده را معرفی کردند. پس از آن طی دهههای اخیر با توسعۀ صنعت نیمهرساناها توجه به آن زیاد شد و توسعه یافت. بهدلیل امکان بازگشت دوبارۀ کارها به یک ماشین، این مسأله پیچیدگیهای حل بیشتری نسبت به مسأله کلاسیک برنامهریزی جریان کارگاهی دارد. پن و چن[xv] (2003) در مطالعهای نشان دادهاند مسأله برنامهریزی جریان کارگاهی دوباره واردشونده حتی در ابعاد کوچک آن از نوع مسائل دارای پیچیدگی حل است. طی سالهای اخیر، همزمان با توسعۀ صنایع با فناوری سطح بالا نظیر توسعۀ نیمهرساناها، مسأله جریان کارگاهی دوباره واردشونده با امکان یکسانبودن توالی کارها روی همۀ ماشینها و با نام جایگشتی بهشدت توجه پژوهشگران را بهخود جلب کرد (چن، پن و لین[xvi]، 2009؛ چن[xvii]، 2006؛ چن، پن و وو[xviii]، 2008). در مسائل زمانبندی عملیاتِ دوباره واردشونده، توجه به دو مقولۀ کاهش هزینهها و افزایش بهرهوری با در نظر گرفتن موعد تحویل کارها همواره مدنظر پژوهشگران بوده است (ریفی، گوین و داوال7، 2016). حداقلکردن زمان تکمیل آخرین کار با هدف حداکثرکردن بهرهوری با افزایش میزان خروجی از متداولترین معیارهای ارزیابی در زمانبندی جریان کارگاهی دوباره واردشونده است (چو، چو و دسپرز[xix]، 2010؛ سان، ژانگ، گو و وانگ[xx]، 2011)؛ برای مثال یانگ[xxi] و همکارانش (2008) مدل برنامهریزی جریان کارگاهی دوباره واردشونده با چند ماشین مبتنیبر مسأله ساخت پل را با هدف حداقلکردن زمان تکمیل آخرین کار ارائه کردهاند. همچنین، سانگ ساوانگ، ستانان، فوجیموتو و جن[xxii] (2015) مدل برنامهریزی دوسطحی را برای حداقلکردن زمان تکمیل آخرین کار در مسأله زمانبندی جریان کارگاهی دوباره واردشونده را با در نظر گرفتن امکان توقف در فرایند تولید بهدلیل نگهدارینکردن موجودی بافر و امکان توقف کار روی ماشین ارائه کردهاند. جیونگ و کیم[xxiii] (2014) مسأله برنامهریزی جریان کارگاهی دوباره واردشونده را با در نظر گرفتن زمآنهای راهاندازی وابسته به توالی عملیات و یا هدف حداقلکردن کل دیرکردها ارائه کردهاند. کانگ و همکاران (2007) مدلی ریاضی برای مسأله برنامهریزی جریان کارگاهی دوباره واردشونده با هدف حداقلکردن میانگین موزون کل دیرکردها و با در نظر گرفتن زمانهای راهاندازی وابسته به توالی عملیات ارائه کردهاند. کایهارا[xxiv] و همکاران (2010) نیز مدلی برای حداقلکردن میانگین کل دیرکردها با در نظر گرفتن برنامهریزی نگهداری و تعمیرات فعال ارائه کردهاند. هوانگ[xxv] و همکاران (2014) مدلی با هدف حداقلکردن کل دیرکردها و زودکردها بهصورت توأمان ارائه کردهاند. نتایج مطالعات اخیر انجامشده در حوزۀ برنامهریزی جریان کارگاهی دوباره واردشونده حاکی از آن است که مواجه با این مسأله تنها با لحاظکردن یک معیار ارزیابی بهخوبی الزامات مربوط به این فضای تصمیمگیری را در دنیای واقعی برآورده نمیسازد؛ ازاینرو مدلهای برنامهریزی جریان کارگاهی دوباره واردشوندۀ چندهدفه طی سالهای اخیر توسعه یافتهاند (ریفی، گوین و داوال7، 2016). دوگاردین[xxvi] و همکاران (2010) مدلی چندهدفه برای برنامهریزی جریان کارگاهی دوباره واردشونده با دو هدف حداقلکردن زمان سیکل تولید و حداکثرکردن میزان استفاده از منابع ارائه کردهاند. همچنین در مطالعات دیگر، دو تابع هدف حداقلکردن زمان تکمیل آخرین کار و کل تأخیرها نیز در نظر گرفته شدهاند (ابراهیمی، فاطمی قمی و کریمی[xxvii]، 2014).
طی سالهای اخیر و متأثر از الزامات فضای کسبوکار، مشاهده میشود که تصمیمِ پراکندهکردن فعالیتهای تولید در تسهیلات مختلف و تخصیص کارها به تسهیلات در کنار تصمیم تعیین توالی انجام کارها توجه پژوهشگران را بهخود جلب کرده است. ابن تصمیمات با هدف افزایش بهرهوری و دستیابی به مزیتهای گوناگون همچون کاهش هزینهها و ریسک تولید انجام میشود؛ ازاینرو در ادبیات، مسأله زمانبندی جریان کارگاهی دوباره واردشوندۀ توزیعشده توسعه یافته است (ریفی، گوین و داوال7، 2016). ریفی و همکارانش (2016) مدلی ریاضی برای زمانبندی کارها در جریان کارهای توزیعشده با در نظر گرفتن امکان بازگشت مجدد کارها به ماشین در حالت قطعیت کامل و بدون در نظر گرفتن محدودیتهای استفاده از منابع مانند برنامۀ نگهداری و تعمیرات ماشین، ارائه کردهاند. این در حالی است که باتوجهبه پیچیدگیهای محیطی، تصمیمگیری دربارۀ توسعۀ بیشتر مدلهای جریان کارهای دوباره واردشوندۀ توزیعشده لازم است.
در دنیای واقعی، نمونههای متفاوتی از عدمقطعیت مانند عدمقطعیت در زمان انجام کارها، در دسترس بودن ماشین و ثابتبودن لیست کارها بر فعالیتهای تولیدی و در پی آن مسأله زمانبندی تولید تأثیرگذار هستند (آرنات و ربدی[xxviii]، 2008؛ کوپانوس، کاپون، گارسیا، اسپونا و پویجانر[xxix]، 2008)؛ درنتیجه نیاز است تا برای افزایش اثربخشی تصمیمات، عدمقطعیتها در برنامهریزی لحاظ شوند (کاتراجینی، والادا و رویز[xxx]، 2015). هنگام مواجهه با عدمقطعیت شدید و در پی آن دسترسینداشتن به دادههای کافی و معتبر برای برآورد تابع احتمال و رفتار پارامتر بررسیشده با استفاده از رویکردهای برنامهریزی احتمالی و فازی، استفاده از رویکرد برنامهریزی استوار پیشنهاد میشود. رویکرد بهینهسازی استوار مبتنیبر مفهوم بودجۀ عدمقطعیت تا حد مطلوبی شرایط دنیای واقعی را هنگامیکه احتمال انحراف مقادیر همۀ پارامترهای غیرقطعی از مقادیر اسمی خود اندک باشد بهخوبی پاسخ میدهد؛ بنابراین، تعداد پارامترهایی که مقادیر آنها نسبت به مقدار اسمی دارای انحراف است با حدی از پیش تعیینشده، تعیین میشود و بودجۀ عدمقطعیت نامیده میشود. سطح بودجه نشاندهندۀ درجۀ محافظهکاری تصمیمگیرنده است. مقادیر کمتر و بیشتر بودجۀ عدمقطعیت بهترتیب بیانگر حداکثر و حداقل مقدار ریسکپذیری تصمیمگیرنده هستند (حسنی، ذگردی و نیکبخش[xxxi]، 2014).
باتوجهبه ماهیت مسائل جریان کارگاهی دوباره واردشونده در حالت عمومی و در حالت توزیعشده که از نوع مسائل با پیچیدگی حل است، نیاز به توسعه و ارائۀ روشهایِ حلِ کارآمد برای حل این مسائل در ابعاد بزرگ و باتوجهبه پیچیدگیهای ذاتی آن است (ریفی، گوین و داوال7، 2016)؛ ازاینرو پژوهشگران روشهای فرا ابتکاری بیشتری نسبت به الگوریتمهای حل دقیق و ابتکاری برای حل این نوع مسائل ارائه دادهاند. لیو[xxxii] (2010)، رائو و چو[xxxiii] (2009)، و لین و لی[xxxiv] (2012) الگوریتم ژنتیک را برای حل جریان کارگاهی دوباره تکرارشونده ارائه کرده است. زو[xxxv] و همکاران (2014 الگوریتم ممتیک را برای حداقلکردن زمان تکمیل آخرین کار در مسأله جریان کارگاهی دوباره واردشوندۀ جایگشتی ارائه کردهاند. یینگ[xxxvi] و همکاران (2014) الگوریتم گریدی پارتو تکرارشونده را برای مسأله جریان کارگاهی دوباره واردشونده با در نظر گرفتن اهداف حداقلکردن زمان تکمیل آخرین کار و کل تأخیرها ارائه کردهاند. چام نانلور[xxxvii] و همکاران (2014) الگوریتم ژنتیک ترکیبی بهبودیافته را برای حل مسأله جریان کارگاهی دوباره واردشونده با در نظر گرفتن پنجرۀ زمانی ارائه کردهاند. چان، پراکاش، ما و ونگ[xxxviii] (2013) الگوریتم فرا ابتکاری ترکیبی مبتنیبر جستجوی ممنوعه و شبیهسازی تبرید را برای حل مسأله جریان کارگاهی توزیعشده ارائه کردهاند. چن17 (2006) الگوریتم فرا ابتکاری جستجوی ممنوعه را برای حداقلکردن زمان تکمیل آخرین کار در مسأله جریان کارگاهی دوباره واردشونده ارائه کردهاند. چوی و کیم[xxxix] (2008) مجموعهای از الگوریتمهای ابتکاری را برای حداقلکردن زمان تکمیل آخرین کار در مسأله جریان کارگاهی دوباره واردشونده ارائه کردهاند. سانگ ساوانگ و ستانان22 (2015) الگوریتم فرا ابتکاری ترکیبی را مبتنیبر الگوریتم ژنتیک و جستجوی ذرات برای حداقلکردن زمان تکمیل آخرین کار در مسأله جریان کارگاهی دوباره واردشونده ارائه کردهاند. جیو[xl] و همکاران (2013) الگوریتم جستجوی ممنوعه را برای حداقلکردن زمان تکمیل آخرین کار در مسأله جریان کارگاهی دوباره واردشوندۀ توزیعشده ارائه کردهاند. لین[xli] و همکاران (2013) نیز الگوریتم گریدی اصلاحشده را برای آن مسأله ارائه کردهاند. نادری و رویز11 (2010) الگوریتم جستجوی پراکنده را برای حل مسأله مشابه ارائه کردهاند.
علاقهمندان به مطالعۀ بیشتر در حوزۀ برنامهریزی جریان کارگاهی دوباره واردشونده به مطالعات چوی[xlii] و همکاران (2009)، چیو[xliii] و همکاران (2010)، و بودهار و مزیانی[xliv] (2010) مراجعه کنند. برای مطالعه درزمینۀ مدلهای برنامهریزی و زمانبندی انجام کارها با انواع حالتهای برگشت کارها به مطالعات بلمان و ارنست[xlv] (1982)، ازوی[xlvi] و همکاران (1992)، لین و لی34 (2011) نیز مراجعه شود.
تعریف مسأله پژوهش
در این مقاله مسأله برنامهریزی جریان کارگاهی جایگشتی توزیعشده دارای کاربرد در صنایع تولید محصولات فناورانه الکترونیکی بررسی شده است. برای این منظور نیاز است تا علاوه بر تعیین توالی و زمانبندی عملیات تولید برای انجام کارها، مراکز تولید نیز انتخاب و فعالیتهای تولیدی در این مراکز درراستای دستیابی به اهداف مدنظر بهنحو مناسب توزیع شوند. لازم به ذکر است که انقطاع در انجام کارها مجاز نیست. مجموعۀ کارها کاملاً از یکدیگر مستقل هستند. ماشینها همواره در دسترس نبوده و امکان بُروز خرابی و یا توقف بهدلیل فعالیتهای نگهداری و تعمیرات در نظر گرفته شده است. عدمقطعیت مدت زمان انجام فعالیت نگهداری و تعمیرات پیشگیرانه با رویکرد بهینهسازی استوار بودجهای نمایش داده شده است. همۀ کارها در زمان صفر در کارگاه حضور دارند. در شکل شماره 1 نمایی از جریان کارگاهی توزیعشده دوباره واردشونده شامل 3 ماشین و 2 سایت تولیدی مستقل و با امکان نگهداری موجودی بافر بدون ظرفیت هر ماشین نمایش داده شده است.
مدلسازی ریاضی
مجموعهها
P: مجموعه سایتهای تولید
M: مجموعه ماشینها با مشخصات و ویژگیهای برابر که در مجموعه تسهیلات تولید استقرار یافتهاند
J: مجموعه کارها
L: مجموعه لایهها با هدف نمایش امکان بازگشت دوباره یک کار به یک ماشین در حین فرایند تولید
O: مجموعه عملیات یکسان برای تمامی کارها که باید بهصورت متوالی انجام شوند
شکل 1- نمای شماتیک جریان کارگاهی دوباره وارد شونده (ریفی و همکاران، 2016)
پارامترها
prjml: زمان انجام کار j روی ماشین m در لایۀ l
sjml: زمان راهاندازی ماشین m برای انجام کار j در لایۀ l
dj: موعد تحویل کار j
B:عدد بزرگ مثبت
fcjp: هزینۀ ثابت تخصیص کار j به تسهیل p،
fc’jm: هزینۀ هر واحد زمانی انجام کار j روی ماشین m،
و : بهترتیب میانگین و انحراف از میانگین مدتزمان انجام تعمیرات پیشگیرانه روی ماشین m
tm: زمان حملونقل بین ماشین m-1 و m
متغیرها
stojmlp: زمان آغاز فعالیت o از کار j روی ماشین m در لایۀ l در سایت تولیدی p
cojmlp: زمان تکمیل فعالیت o از کار j روی ماشین m در لایۀ l در سایت تولیدی p
c’ojmlp: زمان تکمیل فعالیت o از کار j روی ماشین m در لایۀ l در سایت تولیدی pدرصورت انجام تعمیرات پیشگیرانه روی ماشین
tbm: مدت زمان بین دو تعمیر پیشگیرانۀ متوالی
yojmlt: متغیر باینری نشاندهندۀ تخصیص عملیات o از کار j در لایۀ l به ماشین m در زمان t
xjp: متغیر باینری نشاندهندۀ تخصیص کار j به سایت تولید p
xxjj’p: متغیر باینری نشاندهندۀ انجام کار j بلافاصله قبل از کار j’ در سایت تولید p انجام شود
zxjj’p: متغیر باینری نشاندهندۀ انجام کار j قبل از کار j’ در سایت تولید p انجام شود
yxjj’mp: متغیر باینری نشاندهندۀ انجام تعمیرات پیشگیرانه بین دو کار j و j’ روی ماشین mدر سایت تولیدp،
: بودجۀ عدمقطعیت،
Rpf10، Zf10، ys1ojmlp، Rpf10، Zf10، ys1ojmlp، Rpf10، Zf10، ys1ojmlp، Rpf10، Zf10وys1ojmlp: متغیرهای کمکی در مدل قرین استوار برای نمایش عدمقطعیت در زمان انجام تعمیرات پیشگیرانه.
تابع هدف و محدودیتها: در مدل ریاضی ارائهشده، سه تابع هدف بهصورت توأم در نظر گرفته شده است که عبارتاند از (روابط 1 الی 3):
|
(1) |
|
|
(2) |
|
|
(3) |
تابع هدف (1) زمان تکمیل آخرین کار را حداقل میکند. تابع هدف (2) کل هزینههای تولید شامل هزینههای انجام فرایند و تخصیص کارها به هر ماشین را حداقل کند. تابع هدف (3) نیز متوسط زمان دیرکردها را حداقل میکند. لازم به ذکر است که در مسأله جریان کارگاهی جایگشتی عمومی، حداقلکردن زمان تکمیل آخرین کار و جریان کارها در کارگاه هزینههای تولید را حداقل میکنند. این در حالی است که در مسأله جریان کارگاهی توزیعشده بهدلیل در نظر گرفتن هزینههای راهاندازی در تسهیلات مختلف تولید و تصمیمگیری باتوجهبه ارتقاءِ سطح استفاده از تسهیل و راهاندازی تسهیل جدید، دو معیار مذکور، هزینههای کل تولید را حداقل نمیکنند (لین و یینگ[xlvii]، 2013).
|
(4) |
||
|
(5) |
||
|
(6) |
||
|
(7) |
||
|
(8) |
||
|
(9) |
||
|
(10) |
||
|
(11) |
||
|
(12) |
||
|
(13) |
||
|
(14) |
||
|
(15) |
||
|
(16) |
||
|
(17) |
||
|
(18) |
||
|
(19) |
||
|
(20) |
||
|
(21) |
||
|
(22) |
|
|
|
(23) |
|
|
|
(24) |
||
|
(25) |
|
|
|
(26) |
||
|
(27) |
||
|
(28) |
محدودیت (4) تضمین میکند هر کار تنها به یک تسهیل تولیدی تخصیص مییابد. محدودیت (5) مقید میکند ماشینها تککاره هستند و هر ماشین در زمان t تنها یک کار را انجام میدهد. محدودیت (6) نیز نشان میدهد در زمان t هر کار تنها روی یک ماشین انجام میشود. محدودیت (7) وابستگی تخصیص عملیات به هر ماشین درصورت انتخاب آن را نشان میدهد. محدودیت (8) آغاز هر کار بعد از زمان صفر را نشان میدهد. محدودیتهای (9) تا (11) زمان انجام تعمیرات پیشگیرانه (مدتزمان دو تعمیر پیشگیرانه متوالی) را روی هر ماشین مشخص میکنند. در محدودیت (11) عدمقطعیت زمان انجام تعمیرات پیشگیرانه با در نظر گرفتن بودجۀ عدمقطعیت لحاظ شده است. محدودیتهای (14) و (15) بهترتیب نشاندهندۀ وابستگی بین انجام تعمیرات پیشگیرانه با انجام کار روی یک ماشین و توالی انجام کارهای تخصیص دادهشده به یک ماشین است. محدودیتهای (17) و (20) نشان میدهند زمان تکمیل عملیات o از کار jام تابعی از زمان آغاز انجام یک کار، زمان آمادهسازی، زمان انجام فرایند و زمان انجام تعمیرات پیشگیرانه است. محدودیت (16) وضعیت انجام یک کار قبل از یک کار دیگر را نشان میدهد. محدودیت (17) تضمین میکند زمان تکمیل عملیات o از کار j روی ماشین m در لایۀ l در سایت تولیدی p باید مخالف با صفر باشد. محدودیت (18) اطمینان میدهد کار j+1ام تنها زمانی میتواند روی ماشین m در سایت تولیدی p که فعالیت پیشنیاز آن انجام شده باشد. محدودیت (19) اطمینان میدهد زمان آغاز عملیات o از کار j نمیتواند زودتر از زمان تکمیل عملیات قبل آن باشد. مجموعه محدودیتهای خطی (12)، (13)، (15)، (16)، (18)، (19)، (21) و (22) نیز باتوجهبه مدل همتای (قرین) استوار مبتنیبر برنامهریزی استوار بودجهای (ارائهشده در پژوهش برتسیماس و سیم[xlviii] (2004) برای لحاظکردن عدمقطعیت در محدودیتهای (11)، (14)، (17) و (20) زمان انجام تعمیرات پیشگیرانه مبتنیبر رویکرد بودجهبندی در نظر گرفته شدهاند.
الگوریتم حل پیشنهادی مبتنیبر الگوریتم فرا ابتکاری ترکیبی
در این بخش، الگوریتم فرا ابتکاری ترکیبی جدیدی باتوجهبه ماهیت مسأله جریان کارگاهی که از نوع مسائل با پیچیدگی حل بالا بوده، ارائه شده است. الگوریتم ارائهشده مبتنیبر جستجوی همسایگی وسیع انطباقپذیر با اندازۀ جمعیت پویا و الگوریتم شبیهسازی تبرید است. در الگوریتم جستجوی همسایگی وسیع انطباقپذیر از مجموعهای از روشهای جدید برای تخریب و بازسازی جواب و فرایند سیستماتیکِ انتخاب، براساس سابقۀ عملکرد هریک از روشهای تعمیر و تخریب استفاده شده است. فرایند تکرارپذیر جستجوی جواب مبتنیبر الگوریتم شبیهسازی تبرید با دمای اولیه آغاز میشود و سپس این دما با نرخی مشخص کاهش خواهد یافت. نرخ تبریدِ کم باعث طولانیترشدن فرایند جستجو و نرخ تبرید سریع باعث افزایش احتمال قرارگرفتن در دام بهینۀ محلی خواهد شد. شبهکد الگوریتم ترکیبی پیشنهادشده در شکل 2 نمایش داده شده است.
نمایش جواب: هر جواب با ارائهای دو بعدی نمایش داده خواهد شد و ابعاد آن در شکل 3 نمایش داده شده است. با کدگشایی از این ساختارِ نمایشِ جواب مقادیر متغیرهای مربوط به تخصیص کارها به تسهیلات تولیدی و توالی عملیات کارها در هر تسهیل تعیین میشود. عملیات نگهداری و تعمیرات پیشگیرانه نیز مجموعه کار جدیدی است که در کنار کارهای اصلی تعریف میشود. این نحوۀ نمایش باعث تسهیل در در نظر گرفتن موقعیت اعمال تعمیر پیشگیرانه نسبت به دیگر کارها روی هر ماشین در هر سایت خواهد شد.
عملگرهای جستجوی همسایگی: باتوجهبه انتخاب الگوریتم جستجوی همسایگی سریع، با استفاده از دو عملگر تخریب و تعمیر بهصورت متوالی، جستجو برای یافتن جوابهای جدید مبتنیبر جواب در اختیار، انجام خواهد شد. در توسعۀ عملگرهای تخریب و تعمیر تلاش شده است تا باتوجهبه فضای جواب مسأله در حال بررسی، عملگرها بهخوبی بتوانند در ایجاد تنوع و تمرکز در فرایند جستجوی جواب ایفای نقش کنند. در ادامه، این عملگرها و نحوۀ پیادهسازی آنها توضیح داده شده است.
عملگر تخریب: با اعمال عملگر تخریب N- روی جواب نمونۀ بررسیشده، امکان توسعۀ جواب درراستای رسیدن به جواب جدید فراهم میشود. این در حالی است که در استفاده از این عملگر باید توجه شود که دو مفهوم تنوع و عمقبخشیدن به فضای جستجو بهخوبی مدنظر قرار گیرد. عملگر تخریب روی بخشهای مختلف جواب نظیر توالی انجام کارها و یا تخصیص کارها به تسهیلات تولید بهتنهایی و یا هر دو بخش بهصورت توأم اعمالشدنی است. در جدول 1، تکنیکهای استفادهشده برای چگونگی اعمال این عملگر ارائه شده است. اندازۀ دامنۀ تخریب در هر مرحله از الگوریتم جستجوی همسایگی وسیعِ انطباقپذیر با هدف تنوعبخشی در ابتدای فرایند جستجو و تمرکز در مراحل پایانی، متفاوت در نظر گرفته خواهد شد (رابطه 29).
|
(29) |
عملگر تعمیر: عملگر تعمیر N+ عملیات اصلاح جواب ناقص ایجادشده بهوسیلۀ عملگر تخریب را انجام میدهد. هدف از اعمال عملگر تعمیر عبارت از ایجاد بهبود در جوابهای بهدستآمده و ایجاد تنوع در آنها با هدف یافتن جوابهای نامغلوب جدید است. برای این منظور از تکنیکهای مختلفی در اعمال عملگر تعمیر روی جواب استفاده میشود (جدول 2). مجموعه جوابهای پارتو ذخیرهشده در مجموعۀ آرشیو، نقش مهمی در پیادهسازی عملگر تعمیر دارند.
انتخاب عملگرهای تعمیر و تخریب مبتنیبر رویکردی سیستماتیک انطباقپذیر است؛ یعنی سابقۀ عملکرد هر عملگر انتخابشده، در شانس انتخاب آن در مراحل آتی الگوریتم جستجو تأثیرگذار است. انتخاب عملگرها با استفاده از چرخۀ رولت انجام میشود (رابطۀ 30). بهروزرسانی وزن هریک از عملگرها نیز باتوجهبه مشارکت عملگر در بهبود مقدار تابع هدف با استفاده از رابطۀ (31) انجام خواهد شد. ضریب تعدیل λ نیز میزان وابستگی وزن جدید را به سابقۀ عملگر بررسیشده نشان میدهد. رابطۀ (32) نشاندهندۀ وزن عملگر در پیادهسازی آن است و تابعی از کیفیت جواب جدید بهدستآمده است. برای این منظور چهار حالت در نظر گرفته شده است که بهترتیب عبارتاند از: (1) جواب جدید بهترین جواب موجود را مغلوب کند؛ (2) جواب جدید، جواب قبلی را مغلوب کند؛ (3) جواب جدید، جواب قبلی را مغلوب نکند؛ اما باتوجهبه معیار انتخابِ متأثیر از شبیهسازی تبرید پذیرفته شود؛ (4) جواب جدید رد شود. در رابطۀ (31)، شاخص میزان مشابهت جواب جدید با جواب موجود نیز در نظر گرفته شده است. تنوع جوابهای ایجادشده تأثیر زیادی بر کیفیت جواب نهایی و توانمندی فرایند جستجوی همسایگی خواهد داشت. باتوجهبه بررسی مسألهای چندهدفه و مواجه با چند معیار ارزیابی بهصورت همزمان، میزان مشابهت با استفاده از محاسبۀ شاخص مسافت اقلیدسی سهبعدی انجام خواهد شد (رابطۀ 34).
(30) |
||
|
(31) |
||
|
(32) |
||
|
(33) |
||
|
(34) |
||
یافتههای پژوهش و تحلیل نتایج
در این بخش، نتایج تحلیل دادهها و یافتههای پژوهش درقالب نتایج محاسباتی حل مدل ریاضی (توابع هدف و محدودیتهای 1 تا 28) با هدف بررسی اثر عدمقطعیت بر عملکرد زمانبندی کارها در مسأله جریان کارگاهی جایگشتی با برگشت دوبارۀ کارها ارائه شده است. برای این منظور، 21 مسأله نمونۀ اصلی و الگوی تولید دادهها از مطالعات ریفی7 و همکاران (2016) بهعنوان نزدیکترین مسأله مشابه بررسیشده در ادبیات موضوع که در این مطالعه نیز توسعه یافته است، برداشت شده است (جداول 3 و 4).
شکل 2- شبه کد الگوریتم ترکیبی جستجوی همسایگی وسیع انطباقپذیر و شبیهسازی تبرید
|
شماره کارها |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
تسهیل تولید تخصیص دادهشده |
1 |
4 |
4 |
3 |
2 |
1 |
4 |
1 |
3 |
2 |
|
توالی عملیات |
1 |
3 |
1 |
2 |
1 |
2 |
2 |
3 |
1 |
2 |
شکل 3- نمایش جواب در الگوریتم فرا ابتکاری ترکیبی ارائهشده برای برنامهریزی 10 کار در 4 سایت تولید بهصورت نمونه
جدول 1- الگوی عملگرهای تخریب و نحوۀ پیادهسازی آنها روی جواب نمونۀ بررسیشده
|
عملگر تخریب |
نحوۀ پیادهسازی |
|
تخریب تصادفی |
برای تنوعبخشی به فرایند جستجو، یک بخش از ساختار جواب بهصورت تصادفی تخریب خواهد شد. این فرایند تصادفی نقش مؤثری در خارجشدن از بهینۀ محلی خواهد داشت. انواع حالات تخریب تصادفی عبارتاند از:
|
|
تخریب تسهیلات با ظرفیت آزاد |
در این راستا، تخصیصهای در نظر گرفته شده برای تسهیل تولیدی با بیشترین ظرفیت آزاد از جواب حذف خواهند شد. هدف از این اقدام، تخصیص کارهای مربوط بدین تسهیلات به تسهیلات با ظرفیت آزاد کمتر و درنهایت بستن تسهیلاتی که سطح بالایی از ظرفیت آنها اشغال نشده است. با کاهش تعداد تسهیلات تولیدی، کل هزینههای راهاندازی نیز کاهش خواهد یافت. |
|
تخریب تسهیلات با ظرفیت مازاد |
رویکرد این روش تخریب نقطۀ مقابل تخریب تسهیل با ظرفیت آزاد است. در این روش تخریب بخشهایی از جواب حذف میشود که مرتبط با تخصیص کارها با بیشترین ظرفیت است. با اعمال تصادفی این روش تخریب و سپس تخصیص کارهای انتخابشده به دیگر تسهیلات با ظرفیت آزاد در برنامهریزی ظرفیت تسهیلات تسطیح رخ میدهد. هدف نهایی از این اقدام، کاهش کلی زمان تکمیل آخرین کار و هزینههای سربار تولید است. |
|
تخریب برمبنای زمان تکمیل آخرین کار |
بخش بحرانی جواب باتوجهبه معیار زمان تکمیل آخرین کار از جواب با هدف برنامهریزی بهتر در فرایند تعمیر، برداشته میشود. این اقدام به تمرکز بیشتر در فرایند جستجو منجر میشود. |
|
تخریب مبتنیبر دیرکرد |
این عملگر، بخشی از جواب را حذف میکند که بیشترین مقدار دیرکرد ناشی از زمان تکمیل زیاد و یا موعد تحویل بسیار نزدیک را دارد. |
|
تخریب مبتنیبر دیرکرد در آغاز کار |
این عملگر بخشی از جواب را که دارای بیشترین مدتزمان دیرکرد در آغازشدن کار است، انتخاب و حذف میکند. مدتزمان دیرکرد در آغاز کار برابر است با مدتزمان سپریشده از ورود کار به موجودی بافر تا آغاز عملیات تولیدی روی آن. این اقدام در کاهش هزینههای موجودی در جریان ساخت در پی کاهش سطح موجودیهای بافر تأثیرگذار است. |
جدول 2- الگوی عملگرهای تخریب و نحوۀ پیادهسازی آنها روی جواب نمونۀ بررسیشده
|
عملگر تخریب |
نحوۀ پیادهسازی |
|
تعمیر تصادفی |
برای تنوعبخشیدن به فرایند جستجو در اعمال عملگر تعمیر، از رویکرد انتخاب تصادفی با شانس برابر برای هریک از اعضای مجموعه آرشیو در فرایند تعمیر جواب تخریبشده استفاده میشود. انواع حالات تعمیر تصادفی عبارتاند از:
|
|
ترکیب مبتنیبر آرشیو با هدف حداقلکردن زمان تکمیل آخرین کار |
از میان جوابهای حاضر در مجموعه آرشیو، جواب با کمترین میزان زمان تکمیل آخرین کار، مبنای واردکردن بخشهای جداشده از جواب در فرایند تخریب و درنهایت تعمیر جواب جدید خواهد بود. تلاش برای کاهش زمان تکمیل کارها درراستای کاهش میزان دیرکرد نیز مفید است. |
|
ترکیب مبتنیبر آرشیو باهدف حداقلکردن هزینۀ کل |
در این حالت، عملیات تعمیر جواب تخریبشده مبتنیبر جواب انتخابشده از مجموعۀ آرشیو با کمترین هزینه خواهد بود. |
برای نمایش سطوح متفاوت محافظهکاری تصمیمگیرنده، پنج سطح شامل 0، 25، 50، 75 و 100 درصد کل بودجۀ عدمقطعیت برای هریک از مسائل نمونۀ اصلی نمایش داده شده در جدول 3، لحاظ شده است؛ درنتیجه، 105 مسأله نمونه درمجموع بررسی شده است. دو سطح 0 و 100 درصد بودجه بهترتیب نشاندهندۀ قطعیت و عدمقطعیت کامل است. سطوح میانی نیز حد متوسطی از محافظهکاری تصمیمگیرنده را نشان میدهند. تنظیم تمامی پارامترهای الگوریتم فرا ابتکاری ترکیبی پیشنهادی با استفاده از روش طراحی آزمایشهای تاگوچی انجام شده است و نتایج آن در جدول 5 ارائه شده است.
نخست، کیفیت جوابهای بهدستآمده از الگوریتم فرا ابتکاری ترکیبی پیشنهادی در مقایسه با الگوریتم فرا ابتکاری ارائهشده برای مسأله مشابه در ادبیات موضوع (جستجوی همسایگی سریع انطباق پذیر)، براساس دو معیار ارزیابی متداول ارائهشده در ادبیات موضوع و پس از 10 بار اجرای الگوریتمهای حل مدنظر، بررسی شده است. این دو معیار ارزیابی بهترتیب عبارتاند از: متوسط تعداد جوابهای پارتو بهدستآمده در هر اجرای الگوریتم (معیار 1) و متوسط نرخ جوابهای پارتو بهدستآمده برحسب درصد بهوسیلۀ یک الگوریتم بهطوریکه با جوابهای پارتو دیگر الگوریتم بررسیشده، مغلوب نشود (معیار 2). زمان حل برحسب ثانیه نیز سومین معیار ارزیابی عملکرد الگوریتمها لحاظ شده است. نتایج مقایسۀ عملکرد الگوریتم فرا ابتکاری پیشنهادی با روش حل محدودیت اپسیلون آگمنت با نرمافزار بهینهسازی گمز حاکی از کارایی روش حل پیشنهادی از منظر زمان حل و عملکرد برابر آن در حل مسائل با ابعاد کوچک، متوسط و بزرگ است (جدول 6).
جدول 3- مسائل نمونه
|
مسأله نمونه |
بودجۀ عدمقطعیت |
بعد مسأله (n×p) |
دسته |
|
(5-1) |
(100-75-50-25-0) |
(2×4) |
1 |
|
(10-6) |
(100-75-50-25-0) |
(3×4) |
|
|
(15-11) |
(100-75-50-25-0) |
(4×4) |
|
|
(20-16) |
(100-75-50-25-0) |
(2×6) |
2 |
|
(25-21) |
(100-75-50-25-0) |
(3×6) |
|
|
(30-26) |
(100-75-50-25-0) |
(4×6) |
|
|
(35-31) |
(100-75-50-25-0) |
(2×8) |
3 |
|
(40-36) |
(100-75-50-25-0) |
(3×8) |
|
|
(45-41) |
(100-75-50-25-0) |
(4×8) |
|
|
(50-46) |
(100-75-50-25-0) |
(2×10) |
4 |
|
(55-51) |
(100-75-50-25-0) |
(3×10) |
|
|
(60-56) |
(100-75-50-25-0) |
(4×10) |
|
|
(65-61) |
(100-75-50-25-0) |
(2×12) |
5 |
|
(70-66) |
(100-75-50-25-0) |
(3×12) |
|
|
(75-71) |
(100-75-50-25-0) |
(4×12) |
|
|
(80-76) |
(100-75-50-25-0) |
(2×14) |
6 |
|
(85-81) |
(100-75-50-25-0) |
(3×14) |
|
|
(90-86) |
(100-75-50-25-0) |
(4×14) |
|
|
(95-91) |
(100-75-50-25-0) |
(2×16) |
7 |
|
(100-96) |
(100-75-50-25-0) |
(3×16) |
|
|
(105-101) |
(100-75-50-25-0) |
(4×16) |
محدودیت زمان 20 هزار ثانیهای برای دریافت جواب از نرمافزار اعمال شده است. امکان دریافت نتایج مربوط به معیار 1 از نرمافزار میسر نبوده و مقایسه برمبنای معیارهای 2 و 3 انجام میشود. علاوه بر آن، نتایج بهدستآمده نشان میدهد که با افزایش ابعاد مسأله، کارایی روش حل اپسیلون محدودیت اگمنت ازنظر زمان بهشدت کاهش مییابد. برتری کامل کیفیت جواب و زمان حل حاصل از پیادهسازی الگوریتم فرا ابتکاری چندهدفه پیشنهادی برای حل مسائل با ابعاد بزرگ نیز کاملاً مشهود است.
جدول 4- محدودۀ تولید پارامترها
|
محدوده داده |
پارامتر |
محدوده داده |
پارامتر |
|
U(5,10) |
fc’ |
U(1,99) |
pr |
|
U(10,40) |
U(1,99) |
S |
|
|
U(1,5) |
U(20,2000) |
d |
|
|
U(2,4) |
t |
U(1000;2000) |
fc |
جدول 5- فاکتورهای طراحی برای تنظیم پارامترها
|
فاکتور طراحی |
سطوح |
|
تکرار الگوریتم جستجوی همسایگی سریع |
(200-150-100) |
|
دمای اولیه |
(400-150-100) |
|
بیشینه تعداد تکرار در هر دما |
(30-20-10) |
|
حد بالای ضریب پایان جستجو در یک دما |
(20-15-10) |
|
حد بالای ضریب انجماد |
(50-30-20) |
جدول 6- ارزیابی عملکرد الگوریتم پیشنهادی
|
الگوریتم پیشنهادی |
اپسیلون محدودیت آگمنت |
مسأله نمونه |
||||
|
معیار3 |
معیار2 |
معیار1 |
معیار3 |
معیار2 |
معیار1 |
|
|
12/57 |
95/25 |
4129/0 |
06/210 |
13/30 |
- |
15 |
|
11/152 |
80/28 |
5972/0 |
04/10832 |
70/28 |
- |
30 |
|
06/398 |
10/38 |
6543/0 |
93/3485 |
15/36 |
- |
45 |
|
47/1200 |
30/36 |
7810/0 |
49/17578 |
12/31 |
- |
60 |
|
18/3019 |
80/13 |
5114/0 |
- |
- |
- |
75 |
|
07/5631 |
20/11 |
5304/0 |
- |
- |
- |
90 |
|
29/6594 |
83/11 |
5713/0 |
- |
- |
- |
105 |
نتایج ارائهشده در جدول 7 نشاندهندۀ برتری الگوریتم فرا ابتکاری پیشنهادی در مقایسه با الگوریتم فرا ابتکاری مبتنیبر جستجوی همسایگی وسیع انطباقپذیر دارد. در جدول 7، با هدف ارزیابی عملکرد و کارایی روش حل پیشنهادی، مقایسۀ عملکرد بین الگوریتمهای ارزیابیشونده تنها برای بزرگترین سایز مسأله در هر دسته از نظر ابعاد و بودجۀ عدمقطعیت (نمایش دادهشده در جدول 3) ارائه شده است. نتایج مقایسه حاکی از اثربخشی فرآیند جستجوی محلی توسعه دادهشده در عمقبخشیدن به جستجو است. الگوریتم جستجوی همسایگی وسیع انطباقپذیر از نظر زمان جستوجو برتر از فرا ابتکاری ترکیبی پیشنهادی است؛ اگرچه این برتری خود متأثر از کیفیت کم جواب آن قرار خواهد گرفت. نتایج اعمال آزمون آماری برای سنجش برابری عملکرد دو الگوریتم ارزیابیشونده برای تمامی مقایسههای ممکن بین عملکرد دو الگوریتم، حاکی از اختلاف آماری معنادار در سطح اطمینان 95 درصد است (جدول 8). باتوجهبه نرمالبودن دادهها، از آزمون t مستقل استفاده شده است. فرض صفر و فرض مقابل بهترتیب عبارتاند از عملکرد دو الگوریتم و برتری الگوریتم پیشنهادی نسبت به الگوریتم مقایسهشده.
جدول 7- ارزیابی عملکرد الگوریتم پیشنهادی
|
الگوریتم پیشنهادی |
الگوریتم مقایسهشده |
مسأله نمونه |
||||
|
معیار3 |
معیار2 |
معیار1 |
معیار3 |
معیار2 |
معیار1 |
|
|
12/57 |
95/25 |
4129/0 |
01/72 |
30/39 |
7270/0 |
15 |
|
11/152 |
80/28 |
5972/0 |
23/180 |
43/34 |
6991/0 |
30 |
|
06/398 |
10/38 |
6543/0 |
19/479 |
23/48 |
9009/0 |
45 |
|
47/1200 |
30/36 |
7810/0 |
21/1308 |
13/47 |
9207/0 |
60 |
|
18/3019 |
80/13 |
5114/0 |
26/3392 |
71/18 |
6120/0 |
75 |
|
07/5631 |
20/11 |
5304/0 |
74/5900 |
01/18 |
6523/0 |
90 |
|
29/6594 |
83/11 |
5713/0 |
69/6801 |
23/15 |
6914/0 |
105 |
در شکل 4، مجموعه نقاط پارتوی یافتشده برای بهینهسازی همزمان، حداقلسازی زمان تکمیل آخرین کار و هزینههای کل زمانبندی برای پنج بودجۀ عدمقطعیت و بزرگترین مسأله نمونۀ درحال بررسی (مسائل 105-101) نشان داده شده است.
جدول 8- ارزیابی عملکرد الگوریتم پیشنهادی (آزمون tمستقل) در سطح معناداربودن 05/0
|
مقادیر p-value مقایسۀ دو الگوریتم از منظر |
مسأله نمونه |
||
|
معیار 3 |
معیار 2 |
معیار 1 |
|
|
000/0 |
000/0 |
000/0 |
15-1 |
|
000/0 |
000/0 |
000/0 |
30-16 |
|
000/0 |
000/0 |
000/0 |
45-31 |
|
000/0 |
000/0 |
000/0 |
60-46 |
|
000/0 |
000/0 |
000/0 |
75-61 |
|
000/0 |
000/0 |
000/0 |
90-76 |
|
000/0 |
000/0 |
000/0 |
105-91 |
همانطورکه مشاهده میشود، حداقلکردن زمان تکمیل آخرین کار لزوماً باعث کاهش هزینهها نمیشود؛ این در حالی است که با افزایش بودجۀ عدمقطعیت، هزینههای کلی برنامهریزی نیز افزایش مییابد. این موضوع حاکی از برنامهریزی محافظهکارانه در برابر شدتیافتن عدمقطعیت است. از سوی دیگر، افزایش بودجۀ عدمقطعیت زمان تعمیر ماشینها تأثیر منفی بر زمان تکمیل آخرین کار خواهد داشت؛ بهطوریکه درنتیجۀ آن زمان تکمیل آخرین کار کاهش مییابد (شکل 4). در شکل 5، افزایش هزینهها درنتیجۀ کاهش متوسط کل دیرکردها برای بزرگترین مسأله نمونه مشاهده میشود. علاوه بر آن مشاهده میشود که با افزایش بودجۀ عدمقطعیت، هزینۀ انجام کارها و متوسط دیرکردها نیز افزایش یافتهاند. درنهایت تأثیر اِعمالکردن و نکردن برنامههای نگهداری و تعمیرات پیشگیرانه بر عملکرد برنامهریزی و زمانبندی انجامشده در شکل 6 برای مسأله نمونه در ابعاد بزرگ مشاهده میشود. نتایج حاکی از اثرگذاری معنادار اِعمال نگهداری و تعمیرات پیشگیرانه بر شاخصهای عملکردی مدنظر بهصورت معنادار است.
شکل 4- جبهۀ جواب پارتو باتوجهبه معیارهای ارزیابی زمان تکمیل آخرین کار و هزینههای کل برنامهریزی برای بودجههای عدمقطعیت
شکل 5- جبهۀ جواب پارتو باتوجهبه معیارهای ارزیابی متوسط دیرکردها و هزینههای کل برنامهریزی برای بودجههای عدمقطعیت
شکل 6- ارزیابی اعمالکردن و نکردن سیاست نت پیشگیرانه
نتیجهگیری
در این مقاله مدل ریاضی جامعی برای مسأله برنامهریزی جریان کارگاهی جایگشتی دوباره واردشوندۀ توزیعشده با در نظر گرفتن برنامهریزی نگهداری و تعمیرات پیشگیرانه و عدمقطعیت زمان انجام تعمیرات قرار گرفته است. در مدل ارائهشده سه تابع هدف حداقلکردن زمان تکمیل آخرین کار، هزینههای کل برنامهریزی و متوسط زمان دیرکردها لحاظ شده است. باتوجهبه ماهیت توزیعشدۀ مسأله بررسیشده، تصمیمات انتخاب تسهیلات تولید، تخصیص کارها به تسهیلات پراکندۀ توزیع و تعیین توالی انجام کارها بهصورت همزمان اتخاذ میشود. بهدلیل فناوری سطح بالای ماشینآلات تولیدی و عدمقطعیت زیاد در زمان تعمیر آنها، عدمقطعیت مذکور با استفاده از رویکرد برنامهریزی استوار بودجهای برای نمایش سطوح مختلف عدمقطعیت استفاده شده است. باتوجهبه پیچیدگیهای حل زیاد مدلِ ارائهشده، یک الگوریتم فرا ابتکاری ترکیبی جدید مبتنیبر جستجوی همسایگی وسیع انطباقپذیر و شبیهسازی تبرید ارائه شده است. نتایج حل حاکی از کارایی مدل ریاضی و روش حل ارائهشده برای مواجه با پیچیدگیهای مسأله در حال بررسی است. نتایج نشان میدهد با افزایش سطح عدمقطعیت، سطح محافظهکاری تصمیمات ایجادشده بهنحو معناداری افزایش خواهد یافت. عملکرد الگوریتم پیشنهادی با الگوریتم مشابه ارائهشده در ادبیات موضوع سنجیده شده و نتایج حاکی از کارایی روش حل پیشنهادی ازنظر کیفیت جواب است. دلیل این برتری بهبود ایجادشده در فرایند جستجوی محلی الگوریتم پیشنهادی بهواسطۀ توسعۀ روشهای تخریب و تعمیر جواب همسایگی است.
باتوجهبه اهمیت مقولۀ آمادهسازی ماشینآلات و تأثیر آن در فرایند برنامهریزی، در نظر گرفتن زمان آمادهسازی وابسته بهتوالی عملیات اثربخشی تصمیمات را در دنیای واقعی ارتقاء میدهد. همچنین در نظر گرفتن دیگر پویاییهای محیط تصمیمگیری همچون لیست کارهای پویا و امکان تغییر در مجموعه کارها و یا متفاوتبودن زمان حضور کارها در سیستم، یکی دیگر از زمینههای پژوهشی است که برای پژوهشگران پیشنهاد میشود. باتوجهبه پیچیدگیهای زیاد حل مسأله برنامهریزی جریان کارگاهی، توسعۀ روش حل کارآمد برای حل مسائل توسعهیافته در ابعاد بزرگ و ارزیابی عملکرد الگوریتمهای پیشنهادی باتوجهبه معیارهای ارزیابی بسیار متنوع ارائهشده در ادبیات موضوع برای روشهای حل فرا ابتکاری چندهدفه زمینۀ پژوهش دیگری است که معرفی میشود.
[i] Pinedo
[ii] Vargas-Villamil & Rivera
[iii] Choi, Kim, & Lee
[iv] Bispo & Tayur
[v] Xu, Yin, Cheng, Wu, & Gu
[vi] Lin, Lee, & Ho
[vii] Rifai, Nguyen, & Dawal
[viii] Gupta & Sivakumar
[ix] Ruiz, García-Díaz, & Maroto
[x] Moon, Kim, & Hur
[xi] Naderi & Ruiz
[xii] Kasperski, Kurpisz, & Zieliński
[xiii] Yenisey & Yagmahan
[xiv] Graves
[xv] Pan & Chen
[xvi] Chen, Pan, & Lin
[xvii] Chen
[xviii] Chen, Pan, & Wu
[xix] Chu, Chu, & Desprez
[xx] Sun, Zhang, Gao, & Wang
[xxi] Yang
[xxii] Sangsawang, Sethanan, Fujimoto, & Gen
[xxiii] Jeong & Kim
[xxiv] Kaihara
[xxv] Huang
[xxvi] Dugardin
[xxvii] Ebrahimi, Fatemi Ghomi, & Karimi
[xxviii] Arnaut & Rabadi
[xxix] Kopanos, Capon-Garcia, Espuna, & Puigjaner
[xxx] Katragjini, Vallada, & Ruiz
[xxxi] Hasani, Zegordi, Nikbakhsh
[xxxii] Liu
[xxxiii] Rau & Cho
[xxxiv] Lin & Lee
[xxxv] Xu
[xxxvi] Ying
[xxxvii] Chamnanlor
[xxxviii] Chan, Prakash, Ma, & Wong
[xxxix] Choi & Kim
[xl] Gao
[xli] Lin
[xlii] Choi
[xliii] Chu
[xliv] Boudhar & Meziani
[xlv] Bellman & Ernest
[xlvi] Uzsoy
[xlvii] Lin & Ying
[xlviii] Bertsimas, D., & Sim
)