به‌کارگیری الگوریتم شاخه و حد با حدودِ پایین قوی برای حل مسئلۀ حداقل‌کردن زمان انجام کل کارها روی ماشین پردازندۀ انباشته

نوع مقاله: مقاله پژوهشی

نویسندگان

1 کارشناس ارشد دانشکدۀ مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس، تهران، ایران

2 استادیار دانشکدۀ مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس، تهران، ایران

10.22108/jpom.2019.108815.1103

چکیده

در این مقاله مسئلۀ زمان‌بندی ماشین پردازندۀ انباشته با فرض وجود کارهایی با اندازۀ غیریکسان و با هدف حداقل‌کردن زمان انجام کل کارها (Cmax) بررسی شده است. هدف این مقاله، حل مسئلۀ مدنظر با بهره‌گیری از حدود پایین قوی و با استفاده از الگوریتم شاخه و کران حد، یکی از روش‌های حل دقیق، است. در این الگوریتم از دو روش جدید به‌نام‌های  و  برای تولید حد پایین استفاده و نتایج با حد پایین موجود در ادبیات به‌نام  مقایسه شده است. برای ارزیابی عملکردِ روش ارائه‌شده، دسته‌ای از نمونه مسائل به‌صورت تصادفی تولید و روش شاخه و حد با حدود پایینِ متفاوت روی این مسائل آزمایش شده است. نتایج محاسبات نشان می‌دهد در الگوریتم شاخه و کران وقتی اندازۀ کارها نسبت به ظرفیت ماشین بزرگ باشد، حد پایین  بهترین عملکرد را دارد و زمانی‌که اندازۀ کارها نسبت به ظرفیت ماشین کوچک باشد (حداکثر به‌اندازۀ G نصف ظرفیت ماشین)، الگوریتم با حد پایین  عملکرد بهتری دارد. همچنین زمانی‌که اندازۀ کارها متوسط باشد،  بهترین عملکرد را دارد. 

کلیدواژه‌ها


عنوان مقاله [English]

A branch and bound algorithm equipped with tighter lower bound values for makespan minimization on a batch processing machine

نویسندگان [English]

  • Nahid Hashemi 1
  • Ali Husseinzadeh Kashan 2
1 Department of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran
2 Department of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran
چکیده [English]

In this paper, the problem of scheduling jobs with non-identical sizes has been studied on a single-batch processing machine, in order to minimize the makespan. Using new lower bounds, a branch and bound algorithm has been proposed to solve the problem. In this algorithm, two new methods have been used to generate lower bounds and results have been compared with the existing lower bound in literature. In order to evaluate the performance of the proposed method, test problems have been randomly generated and branch and bound algorithm has been tested with different lower bounds on these cases. Findings indicated that when the size of the jobs is large compared to the capacity of the machine, the branch and bound algorithm with the new lower bound has the best performance. When the size of the jobs is small compared to the capacity of the machine (up to half the capacity of the machine), the algorithm with existing lower bound has better performance. In addition, when the size of the jobs is neither large nor small, the lower bounds provide the best performance.
Introduction: Based on predictions, services are a key component of the growth of the global economy in future (Arnold et al. 2011). Acording to Jane and Kumar (2012), services play a critical role in a supply chain. Also, according to Wang et al. (2015), a "product" or "service" must exist in each supply chain which is produced by the upstream sectors and delivered to downstream. Recently due to increasing customer expectations, companies’ competition has been replaced by the supply chains competition and as a result, competition has been increased in the simultaneous supply of products and services. This has led to challenges in integrating companies and in coordinating the materials, information and financial flow that were previously overlooked. Accordingly, a new managerial philosophy has been developed known as Product-Service Supply Chain (PSSC) (Stanley & Wisner, 2002). This study seeks to develop a performance evaluation model for the product-service supply chain in the home appliance industry, which is finally solved using Adaptive Neuro-Fuzzy Inference System (ANFIS).
Design/Approach: In this paper, performance evaluation constructs and criteria of service supply chain are identified by reviewing the literature and exploratory and confirmatory factor analysis and then, the performance evaluation of service supply chains in Iran's home appliance industry has been performed using these constructs, criteria and ANFIS.
Findings and Discussion: Based on the findings, ten main extracted constructs can be suggested for the performance evaluation of the supply chain. They include "Operational Performance (OP)", "Strategic Performance (SP)", "Financial Performance (FP)", "Performance of Information and Communication Technology (PICT)", “Return Performance” (REP), “Risk Performance (RIP)”, “Logistic Performance (LP)”, “Market Performance (MP)”, “Internal Structure Performance (PIS)” and “Growth and Innovation Performance (PGI)”, among which, the Strategic Performance (SP) and Return Performance (REP) are the most important and the least important constructs, respectively.
Conclusions
Based on the findings, the following practical recommendations are suggested to the companies:

Enhancing the demand forecasts performance and utilizing more appropriate methods and software to improve forecasts in demand and order management areas.
Improving the return management status by increased attention and more investment in return management processes.
Effective investment in service development management to enhance the R&D services performance.
Utilizing risk management approaches and methods to identify and take preventive actions on the risks in the companies’ service supply chain.

References
Arnold, J.M., Javorcik, B.S., & Mattoo, A. (2011). “Does services liberalization benefit manufacturing firms? evidence from the Czech Republic”. Journal of International Economics, 85(1), 136-146.
Azar, A., Gholamzadeh, R., & Ghanavati, M. (2012). Path-Structural Modeling in Management: SmartPLS Application, Tehran: Publishing Knowledge Look.
Rezaei Moghadam S., Yousefi, O.,  Karbasisan, M. and Khayambashi, B. (2018). “Integrated production-distribution planning in a reverse supply chain via multi-objective mathematical modeling; case study in a high-tech industry”. Production and Operations Management, 9(2), 57-76.
Zhou, H., & Benton, W. C. (2007). “Supply chain practice and information sharing”. Journal of Operations Management, 25(6), 1348-1365.

کلیدواژه‌ها [English]

  • Product-service supply chain
  • Performance Evaluation
  • Fuzzy neural network
  • Factor Analysis
  • home appliance industry

مقدمه

امروزه مسائل زمان‌بندی در اکثر محیط­های اقتصادی به‌صورت مزیت رقابتی مطرح و شناخته شده است. طی سه‌دهۀ اخیر به مسائل زمان‌بندی که در آنها انباشته‌سازی کارها مطرح است توجه زیادی شده است، به‌‌نحوی‌‌که امروزه زمان‌بندی انباشته‌ها در سیستم تولید یکی از سیاست‌های معمول در بسیاری از صنایع است. علت این انگیزش در افزایش سرعت تولید و کاهش هزینه­های مرتبط با آن ازطریق سیاست تولید انباشته‌ای به‌جای تولید منفرد کارها است. ماشین‌های پردازش انباشته[i] در سیستم‌های تولید انباشته‌ای قابلیت پردازش دسته‌ای از کارها را درقالب یک انباشته به‌طور هم‌زمان دارند. منظور از یک‌ انباشته، گروهی از کارهاست که به‌طور هم‌زمان زیر عملیات ماشین قرار می‌گیرند؛ بنابراین ظرفیت ماشین تعیین‌کنندۀ اندازۀ انباشته است. خانوادۀ مسائل زمان‌بندی ماشین­های پردازندۀ انباشته با کارهای با اندازۀ غیریکسان در دسته مسائل NP-hard قرار می­گیرد (اوزوی[ii]، 1994).

در ادبیات زمان‌بندی تولید انباشته‌ای، مثال‌های متعددی از ایستگاه‌های تولیدی ذکر شده‌اند که در آن از ماشین‌های پردازش انباشته‌ استفاده می‌شود؛ برای نمونه عملیات فر درون‌سوز در تولید بوردهای مدار چاپی، داخل فرهایی انجام می‌شود که می‌توانند چندین گروه از بوردها را در خود و زیر عملیات حرارتی قرار دهند (لی و همکاران، 1999). در اینجا فرها نقش ماشین‌های پردازش انباشته را بازی می‌کنند. مثالی دیگر، فرآیند حکاکی هدایت الکتریکی[iii] در بوردهای مدار چاپی است. طی این فرآیند و طی عملیات فوتولیتوگرافی[iv] از تانک‌هایی (ماشین‌های پردازش انباشته) استفاده می‌شود که حاوی مواد شیمیایی برای از بین بردن لایۀ فلزی روی بورد هستند که با مادۀ محافظت‌کننده پوشانده نشده است (احمدی و همکاران، 1992). همچنین می‌توان به روترهای کنترل عددی[v] استفاده‌شده در برش ورق‌های فلزی و یا مدارهای چاپی اشاره کرد. طی فرآیند برش ورق‌ها، با چرخش صفحه‌گردنده یک انباشته از قطعات فلزی هم‌خانواده تولید می‌شود. در اینجا روتر برنده با یک ماشین پردازش انباشته مدل می‌شود (احمدی و همکاران، 1992). همچنین می‌توان به کاربرد مدل‌های زمان‌بندی پردازش انباشته در سایر صنایع ازجمله صنایع ریخته‌گری (ماتیراجان و سیواکومار[vi]، 2006) ، صنایع تولید مبلمان و اثاثیۀ خانه‌ (یعقوبیان و همکاران[vii]، 1999) ، صنایع تولید آهن و فولاد (اولامارا[viii]، 2007) و غیره اشاره کرد.

اگرچه کاربردهای مدل‌های زمان‌بندی ماشین‌های پردازش انباشته در طیف وسیعی از صنایع تولیدی یافت می‌شوند، حجم عظیمی از پژوهش‌های انجام‌شده فقط به کاربرد این مدل‌ها در صنایع تولید نیمه‌هادی‌ها مربوط می‌شوند. تعداد زیادی از ماشین‌آلات استفاده‌شده در صنایع تولید نیمه‌هادی‌ها در زمرۀ ماشین‌های پردازش انباشته هستند که قابلیت انجام عملیات هم‌زمان را بر کارهای درون‌انباشته دارند. بعضی از این ماشین‌آلات عبارتند از cleaning، diffusion، oxidation وburn-in operation. عملیات انجام‌‌شده با فرهای درون‌سوز (burn-in operation) قابل مدل­سازی درقالب ماشین(های) پردازش انباشته‌ است. فقط ممکن است ظرفیت فر، بزرگ‌تر از اندازۀ یک کار باشد؛ بنابراین تعداد بوردهایی که می‌توانند داخل فر قرار بگیرند تعیین‌کنندۀ ظرفیت فر است. اندازۀ یک کار نیز با تعداد بوردهای لازم تعریف می‌شود. ازآنجاکه چیپ‌های IC برای مدتی طولانی بیش از آنچه که برای آنها در نظر گرفته شده است در داخل فر زیر عملیات حرارتی قرار می‌گیرند، قرارگیری چیپ‌های مربوط به سفارشات مختلف داخل فر امکان‌پذیر است. این در حالی است که خارج‌کردن آنها از فر پیش از مدت زمان لازم برای پخت امکان­پذیر نیست. گروهی از بوردهایی که هم‌زمان داخل فر قرار می‌گیرند یک انباشته را تشکیل می‌دهند. زمان لازم برای انجام عملیات حرارتی روی انباشته برابر زمان لازم برای انجام عملیات روی کاری است که در بین سایر کارهای درونِ انباشته زمان بیشتری را برای انجام عملیات حرارتی می‌طلبد. با شروع عملیات روی یک انباشته، هیچ کاری نمی‌تواند به انباشته اضافه و یا از آن خارج شود. همچنین ازآنجاکه دمای فر همواره ثابت است، نیاز به هیچ‌گونه آماده­سازی حرارتی نیست (لی و همکاران، 1999). اغلب در فرآیند تولید نیمه‌هادی‌ها، ایستگاه‌هایی که این ماشین‌ها در آنها فعالیت می‌کنند ایستگاه گلوگاه تولید هستند. این امر بدین خاطر است که این تجهیزات بسیار گران است؛ بنابراین میزان بهره‌گیری از آنها زیاد است. به‌علاوه عملیات تولید در این ماشین‌ها طولانی است و بدون انقطاع انجام می‌شود و این موجب انتظار طولانی سایر قطعات می‌‌شود؛ بنابراین هرگونه بهبود در زمان‌بندی و کاهش زمان سیکل نتایج مثبتی را از دیدگاه اقتصاد تولید دارد (ماتیراجان و سیواکومار[ix]، 2006). با‌توجه‌به اینکه تلاش‌های انجام‌شده در این زمینه به ارائۀ روش‌های حل محدود است و در رابطه با ارزیابی عملکرد واقعی این روش‌ها تلاش زیادی انجام نشده است، در این مقاله ضعف موجود درزمینۀ ارزیابی عملکرد الگوریتم‌های ارائه‌شده برای مسئلۀ زمان‌بندی ماشین‌های پردازش انباشته با وجود کارهای با اندازۀ غیریکسان‌ جبران می‌شود.

ساختار ادامۀ مقاله بدین شرح است که درادامۀ پژوهش حاضر، مروری بر پیشینۀ پژوهش ارائه می‌شود. سپس تعریف مسئله و مفروضات بیان و بعد از آن حدود بالا و پایین تشریح می‌شود. بخش بعدی به رویکرد حل مسئله اختصاص داده می‌شود. درپایان نیز بحث و نتایج حاصل از محاسبات تشریح و نتیجه‌گیری ارائه می‌شود.

 

مروری بر پیشینۀ پژوهش

نخستین تلاش­های انجام‌شده در زمان‌بندی ماشین‌های پردازندۀ انباشته به ایکورا و جیمپل[x] (1986) نسبت داده می‌شود. همچنین نخستین افرادی که زمان‌بندی ماشین‌های پردازش‌گر انباشته را با فرض وجود کارهای با اندازه نامساوی[xi] بررسی کردند، دابسون و نامبیادوم[xii](2001) بودند. اوزوی (1994) مسئلۀ حداقل‌کردن Cmax و SCi روی یک ماشین پردازش‌گر انباشته را بررسی و محل کاربرد آن را در صنایع تولید نیمه‌هادی معرفی کرد. وی برای مسئلۀ حداقل‌کردن Cmax نشان داده است که این مسئله با فرض یکسان‌بودن کلیۀ زمان‌های پردازش معادل مسئلۀ شناخته‌شدۀ بسته‌بندی اشیاء در ظروف و مسئله‌ای NP-hard است. سپس برمبنای الگوریتم first-fit که برای مسئلۀ بسته‌بندی اشیاء در ظروف ابداع شده است، 4 الگوریتم برای مسئلۀ حداقل‌کردن Cmax ارائه کرده است. مبنای عمل کلیۀ این الگوریتم‌ها ابتدا مرتب‌سازی کارها براساس ترتیب‌های مختلف و سپس استفاده از الگوریتم first-fit برای انباشته‌سازی کارها است. کارایی این الگوریتم‌ها ازطریق محاسبات کامپیوتری بررسی و معلوم شده است. یکی از این الگوریتم‌ها که برمبنای مرتب‌سازی کارها براساس LPT[xiii] عمل می‌کند، دارای عملکرد بهتری نسبت به سایرین است. دربارۀ مسئلۀ حداقل‌کردن SCi نیز نشان داده شده است که این مسئله NP-hard است و الگوریتم شاخه و حدی برای به دست آوردن جواب بهینه در مسائل کوچک ارائه شده است. وی همچنین 2 الگوریتم ابتکاری برای این مسئله توسعه داده است.

 

دوپونت و جولای[xiv] (1998) برای مسئلۀ حداقل‌کردن Cmax دو الگوریتم ابتکاری ارائه کرده‌اند که یکی از آنها برمبنای اصلاح الگوریتم‌های ارائه‌شده به‌وسیلۀ اوزوی(1994) در استفاده از الگوریتم best-fit به‌جای first-fit است و دیگری برمبنای تعیین اقلام یک انباشته با استفاده از حل مسئلۀ کوله‌پشتی است. نتایج محاسباتی نشان داده‌اند هر دو الگوریتم عملکرد بهتری نسبت به الگوریتم‌های قبلی دارند. آنها همچنین برای مسئلۀ حداقل‌کردن SCi تعدادی الگوریتم ابتکاری ارائه کرده‌اند و ازطریق محاسبات کامپیوتری نشان داده‌اند عملکرد این الگوریتم‌ها در مقایسه با الگوریتم‌های ارائه‌شده به‌وسیلۀ اوزوی (1994) بهتر است. ژانگ و همکاران[xv] (2001) عملکرد الگوریتم‌های ارائه‌شدۀ اوزوی (1994) را برای مسئلۀ حداقل‌کردن  در بدترین حالت تحلیل و یک الگوریتم تقریب جدید ارائه کرده‌اند. حسین‌زاده کاشان و همکاران ) 2009) فرضیات مسئلۀ معرفی‌شده در مرجع ژانگ و همکاران (2001) را تعمیم و یک الگوریتم ابتکاری با نسبت عملکرد معلوم ارائه داده‌اند. آنها همچنین یک الگوریتم تقریب برای حالتی ارائه داده‌اند که اندازه و زمان پردازش کارها موافق یکدیگر هستند.

دوپونت و فیلپو[xvi](2002) مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با کارهایی با اندازۀ غیریکسان را مطالعه کرده‌اند و برای این مسئله یک الگوریتم شاخه و حد ارائه داده‌اند. همچنین رفیعی پارسا و همکارانش[xvii](2010) برای این مسئله حد پایین مناسبی ارائه‌ و با استفاده از روش تولید ستون و روش شاخه و کران، الگوریتم شاخه و قیمت را برای رسیدن به جواب بهینه پیشنهاد کرده­اند. این الگوریتم قابلیت رقابت با روش شاخه و کرانِ دوپونت و فیلپو(2002) را دارد. مالاپرت و همکارانش[xviii] (2012) با استفاده از برنامه­ریزی محدودیت­ها همین مسئله را با تابع هدف  بررسی کرده‌اند. کاشان و کریمی (2010) نیز در مقالۀ خود این مسئله را بررسی کرده‌اند و دو روش جدید تولید حد پایین ( ) روی مقدار بهینۀ تابع هدف به‌‌نام‌های  و  ارائه داده‌اند‌. آنها ثابت کرده‌‌اند این روش نسبت به حد پایین  که به‌وسیلۀ اوزوی(1994) ارائه شده است عملکرد بهتری دارد. همچنین در این مرجع ثابت شده است عملکرد  حداقل به‌خوبی عملکرد  است. لی و ژانگ (2018) مسئلۀ حداقل‌کردن زمان انجام کارها را در یک ماشین پردازش دسته‌ای مطالعه کرده‌اند. برخلاف مسائل زمان‌بندی ماشینِ پردازشِ دسته‌ای کلاسیک که در آن ظرفیت یک ماشین به‌صورت مسئلۀ کوله‌پشتی یک‌بعدی مدل‌سازی می‌شود، در این مطالعه ظرفیت ماشین و اندازۀ کارها با مستطیل دوبعدی نشان داده شده است. یک انباشته از کارها زمانی شدنی است که کارها بتوانند بدون هم‌پوشانی با یکدیگر در ماشین قرار بگیرند. کارها دارای اندازۀ متفاوت هستند و با طول، عرض و زمان پردازش نشان داده می‌شوند. هدف، تعیین تعداد انباشته‌ها برای تخصیص کارها به انباشته‌ها به‌نحوی‌ است که زمان انجام کل کارها حداقل شود. مسئلۀ مطالعه‌شده در این مقاله، ترکیبی از مسئلۀ بسته‌بندی اقلام در ظروف به‌صورت دوبعدی (2D-BPP) و مسئلۀ زمان‌بندی ماشین پردازندۀ انباشته (BPM) است. آنها برای حل این مسئله مدل برنامه‌ریزی عدد صحیح مختلط و چند روش ابتکاری ارائه داده‌اند. مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با دو تابع هدف هم‌زمان "حداقل‌کردن زمان تکمیل تمام کارها" و "حداقل‌کردن هزینۀ انرژی کل" به‌وسیلۀ وانگ و همکاران[xx] (2016) بررسی و این مسئله به‌صورت یک مسئلۀ برنامه‌ریزی عدد صحیح مدل شده است. سپس روش دقیق  محدودیت[xxi] برای به دست آوردن نقاط پارتوی دقیق و دو روش ابتکاری برمبنای ایدۀ تجزیه برای به دست آوردن نقاط پارتوی تقریبی در مسائل با اندازه‌های بزرگ توسعه یافته است.

حل مسائل زمان‌بندی ماشین‌های پردازندۀ انباشته با فرض وجود کارهای با اندازۀ نامساوی با استفاده از الگوریتم‌های فراابتکاری توجه پژوهشگران زیادی را به‌خود جلب کرده است. ملوکو همکارانش[xxii](2004) برای مسئلۀ حداقل‌کردن  روی یک ماشین پردازندۀ انباشته با فرض اینکه که زمان پردازش و اندازۀ کارهای مختلف متفاوت است، الگوریتم شبیه­سازی تبرید را استفاده کرده‌اند. نونگ و همکارانش)[xxiii]2012) همین مسئله را در دو حالتِ مختلف برای اندازۀ کارها بررسی کرده­اند. در حالت نخست اندازۀ کارها یکسان در نظر گرفته و یک الگوریتم تقریب با پیچیدگی زمانی چندجمله­ای ارائه شده است. در حالت دوم نیز اندازۀ کارها متفاوت فرض و یک الگوریتم تقریب پیشنهاد شده است. حسین‌زاده کاشان و همکاران[xxiv] (2006) نیز این مسئله را بررسی کرده‌اند و برای آن یک الگوریتم ژنتیک برمبنای نمایش کروموزومی براساس کلیدهای تصادفی و یک الگوریتم ژنتیک ترکیبی براساس نمایش کروموزومی ابداعی پیشنهاد کرده­‌اند. نتایج مقایسات آنها نشان می­دهد الگوریتم ژنتیک ترکیبی عملکرد بهتری را نسبت به شبیه­سازی تبریدِ ارائه‌شده به‌وسیلۀ ملوکو همکارانش(2004) دارد. چانگ و سون (2018) مسئلۀ یک ماشین پردازندۀ انباشته با فرض وجود کارها با زمان آزادسازی و اندازه‌های متفاوت را برای حداقل‌کردن زمان انجام کل کارها در نظر گرفته‌اند و یک الگوریتم سیستم ایمنی مصنوعی مبتنی‌بر ایمونوگلوبولین (IAIS) برای حل این مسئله ارائه داده‌اند. الگوریتم مدنظر دو مشخصۀ اصلی دارد؛ نخست اینکه فضای جستجو به فرایند نوسازی جسمی محدود شده است تا زمان محاسبات کاهش یابد و دیگر اینکه ترکیبی از چندین روش جستجوی محلی استفاده شده است تا در هر بار اجرا همسایگی تغییر کند و از بهینگی محلی جلوگیری شود. نتایج محاسبات آنها نشان داده است روش ارائه‌شده عملکرد خوبی دارد.

مسئلۀ حداقل‌کردن هم‌زمان  و  به‌وسیلۀ کاشان و همکاران[xxv] (2010) مطالعه شده است. برای این مسئله مؤلفین یک الگوریتم ژنتیک دوهدفه ترکیبی ارائه کرده‌اند. نتایج محاسبات آنها نشان می‌دهد این الگوریتم قابلیت یافتن جواب‌های نزدیک به جواب‌های بهینۀ پارتو را دارد. کاشان و کریمی (2008) نیز چارچوبی برمبنای بهینه‌سازی کلونی مورچگان در دو نسخۀ متفاوت ارائه داده‌اند. زو و همکاران[xxvi] (2012) مسئلۀ حداقل‌کردن  را با فرض وجود زمان‌های ورود پویا برای کارها با اندازۀ غیریکسان روی یک ماشین پردازندۀ انباشته در نظر گرفته‌اند و یک مدل برنامه‌ریزی عدد صحیح مختلط و یک حد پایین معتبر برای این مسئله پیشنهاد داده‌اند. چون این مسئله است، آ‌نها برای حل یک الگوریتم ابتکاری و یک الگوریتم بهینه­سازی کلونی مورچگان برمبنای فرض‌های ارائه‌شده پیشنهاد دادند. نتایج کار نشان می­دهد الگوریتم کلونی مورچگان پیشنهادشده به‌وسیلۀ آنها جواب­های بهتری را در زمان قابل قبولی در مقایسه با دو روش ابتکاری ژنتیک و سیمپلکس تولید می‌کند؛ مخصوصاً زمانی­که اندازۀ کار­ها بزرگ است. لی و همکاران[xxvii] (2013) الگوریتمی برای مسئله­ای با یک ماشین پردازش انباشته­ با کارهایی ارائه کرده‌اند که دارای موعد تحویلِ مشخص، هستند. در این مسئله، محدودیت­های فازی برای برقراری روابط پیش­نیازی و پس­نیازی اعمال شده ­است. تابع هدف نیز به‌صورت حداقل‌کردن زمان تکمیل تمام کارها تعریف شده ­است. چاندرو و همکاران[xxviii] (1993) در مقالۀ خود یک روش شاخه و حد برای حداقل‌کردن زمان انجام کل کارها روی یک ماشین ارائه کردند. آنها همچنین برای مسئلۀ ماشین‌های موازی چند روش ابتکاری معرفی کردند. لی و همکارانش[xxix] (2013) چند روش ابتکاری برای مسئلۀ حداقل‌کردن  روی تعدادی ماشین متفاوت به‌صورت موازی در‌حالت متفاوت‌بودن اندازۀ کارها ارائه کرده­اند.

کوه و همکارانش[xxx] (2005) برای مسئلۀ پردازش دسته­ای با خانواده­های ناسازگار کارها و اندازۀ متفاوت کارها و سه تابع هدفِ "حداقل‌کردن زمان تکمیل تمام کارها"، "حداقل‌کردن مجموع زمان تکمیل کارها" و "حداقل‌کردن مجموع وزنی زمان تکمیل کارها" مدلی ریاضی ارائه کرده­اند. همچنین برای حل مسائل با اندازۀ واقعی تعدادی روش ابتکاری و یک الگوریتم ژنتیک ترکیبی پیشنهاد کرده­اند. لی [xxxi](2012) نیز مسئلۀ حداقل‌کردن  را روی چند ماشین موازی درحالت متفاوت‌بودن اندازۀ کارها در نظر گرفته و برای آن یک الگوریتم تقریب ارائه کرده ­است. در مقالۀ جیا و همکاران[xxxii] (2017) مسئلۀ زمان‌بندی کارهای با اندازۀ غیریکسان و زمان رسیدن پویا روی مجموعه‌ای از ماشین‌های موازی با ظرفیت متفاوت با هدف حداقل‌کردن  در نظر گرفته شده است. در این مقاله ابتدا مدلی ریاضی برای مسئله ارائه و حد پایینی برای آن معرفی شده است، سپس دو روش فراابتکاری برمبنای الگوریتم کلونی مورچگان برای حل مسئله ارائه شده است. داموداران و همکاران[xxxiii] (2012) نیز این مسئله را مطالعه کرده‌اند و یک الگوریتم بهینه‌سازی ازدحام ذرات (PSO) را برای حل آن ارائه داده‌اند. در مقالۀ جیا و همکاران[xxxiv] (2015) نیز همین مسئله، مطالعه و برای حل آن یک روش ابتکاری برمبنای الگوریتم First-Fit-Decreasing (FFD) و یک روش ابتکاری برمبنای الگوریتم Max-Min Ant System (MMAS) ارائه شده است. نتایج این مقاله نشان می‌دهد این دو روش‌ عملکرد بهتری را نسبت به روش ابتکاری معرفی‌شده به‌وسیلۀ داموداران و همکاران (2012) برای این مسئله دارند. از طرف دیگر MMAS عملکرد بهتری در مقایسه با FFD دارد. ژو و همکاران(2018) مسئلۀ حداقل‌کردن  را روی ماشین‌های موازی نامرتبط با فرض وجود کارهای با اندازۀ غیریکسان و زمان‌های آزادسازی دلخواه بررسی کرده‌اند و برای حل این مسئله دو حد پایین و یک الگوریتم ژنتیک برمبنای کدگزاری کلید تصافی ارائه داده‌اند. عملکرد الگوریتم پیشنهادی با یک حل‌کنندۀ تجاری (ILOG CPLEX)و دو روش فراابتکاری موجود در ادبیات (الگوریتم حریصانه و الگوریتم بهینه‌سازی ازدحام ذرات) مقایسه شده و آزمایش‌ها محاسباتی نشان داده است الگوریتم پیشنهادی در مقایسه با روش‌های دیگر راه‌حل‌های بهتری را تولید می‌کند. آنها همچنین کیفیت حدود پایین پیشنهادی را ارزیابی کرده‌اند و نشان داده‌اند که از حدود پایین موجود، عملکرد بهتری دارد. ارویو و همکاران[xxxv] (2017) مسئلۀ زمان‌بندی مجموعه‌ای از کارهای با اندازۀ متفاوت و زمان آماده‌سازی غیر‌صفر را روی مجموعه‌ای از ماشین‌های موازی غیرمرتبط برای حداقل‌کردن  در نظر گرفته‌اند و برمبنای الگوریتم‌های FF[xxxvi] و BF[xxxvii]، چند روش ابتکاری برای مسئله توسعه داده‌اند. در این مرجع یک مدل برنامه‌ریزی عدد صحیح مختلط و یک حد پایین برای ارزیابی کیفیت ابتکاری‌ها ارائه شده است.

با‌توجه‌به اینکه روش‌­های استفاده‌شده در مقالات موجود در ادبیات برای حل این مسئله، بیشتر روش‌ها برمبنای روش­های تقریبی است و به روش­های حل بهینه کمتر توجه شده است. هم‌چنین باتوجه‌به اهمیت این مسائل در حوزۀ صنعت وصرفه­جویی هزینه­ای که درنتیجۀ بهینه­سازی زمان‌بندی عملیات تولید دست‌یافتنی است، نتیجه می‌شود توسعۀ روش­های حل دقیق مانند روش شاخه و حد برای این­گونه مسائل اهمیت زیادی دارد؛ ازاین‌رو هدف این پژوهش ارائۀ روش‌ شاخه و حد کارا با استفاده از حدود پایین و حدود بالا روی مقدار بهینۀ تابع هدف در مسئلۀ زمان‌بندی ماشین‌های پردازش انباشته با وجود کارهای با اندازۀ غیریکسان‌ است.

 

تعریف مسئله و مفروضات

مسئله‌ای که در این پژوهش درحال بررسی است، مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهای با اندازۀ غیریکسان است. مفروضات مسئله به‌شرح زیر است:

1- تعداد n کار برای زمان‌بندی روی یک ماشین پردازش انباشته وجود دارد که همگی در لحظۀ صفر در سیستم در دسترس هستند. کلیۀ کارها با یکدیگر سازگار وتنها متعلق به یک خانواده هستند (زمان‌بندی بدون خانواده‌های کارها).

2- با شروع عملیات ماشین روی یک انباشته، توقف عملیات امکان‌پذیر نیست و پیش از اتمام عملیات ماشین، هیچ‌کاری نمی‌تواند به انباشته اضافه و یا از آن خارج شود.

3- مقادیر زمان‌های پردازش و اندازۀ کارها از قبل مشخص و قطعی هستند.

4- زمان شروع و زمان ختم عملیات تمامی کارهایی که متعلق به یک انباشته هستند با یکدیگر یکسان است. زمان پردازش انباشته نیز برابر زمان پردازش کاری است که بین سایر کارهای متعلق به انباشته زمان پردازش لازم برای آن طولانی‌تر است.

5- حداکثر ظرفیت ماشین برای انجام عملیات هم‌زمان روی کارها برابر Bاست؛ به عبارت دیگر مجموع ابعاد کارهای متعلق به یک انباشته نباید از مقدار B متجاوز شود. همچنین فرض می‌شود کلیۀ کارها دارای اندازه‌ای کوچک‌تر یا مساوی با ظرفیت ماشین است.

6- خرابی ماشین(ها) مجاز نیست.

ماشین‌های پردازش انباشته در مقایسه با سایر عملیات تولید و تست دارای زمان انجام عملیات طولانی‌تری هستند و ایستگاه گلوگاه تولید به‌شمار می‌روند؛ بنابراین میزان بهره‌برداری زیاد از ماشین(ها) در این عملیات باعث افزایش توان عملیاتی کل سیستم می‌شود. ازآنجا‌که میزان بهره‌برداری بیشتر به‌معنی کاهش زمان انجام عملیات کلیۀ کارها (یا به‌طور معادل مقدار Cmax) با ماشین‌ها است، معیار عملکرد، حداقل‌کردن Cmax است.

 

اندیس‌ها و نمادها

j : نشانگر کار jام، j=1,2,…,n (n تعداد کل کارها برای زمان‌بندی).

: زمان پردازش کار jام.

: زمان پردازش کار jام.

B: حداکثر ظرفیت ماشین.

 

مجموعه‌ها.

S: مجموعۀ اندازۀ کارها.

P: مجموعۀ زمان پردازش کارها.

: مجموعه کارهایی که اندازۀ آنها بزرگ‌تر از uو کوچک‌تر یا مساوی با v است.

: مجموعه کارهایی که اندازۀ آنها بزرگ‌تر یا مساوی با uو کوچک‌تر یا مساوی با v است.

حدود بالا و پایین

در این بخش روش‌های تولید حد پایین و بالای موجود برای مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهایی با اندازۀ غیریکسان بررسی می‌شود و در بخش بعد در بدنۀ روش شاخه و حد به ‌کار گرفته می‌شود.

 

حدود بالا

در این پژوهش از دو الگوریتم FFLPT[xxxviii] (اوزوی، 1994) وBFLPT[xxxix] (دوپونت و جولای، 1998) برای تولید حدود بالا استفاده شده است و کمترین مقدار از بین این دو در مراحل حل مسئله برای حد بالا لحاظ شده است.

 

حدود پایین

ازجمله مهم‌ترین کاربردهای حدود پایین، استفاده از آنها در بدنۀ الگوریتم‌های دقیق مانند روش شاخه و حد است. در این مقاله تلاش شده است از حدود پایین ، (اوزوی، 1994)، و ، (کاشان و کریمی، 2012) برای تولید حد پایین در الگوریتم شاخه و کران استفاده و نتایج مقایسه شود. درادامه الگوریتم‌های مذکور تشریح می‌شود.

 

الگوریتم

روش کار در این الگوریتم به‌صورت زیر خلاصه شده است:

گام1. ابتدا کلیۀ کارها را به‌ترتیب نزولیِ زمان پردازش­شان مرتب کنید.

گام2. با شروع از ابتدای لیست، نخستین کار را در تنها انباشته­ای قرار دهید که به­طور کامل پر نشده است (ظرفیت استفاده‌نشدۀ آن از B یعنی ظرفیت انباشته کمتر است). اگر همۀ انباشته­ها به حد بالای ظرفیت خود رسیده باشند یک انباشتۀ جدید تشکیل دهید و اگر فضای لازم برای قراردادن کار در انباشتۀ مذکور وجود ندارد، قسمتی از کار را که ظرفیت خالی انباشته را به‌طور کامل اشغال می­سازد درون انباشته قرار دهید. سپس یک انباشتۀ جدید تشکیل و باقیماندۀ کار خرد‌شده را در آن قرار دهید.

گام3. این فرآیند را تا زمانی تکرار کنید که هیچ‌کاری در لیست باقی نمانده باشد. بدین ترتیب تعداد انباشته­های حاصل برابر  است.

مبنای الگوریتم اشاره‌شده در بالا براساس آزادسازی است. بدین ترتیب که در آن فرض مجازنبودن شکست کارها به اجزا، آزاد شده است. هنگامی‌که اندازۀ کارها نسبت به ظرفیت ماشین کوچک است، عملکرد متوسط  خوب تلقی می‌شود؛ درواقع ثابت شده است هرچقدر اندازۀ کارها نسبت به ظرفیت ماشین کوچک‌تر شود عملکرد  در بدترین حالت بهتر می‌شود. براساس تجربه نیز ثابت شده است برای بسیاری از مسائلی که در آنها اندازۀ کارها نسبت به ظرفیت ماشین کوچک است، مقدار حد پایین تولیدشده به‌وسیلۀ  با مقدار  برابر است؛ اما عملکرد  زمانی تقلیل می‌یابد که اندازۀ کارها به نسبت بزرگ باشد. کاشان و کریمی )2012) از این نقطه ضعف برای تولید حدود پایین جدید استفاده و حد پایین  و  را معرفی کرده‌اند.

الگوریتم

برای دست­یابی به یک حد پایین روی مقدار  به‌ازاءِ مقادیر مختلف ε (ε ≤ B/2) تنها اجازه داده می‌شود کارهایی شکست‌پذیر باشد که اندازۀ آنها در دامنۀ [ε, B- ε] باشد. فرض کنید  دلالت بر مجموعه کارهایی داشته باشد که اندازۀ آنها بزرگ‌تر از uو کوچک‌تر یا مساوی با v است. به‌طور مشابه تعریف می‌شود . روش زیر با عنوان NLB یک حد پایین معتبر را روی مقدار  به دست می­دهد.

گام1. به‌ازاءِ ، یک حد پایین را روی مقدار  به‌صورت زیر محاسبه کنید.

رابطۀ 1

 

که در آن  مقدار حد پایین به‌دست‌آمده به‌وسیلۀ  براساس مجموعه کارهایی است که اندیس آنها متعلق به مجموعۀ  است.

گام2. با تکرار گام 1 به‌ازاءِ تمامی مقادیرε، بزرگ‌ترین مقدار به‌دست‌آمده برای  یک حد پایین روی مقدار  است؛ یعنی:

رابطۀ 2

 

این الگوریتم یک حد پایین معتبر روی مقدار  به دست می­دهد. همچنین ثابت شده است مقدار حد پایینِ حاصل از الگوریتم  بیشتر از حد پایین تولید‌شده به‌وسیلۀ الگوریتم  است؛ اما درادامه حد  معرفی می‌شود که عملکرد آن از هر دو الگوریتم  و  بهتر است؛ بنابراین پس از معرفی این حد از آن برای حد پایین در روش شاخه و کران استفاده می­شود.

 

الگوریتم  

 ازآنجا‌که دو کاری که اندازۀ آنها در بازۀ  قرار می‌گیرد نباید در یک انباشته باشند، هنگامی‌که ، ممکن است مقدار حد  قوی‌تر شود؛ ازاین‌رو حد  به‌صورت زیر تعریف می­شود.

رابطۀ 3

 

که در آن

 

الگوریتم  

با استفاده از ایدۀ تفکیک کارها درقالب سه مجموعه، حد پایین LB3 به‌صورت زیر ارائه شده است.

رابطۀ 4

 

که در آن،  مقدار بهینۀ Cmaxدر زیرمسئله‌ای از مسئلۀ اصلی است که فقط کارهای با اندازۀ بزرگ‌تر از  در نظر گرفته شده‌ است.

طبق تعریف، مجموعه کارهایی که اندیس آنها در مجموعۀ S(B/3,B)قرار دارد درقالب سه زیرمجموعه تفکیک می‌شود؛ نخستین زیرمجموعه به‌صورت ، دومین زیرمجموعه به‌صورت  و سومین زیرمجموعه به‌صورت  است. همچنین مجموعۀ x به‌این‌صورت تعریف می‌شود؛  که در آن  مجموعه‌ای از زیرمجموعۀ دوم است و می­تواند با یکی از کارهای مجموعۀ سوم گروه­بندی شوند. بدین ترتیب باتوجه‌به ترکیب‌بندی کارها به‌صورت بالا می‌توان  را به‌صورت رابطۀ زیر ارائه کرد.

رابطۀ 5

 

بنابراین با محاسبۀ مقدار  می‌توان به مقدار  رسید. درنهایت  به‌صورت رابطۀ زیر نمایش داده می‌شود.

رابطۀ 6

 

 

که مقدار  ازطریق تبدیل مسئلۀ زمان‌بندی مربوطه به یکی از مسائل شناخته‌شده در نظریۀ گراف (مسئلۀ حداکثر تطابق وزنی) به دست می‌آید. لازم به ذکر است در محاسبۀ الگوریتم  باید یک مسئلۀ حداکثر تطابق وزنی حل شود که در پژوهش‌ قبل از جعبۀ بهینه‌سازی موجود در نرم‌افزار متلب استفاده شده است و مبتنی‌بر روش شاخه و حد عمل می­کند؛ اما در این پژوهش از الگوریتم ادموند (گابو[xl] ،1976) برای حل این مسئله استفاده شده است. این الگوریتم قادر است در زمان چندجمله­ای مسئلۀ مدنظر را حل کند؛ بنابراین در زمان حل الگوریتم بهبود حاصل شده است.

 

روش شاخه و حد

در این بخش برای محاسبۀ حداقل  در مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با اندازۀ کارهای غیریکسان، الگوریتم شاخه و کرانی به کار گرفته شده است که برمبنای روش دوپونت و فیلیپو (2002) است. برای شاخه‌زدن در الگوریتم شاخه و کران، در هر مرحله باید دو تصمیم گرفته شود؛ نخست کار انتخابی باید به انباشتۀ جاری اضافه شود یا در انباشتۀ جدید قرار بگیرد و دوم اینکه مشخص شود کدام کار باید به انباشته اضافه شود. همچنین دو روش برای اضافه‌کردن یک کار جدید به جواب جزئی (p) وجود دارد که عبارتند از:

1- نوع یک: در این نوع، کار جدید در یک انباشتۀ جدید قرار می‌گیرد.

2- نوع دو: در این نوع، کار جدید به انباشتۀ موجود در P اضافه می‌شود، به‌طوری‌که انباشته ظرفیت پذیرش کار جدید را داشته باشد.

در سطح نخست از درخت شاخه و کران، در هر جواب جزئی P، دقیقاً یک کار در یک انباشته قرار می‌گیرد. زمانی‌که یک گره برای شاخه‌زدن انتخاب می‌شود، فهرستی از کارهای موجود که هنوز زمان‌بندی نشده‌اند برای اضافه‌شدن به P در نظر گرفته می‌شود. یک مثال از نحوۀ شاخه‌زدن یک مسئله با تعداد 3n= کار با اندازۀ یک و 3B= در شکل 1 آورده شده است. سطح نخست از درخت تنها شامل گره‌های نوع یک است که درواقع هر کار در انباشتۀ مربوط به خود قرار می‌گیرد. در سطح بعدی درخت، گره‌های نوع یک و نوع دو تولید هستند. کارهایی که با هم در یک پرانتز قرار دارند نشان‌دهندۀ کارهایی است که در یک انباشته با هم پردازش می‌شوند. باتوجه‌به اینکه ترتیب قرارگرفتن کارها در انباشته‌ها اهمیتی ندارد و کارهای موجود در یک انباشته به‌صورت هم‌زمان پردازش می‌شوند و زمان شروع و پایان یکسانی دارند، تعداد زیادی از جواب های جزئی ایجاد‌شده تکراری هستند؛ برای مثال دو جواب جزئی ((23)(1)) و ((32)(1)) یکی هستند. برای افزایش کارایی الگوریتم از سه نکتۀ اشاره‌شده درادامه استفاده شود تا از این تکرارها در الگوریتم شاخه و کران اجتناب کرد (دوپونت و فیلیپو، 2002):

الف) ابتدا کارها را براساس زمان پردازششان از بیشتر به کمتر(به‌صورت نزولی) مرتب کنید.

ب) برای شاخه‌زدن، درصورتی‌که گره فرزند از نوع دوم باشد باید زمان پردازش کار جدیدی که قرار است به انباشته اضافه شود از زمان پردازش مابقی کارهایِ موجود در انباشته کمتر یا مساوی باشد.

ج) در نظر نگرفتن جواب‌های جزئی‌ که انباشته‌هایی با کارهای یکسان دارند؛ برای مثال دو جواب جزئی ((1) (32)) و ((32)(1)) یکی هستند و می‌توان یکی از آنها را در نظر نگرفت.

 

 

شکل 1- نحوۀ شاخه‌زدن در درخت شاخه و کران

 

در روش شاخه و کران برای رسیدن به جواب بهینه به حدود بالا و پایین احتیاج است. هرچه مقدار این حدود بالا و پایین به یکدیگر نزدیک­تر باشد، این روش سریع‌تر به جواب می­رسد و تعداد گره­های کمتری بررسی می­شود. در اینجا برای محاسبۀ مقدار اولیه از هر دو روش ابتکاری FFLPT و BFLPT استفاده شده است و کمترین مقدار از بین آنها برای یک حد بالا در مسئله استفاده می­شود. برای توصیف این الگوریتم، اگر مجموعه کارهای زمان‌بندی‌نشده مجموعۀ j نامیده شود، برای به ­دست آوردن یک حد پایین روی مجموعۀ j می­توان از الگوریتم تولید حدود پایین ذکر‌شده در بخش قبل استفاده کرد. مقدار حد پایین روی مجموعۀ j، BInf(j) نامیده می‌شود (اگر j مجموعۀ کل کارها باشد، این حد پایین با Cmin نشان داده می­شود). فرض کنید Valbest مقدار بهترین جواب شناخته‌شده و Valsol جواب جزئی مسئلۀ زمان‌بندی روی انباشتۀ نخست تا انباشتۀ فعلی باشد، دراین‌صورت اگر ، می­توان این گره را قطع کرد؛ چون جواب بهتری تولید نمی‌کند؛ درغیراین‌صورت با استفاده از یک الگوریتم حریصانه جوابی شدنی روی مجموعۀ j تولید کنید و آن را valgreedy نام‌گذاری کنید (در اینجا از FFlPT استفاده شده است). درصورتی‌که  باشد، درواقع یک بهترین جواب جدید به دست آمده است. همچنین اگر  جواب بهینه روی j به ­دست آمده باشد، می‌توان عملیات را در این گره به پایان رساند. در حالت کلی در دو حالت الگوریتم به پایان می­رسد؛ نخست اینکه جواب بهینه برای مسئله پیدا شود و یا زمان در نظر گرفته شده برای حل مسئله به پایان برسد. در روش حاضر برای تولید حد پایین از الگوریتم‌های  و  و  استفاده و نتایج آنها با هم مقایسه شده است. تجربه ثابت کرده است این الگوریتم‌ها بسیار سریع هستند و جواب‌های نزدیک به بهینه را تولید می‌کنند. درادامه برای بررسی کیفیت جواب‌های حاصل‌شده، درصورت استفاده از حدود پایین  و  و  و انجام مقایسات، یک برنامۀ کامپیوتری در نرم‌افزار متلب نوشته و آزمایش‌ها روی یک رایانه با RAM 4 Gb و CPU 40/2 GHz انجام شده است.

 

بحث و نتایج محاسباتی

برای ارزیابی عملکرد حدود پایین ارائه‌شده و به دست آوردن جواب بهینه برای مسئلۀ مد‌نظر، دسته‌ای از نمونه مسائل به‌صورت تصادفی در نرم‌افزار متلب تولید شده است‌ و روش‌های ارائه‌شده در بخش قبل روی این داده‌ها آزمایش شده‌اند. ابتدا داده‌های استفاده‌شده بررسی و سپس نتایج محاسبات درقالب جداول و شکل‌ها در بخش بعد ارائه می‌شوند.

برای انجام آزمایش‌های محاسباتی، 6 مجموعه مسئله در نظر گرفته شده است. برای هر نمونه مسئله دو سطح از زمان پردازش و 5 سطح از اندازۀ کارها بررسی می‌شود. همچنین برای هر مجموعه، 10 نمونه مسئله به‌صورت تصادفی تولید شده است؛ درنتیجه تعداد مسائلی که در هر بخش آزمایش می‌شود برابر 600 است. این مسائل در جدول 1 به‌تفصیل آورده شده است.

 

جدول 1- دسته‌بندی مسائل

شمارۀ مسئله

اندازۀ کارها

ظرفیت ماشین

اندازۀ کارها

1

]10-1[

10

100و80و60و40و20=n

2

]8-4[

10

100و80و60و40و20=n

3

]5-1 [

10

100و80و60و40و20=n

4

]4-2[

10

100و80و60و40و20=n

5

]5-1 [

5

100و80و60و40و20=n

6

]4-2[

5

100و80و60و40و20=n

 

برای انجام آزمایش‌های محاسباتی، مجموعه مسائل مطرح‌شده در جدول 1) در نظر گرفته و مقادیر جواب بهینه برای آنها حساب شده‌ است. درادامه نتایج محاسبات درقالب جدول 2 تا 5 آورده می‌شوند.

جدول 2- شاخه و کران ,pj [1,10] B=10

B&B (LB3)

B&B( )

B&B(LB1)

 

Lb3

Gap (%)

Avg .times

Avg .node

#Opt

Lb2

Gap (%)

Avg .times

Avg. nodes

#Opt

Ub

Lb1

Gap (%)

Avg .times

Avg. nodes

#Opt

   

66

0

13/0

44

10

90/65

0

07/0

44

10

50/67

50/62

0

21/0

173

10

20

]10-1[

70/134

0

59/10

1304

10

10/134

0

10/5

185

10

81/138

40/130

0

09/67

28572

10

40

90/182

0

22/121

12999

10

00/182

0

48/63

21657

10

00/191

90/179

0

80/1103

490190

5

60

90/259

05/1

20/736

69984

7

80/259

08/1

82/471

116600

8

50/265

00/248

63/6

30/1793

518580

0

80

70/334

72/0

60/876

34505

7

70/333

97/0

61/657

117600

8

00/9

70/322

48/5

10/1795

452462

0

100

86

0

04/0

3

10

10/85

0

02/0

5

10

62/86

40/72

0

06/0

46

10

20

]8-4[

20/166

0

75/0

20

10

70/164

0

29/0

85

10

30/168

80/139

0

43/1

657

10

40

30/243

0

94/3

23

10

10/241

0

77/0

97

10

71/246

20/202

0

42/100

33002

10

60

3/318

0

18/7

35

10

90/314

0

30/15

2252

10

00/321

60/269

01/18

60/356

91892

9

80

50/415

0

12/20

50

10

80/411

0

16/153

22651

10

22/419

40/346

92/19

14/680

190190

8

100

60/36

0

17/0

29

10

60/36

0

07/0

29

10

10/37

60/36

0

05/0

29

10

20

]5-1[

60/69

0

47/3

141

10

60/69

0

43/0

141

10

51/70

60/69

0

33/0

141

10

40

107

0

88/13

271

10

00/107

0

71/1

271

10

43/108

00/107

0

23/1

271

10

60

70/135

0

22/137

1620

10

70/135

0

85/9

1620

10

90/136

70/135

0

67/6

1620

10

80

60/167

0

69/66

534

10

60/167

0

69/5

534

10

45/168

60/167

0

85/3

534

10

100

10/36

0

15/0

27

10

10/36

0

09/0

31/27

10

92/36

10/36

0

07/0

27

10

20

]4-2[

90/70

0

77/8

1565

10

90/70

0

55/4

1568

10

81/73

90/70

0

55/3

1568

10

40

50/103

0

69/148

4633

10

50/103

0

97/23

4633

10

20/107

50/103

0

68/19

4633

10

60

30/136

03/2

18/624

89332

7

30/136

50/0

17/579

159890

7

91/139

30/136

50/0

94/568

208160

7

80

10/176

62/0

40/915

23291

6

10/176

50/0

64/754

86215

7

90/174

10/176

45/0

50/688

109200

7

100

 

جدول 3- روش شاخه و کران ,pj [1,10] B=5

B&B (LB3)

B&B( )

B&B(LB1)

 

Lb3

Gap (%)

Avg .times

Avg.node

#Opt

Lb2

Gap (%)

Avg .times

Avg .nodes

#Opt

Ub

Lb1

Gap (%)

Avg .times

Avg. nodes

#Opt

   

80/68

0

09/0

22

10

40/68

0

06/0

24

10

20/70

00/67

0

09/0

45

10

20

]5 -1[

60/146

0

55/0

37

10

90/142

0

21/0

47

10

20/145

40/135

0

61/0

213

10

40

205

0

54/10

406

10

90/203

0

43/3

588

10

10/211

60/201

0

72/68

22374

10

60

60/263

0

29/109

4112

10

10/262

0

34/64

9917

10

00/269

00/260

09/1

40/394

106670

9

80

60/327

04/1

48/466

6528

9

40/325

04/1

29/330

48965

9

00/334

80/321

69/2

1044

244840

5

100

20/82

0

12/0

3

10

30/80

0

02/0

6

10

20/82

20/71

0

07/0

27

10

20

]4-2 [

90/159

0

79/0

9

10

00/158

0

17/0

31

10

10/163

10/139

0

64/0

224

10

40

80/222

0

80/5

38

10

10/219

0

75/2

765

10

10/226

70/196

0

23/8

2974

10

60

80/308

0

43/15

47

10

10/304

0

52/9

1405

10

30/314

10/270

0

91/45

13579

10

80

30/394

0

69/24

50

10

80/390

0

84/15

3341

10

80/398

00/344

0

66/67

23998

10

100

                                         

 

جدول 4- روش شاخه و کران B=5, pj [1,5]

B&B (LB3)

B&B( )

B&B(LB1)

 

Lb3

Gap (%)

Avg .times

Avg. node

#Opt

Lb2

Gap (%)

Avg. times

Avg. nodes

#Opt

Ub

Lb1

Gap (%)

Avg .times

Avg. nodes

#Opt

   

90/40

0

09/0

15

10

90/40

0

04/0

15

10

90/41

70/38

0

11/0

49

10

20

]5-1[

90/71

0

54/0

33

10

60/71

0

26/0

48

10

30/73

60/70

0

74/0

239

10

40

10/115

0

62/4

143

10

80/114

0

41/1

214

10

10/118

40/110

0

60/99

24501

10

60

20/152

0

23/24

458

10

40/151

0

74/14

1867

10

10/154

40/145

20/5

14/539

133070

8

80

60/188

0

65/19

237

10

40/178

0

72/11

1590

10

00/192

30/181

46/4

70/984

230080

7

100

90/42

0

07/0

2

10

30/42

0

02/0

5

10

20/43

50/37

0

07/0

27

10

20

]4-2[

20/88

0

32/0

4

10

70/87

0

15/0

33

10

90/88

20/77

0

66/0

234

10

40

20/121

0

04/3

21

10

90/119

0

95/0

160

10

40/122

80/105

0

38/3

1135

10

60

00/167

0

59/3

14

10

50/165

0

60/0

818

10

20/168

50/146

0

36/36

17718

10

80

80/206

0

53/28

87

10

10/204

0

20/67

5775

10

40/210

50/180

40/14

17/493

103470

8

100

جدول 5- روش شاخه و کران pj [1,5],B=10

B&B (LB3)

B&B( )

B&B(LB1)

 

Lb3

Gap (%)

Avg. times

Avg. node

#Opt

Lb2

Gap (%)

Avg. times

Avg. nodes

#Opt

Ub

Lb1

Gap (%)

Avg .times

Avg. nodes

#Opt

   

20/41

0

06/0

14

10

20/41

0

04/0

15

10

20/42

20/39

0

28/0

198

10

20

]10-1[

90/69

0

23/1

137

10

70/69

0

50/0

139

10

70/71

60/67

0

10/5

1961

10

40

50/102

20/1

08/354

44285

9

20/102

40/1

80/302

92314

9

50/105

80/98

20/5

50/1552

516730

2

60

20/141

71/1

60/615

40046

8

70/140

0

60/469

84071

10

30/146

60/137

34/5

80/1776

510399

0

80

10/173

73/0

90/530

21209

8

50/172

06/1

80/475

73316

9

10/178

20/166

15/6

90/1799

510660

0

100

70/43

0

18/0

10

10

50/43

0

06/0

20

10

70/44

00/36

0

17/0

88

10

20

]8-4[

40/87

0

79/0

17

10

70/86

0

36/0

79

10

40/88

40/73

0

49/7

3864

10

40

60/135

0

55/1

16

10

30/135

0

14/0

20

10

136

10/113

0

05/3

1120

10

60

40/170

0

57/6

26

10

20/169

0

13/90

11983

10

50/171

50/145

16/17

12/403

153160

8

80

60/217

0

69/25

77

10

00/216

0

14/27

3281

10

50/220

60/183

57/18

04/765

200280

6

100

90/20

0

15/0

12

10

90/20

0

04/0

12

10

00/21

90/20

0

02/0

12

10

20

]5-1[

50/40

0

69/3

142

10

50/40

0

54/0

145

10

10/41

50/40

0

39/0

145

10

40

40/56

0

48/9

227

10

40/56

0

56/1

227

10

00/57

40/56

0

12/1

227

10

60

10/72

0

80/28

281

10

10/72

0

63/2

281

10

70/72

10/72

0

78/1

281

10

80

10/89

0

65/12

50

10

10/89

0

95/0

50

10

30/89

10/89

0

60/0

50

10

100

70/19

0

03/0

6

10

70/19

0

01/0

6

10

90/19

70/19

0

00/0

6

10

20

]4-2[

10/37

0

12/1

83

10

10/37

0

48/0

83

10

20/38

10/37

0

37/0

83

10

40

70/55

0

70/167

44993

10

70/55

0

40/155

67416

10

60/57

70/55

0

88/113

67416

10

60

80/73

25/0

30/286

4952

9

80/73

25/0

65/193

19791

9

80/75

80/73

25/0

14/189

27558

9

80

60/95

61/0

20/393

58823

8

60/95

61/0

20/363

157870

8

10/98

60/95

61/0

50/360

199980

8

100

 

در این جداول  نشان‌دهندۀ اندازۀ کارها و #opt نمایانگر تعداد مسائلی است که جواب بهینۀ آنها در زمان کمتر از 1800 ثانیه به ‌دست آمده است. همچنینAvg. Nodes میانگین تعداد گره‌های بررسی‌شده برای رسیدن به جواب بهینه و Avg times میانگین زمان اجرای برنامه برای ده نمونه مسئله را نشان می‌دهد. Avg (LB1)و Avg ( ) وAvg.( )به‌ترتیب نشانگر میانگین حدود پایین ، ،  و Avg (UB) میانگین حد بالا برای ده نمونه مسئله هستند. لازم به ذکر است، Gap که میانگین شکاف بهینگی نامیده می‌شود، برای مسائلی محاسبه می‌شود که جواب بهینه در زمان 1800 ثانیه به دست نمی‌آید. میانگین شکاف بهینگی از رابطۀ زیر حاصل می‌شود:

رابطۀ 7

 

در جدول 2) ظرفیت انباشته برابر 10 و زمان پردازش کارها به‌طور تصادفی در بازۀ ]10-1[ در نظر گرفته شده است. همان‌طورکه مشاهده می‌‌شود زمانی‌که اندازۀ کارها بزرگ باشد، زمان اجرای الگوریتم شاخه و حد نیز افزایش می‌یابد. هنگامی‌که از حد پایین  در الگوریتم استفاده شود، افزایش زمان اجرا بیشتر است؛ زیرا ازآنجایی‌که حد پایین  نسبت به  و عمکرد ضعیف‌تری دارد، زمان اجرای الگوریتم نسبت به حالتی‌‌که از حد پایین  و استفاده شود به‌‌طور چشم‌گیری افزایش پیدا می‌کند. بیشترین زمان در نظر گرفته شده برای اجرای این الگوریتم 1800 ثانیه است که در این زمان یا الگوریتم جواب بهینه را پیدا می‌کند یا با بهترین جواب پیدا‌شده در این زمان متوقف می‌‌شود. باتوجه‌به نتایج جدول نتیجه می‌شود وقتی اندازۀ کارها در بازۀ ]10-1[ باشد و تعداد کارها 60 انتخاب شود، عملکرد  کاهش شدیدی می‌یابد و الگوریتم شاخه و کران زمان اجرای بیشتری می‌طلبد؛ درنتیجه در زمان تعیین‌شده این الگوریتم فقط قادر به حل بهینۀ نیمی از مسائل است. درصورتی‌که اگر از حدود پایین  و  در بدنۀ روش شاخه و کران استفاده شود، برای هر ده نمونه مسائل، جواب بهینه به دست می‌آید. هنگامی‌که تعداد کارها افزایش ‌یابد و برابر80 تا 100 انتخاب ‌شود الگوریتم شاخه و کران با حد پایین  قادر به یافتن جواب بهینۀ هیچ‌کدام از مسائل در زمان تعیین‌شده نیست. درحالی‌که اگر از حد پایین  و  استفاده شود بیش از نیمی از مسائل در زمان مدنظر به جواب بهینه می‌رسند. در‌این‌حالت از نظر زمان اجرا عملکرد  از بهتر است. البته برای مسائلی که در زمان تعیین‌شده به جواب بهینه نمی‌رسند مقدار  از رابطۀ (7) محاسبه می‌شود که این مقدار درصورت استفاده از کمتر می‌شود؛ یعنی در‌صورتی‌که از حد پایین  در روش شاخه و کران استفاده شود و الگوریتم در زمان تعیین‌شده به جواب بهینه نرسد جواب به‌دست‌آمده در زمان مذکور نزدیک‌تر از حالتی است که از حد پایین  استفاده شود؛ زیرا الگوریتم تولید حد پایین نسبت به دو الگوریتم دیگر حد پایین قوی‌تری تولید می‌کند.

اگر اندازۀ کارها در بازۀ ]8-4[ انتخاب شود، درحالتی‌که تعداد کارها کمتر یا مساوی 60 باشد، هر سه الگوریتم جواب بهینه را در زمان تعیین‌شده می‌یابند؛ با این تفاوت که روش شاخه و حدی که از حد پایین  استفاده می‌کند بهترین و  بدترین عملکرد را از نظر زمان اجرا دارند؛ اما هنگامی‌که تعداد کارها زیاد شود (بیشتر از 60 کار)  بهترین عملکرد را دارد. زمانی‌که اندازۀ کارها کوچک باشد (حداکثر به‌اندازۀ نصف ظرفیت ماشین باشد) الگوریتم شاخه و کران با حد پایین  بهترین عملکرد و بدترین عملکرد را از نظر زمان اجرا دارد. درواقع زمانی‌که ظرفیت انباشته زیاد و اندازۀ کارها کوچک باشد  عملکرد بهتری دارد و قادر به یافتن جواب بهینه در زمان کمتری نسبت به  و  است.

در جدول (3) Error! Reference source not found.ظرفیت انباشته کاهش یافته و برابر 5 در نظر گرفته شده است. زمان پردازش کارها نیز به‌‌طور تصادفی در بازۀ ]10-1[ در نظر گرفته شده است. وقتی اندازۀ کارها در بازۀ ]5-1[ است،  بهترین عملکرد را دارد و در زمان کمتری به جواب بهینه می‌رسد؛ اما هنگامی‌که اندازۀ کارها در بازۀ ]4-2[ قرار می‌گیرد روش شاخه و حد با هر سه حد معرفی‌شده، جواب بهینۀ مسائل را در زمان تعیین‌شده به‌ دست می‌آورد؛ چون اندازۀ کارها کاهش می‌یابد. اگرچه در‌این‌حالت نیز ابتدا  و سپس  بهترین عملکرد را دارد. در جداول (4) و (5) زمان پردازش کارها نسبت به جداول (2) و (3) کاهش یافته است و نتایج محاسبات نشان می‌دهد اگر زمان پردازش کارها کاهش یابد سرعت اجرای الگوریتم شاخه و حد افزایش می‌یابد.

برای نمایش بهتر، نتایج روش شاخه و حد درقالب شکل 1 تا شکل 3ارائه شده است. این شکل‌ها به‌ترتیب تعداد گره‌های بررسی‌شده، زمان و تعداد مسائل حل‌شدۀ بهینه را در‌صورت استفاده از حدود پایین  و  و  نشان می‌دهد.

شکل (1) میانگین تعداد گره‌های بررسی‌شده با الگوریتم شاخه و کران با حدود پایین مختلف را نشان می‌دهد. همان‌طورکه دیده می‌شود وقتی اندازۀ کارها کوچک‌تر یا مساوی نصف ظرفیت ماشین باشد میانگین تعداد گره‌های بررسی‌شده به‌وسیلۀ هر سه حد پایین برابر است و همۀ مسائل در زمان مشخص‌شده حل شده‌اند؛ اما زمانی‌که اندازۀ کارها نسبت به ظرفیت ماشین بزرگ می‌شود پیچیدگی مسئله افزایش می‌یابد و در درخت شاخه و حد میانگین تعداد گره‌های بررسی‌شده برای رسیدن به جواب بهینه زیاد می‌شود. در‌این‌حالت حد پایین  عملکرد ضیفی دارد و بهتر است از حدود پایین دیگر در بدنۀ شاخه و حد استفاده شود. دربارۀ استفاده از حد پایین  باید گفت که اگر‌چه کیفیت حدود پایینی که تولید می‌کند از دو الگوریتم دیگر بهتر است، زمان اجرای الگوریتم بیشتر است؛ چون در یکی از گام‌های الگوریتم باید مسئلۀ حداکثر تطابق وزنی حل شود. هرچند در این پژوهش از الگوریتم ادموند (که باعث بهبود زمان اجرای الگوریتم می‌شود) برای حل مسئله استفاده شده است، به ‌نظر می‌رسد اگر از زبان‌های برنامه‌نویسی با سرعت بیشتر مثل C استفاده شود سرعت اجرای الگوریتم افزایش می‌یابد و در مسائل با اندازۀ کارهای بزرگ کارایی بهتری نسبت به حدود پایین دیگر دارد. شکل 3 تعداد مسائل حل‌شدۀ بهینه را با استفاده از روش شاخه و حد در زمان تعیین‌شده نشان می‌دهد. در این شکل نیز عملکرد بهتر حدود  و  نبست به حد  در نمونه مسائل با کارهای با اندازۀ بزرگ به‌وضوح مشخص است.

 

 

 

 

 

 

شکل 1- نتایج تعداد گره‌های بررسی‌‌شده با استفاده از روش شاخه و حد

 

 

 

 

 

شکل 2- نتایج زمان حل مسائل با استفاده از روش شاخه و حد

 

 

شکل 3- نتایج تعداد مسائل حل‌شدۀ بهینه با استفاده از روش شاخه و حد

نتیجه‌گیری

در این مقاله روش شاخه و حد برای حل مسئلۀ زمان‌بندی یک ماشین پردازندۀ انباشته با فرض وجود کارهای با اندازۀ غیریکسان ارائه شد. در این روش برای تولید حد بالا از دو روش ابتکاری FFLPT و BFLPT استفاده و کمترین مقدار از بین آنها برای یک حد بالا در مسئله به کار گرفته شد.هم‌چنین برای تولید حد پایین از سه الگوریتم  و  و  استفاده و نتایج آنها با هم مقایسه شد. در محاسبۀ الگوریتم  باید یک مسئلۀ حداکثر تطابق وزنی حل شود که در پژوهش قبل از جعبه بهینه‌سازی موجود در نرم‌افزار متلب استفاده شده است و مبتنی‌بر روش شاخه و حد عمل می­کند؛ اما در این پژوهش از الگوریتم ادموند برای حل این مسئله استفاده شد و قادر است در زمان چندجمله­ای مسئلۀ مدنظر را حل کند؛ بنابراین در زمان حل الگوریتم، بهبود حاصل شده است. نتایج محاسبات نشان داد که در الگوریتم شاخه و کرانِ استفاده‌شده، وقتی اندازۀ کارها نسبت به ظرفیت ماشین بزرگ باشد حد پایین  بهترین عملکرد را دارد؛ زیرا کیفیت حدود پایینی که تولید می‌کند از  و زمان اجرای آن نیز از الگوریتم  بهتر است؛ بنابراین تعداد مسائلی که جواب بهینۀ آنها در زمان تعیین‌شده به‌دست آمده است بیشتر از حالتی است که از دو حد پایین دیگر استفاده شود؛ اما وقتی اندازۀ کارها نسبت به ظرفیت ماشین کوچک باشد (حداکثر به‌اندازۀ نصف ظرفیت ماشین) الگوریتم شاخه و کران با حد پایین  بهترین عملکرد را دارد. همچنین وقتی اندازۀ کارها متوسط باشد  بهترین عملکرد را دارد؛ بنابراین طبق نتایج به‌دست‌آمده از این پژوهش، با‌توجه‌به اندازۀ کارها از حدود پایین مختلف استفاده می‌شود و نتایج روش شاخه و حد بهبود می‌یابد.

برای پژوهش‌های آینده، پیشنهاد می‌‌شود سایر روش‌های حل دقیق مانند روش تولید ستون برای حل این مسئله به کار برده شود و نتایج آن با نتایج الگوریتم شاخه و کران درصورت استفاده از حدود پایین  و  مقایسه شود. همچنین ممکن است استفادۀ ‌هم‌زمان از دو حد پایین به‌صورت هوشمندانه نتایج بهتری به دست آورد.



[i]- Batch processing machines

[ii]- Uzsoy, R.

[iii]- Etching process

[iv]- Photolithography

[v]- Numerically controlled routers

[vi]- Mathirajan, M. & Sivakumar, A. I.

[vii]- Yaghubian, A.R., Hodgson, T.J., Joines, J.A., Culbreth, C.T., & Huang, J.C.

[viii]- Oulamara

[ix]- Mathirajan, M. & Sivakumar, A. I.

[x]- Ikura, Y. & Gimple, M

[xi]- Non-identical jobes

[xii]- Dobson, G. & Nambimadom, R. S.

[xiii]- Longest Processing Time

[xiv]- Dupont, L. & Ghazvini, F. J

[xv]- Zhang, G., Cai, X., Lee, C. Y., & Wong, C. K.

[xvi]- Dupont, L. & Dhaenens-Flipo, C.

[xvii]- Parsa, N. R., Karimi, B. & Husseinzadeh Kashan, A.

[xviii]- Malapert A., Guéret C. & Rousseau L.M

[xix]- Lower Bound

[xx]- Wang, S., Liu, M., Chu, F., & Chu, C.

[xxi]-  constraint

[xxii]- Melouk, S., Damodaran, P. & Chang, P.Y

[xxiii]- Nong Q.Q., Ng C.T. & Cheng T.C.E.

[xxiv]- Husseinzadeh Kashan, A., Karimi, B. & Jolai, F.

[xxv]- Husseinzadeh Kashan, A., Karimi, B., & Jolai, F.

[xxvi]- Xu, R., Chen, H. & Li, X

[xxvii]- Li, X., Huang, Y., Tan, Q. & Chen, H.

[xxviii]- Chandru, V., Lee, C. Y. & Uzsoy, R

[xxix]- Li X., Huang Y., Tan Q. & Chen H.

[xxx]- Koh S.G., Koo P.H., Kim D.C. & Hur W.S.

[xxxi]- Li

[xxxii]- Jia, Z., Li, X., & Leung, J.Y.T.

[xxxiii]- Damodaran, P., Diyadawagamage, D. A., Ghrayeb, O., & Vélez-Gallego, M. C.

[xxxiv]- Jia, Z.H., Li, K., & Leung, J.Y.T.

[xxxv]- Arroyo, J.E.C., Leung, J.Y.T.

[xxxvi]- First fit

[xxxvii]- Best fit

[xxxviii]- First-Fit Longest Processing Time

[xxxix]- Best-Fit Longest Processing Time

[xl]- Gabow

Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S. (1992). "Batching and scheduling jobs on batch and discrete processors". Operations research, 40(4), 750-763.

Arroyo, J.E.C., Leung, J.Y.T. (2017). "Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times". Computers & Operations Research, 78, 117-128.

Chandru, V., Lee, C. Y., & Uzsoy, R. (1993). "Minimizing total completion time on batch processing machines". The International Journal Of Production Research, 31(9), 2097-2121.

Chung, T. P., & Sun, H. (2018). “Scheduling batch processing machine problem with non-identical job sizes via artificial immune system”. Journal of Industrial and Production Engineering, 35(3), 129-134.

Damodaran, P., Diyadawagamage, D. A., Ghrayeb, O., & Vélez-Gallego, M. C. (2012). “A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines”. The International Journal of Advanced Manufacturing Technology, 58(9-12), 1131-1140.

Dobson, G., Nambimadom, R. S. (2001). “The batch loading and scheduling problem”. Operations research, 49(1), 52-65.

 Dupont, L., & Ghazvini, F. J. (1998). “Minimizing makespan on a single batch processing machine with non-identical job sizes.” Journal européen des systèmes automatisés, 32(4), pp. 431-440.

Dupont, L., Dhaenens-Flipo, C. (2002). “Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure”. Computers & operations research, 29(7), 807-819.

Gabow, H. N. (1976). “An efficient implementation of Edmonds' algorithm for maximum matching on graphs”. Journal of the ACM (JACM), 23(2), 221-234.

Ikura, Y., Gimple, M. (1986). “Efficient scheduling algorithms for a single batch processing machine”. Operations Research Letters, 5(2), pp.61-65.

Jia, Z., Li, X., & Leung, J.Y.T. (2017). “Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities”. Future Generation Computer Systems, 67, 22-34.

Jia, Z.H., Li, K., & Leung, J.Y.T. (2015). “Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities”. International Journal of Production Economics, 169, 1-10.

Hosein Zade Kashan, A., Karimi, B. (2012) "New Lower Bounds for the Optimal Makespan on a Single Batch Processing Machine" . Amirkabir Journal of Mechanical Engineering. 43(2), pp. 75-84.

Husseinzadeh Kashan, A., & Karimi, B. (2008). “Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: an ant colony framework”. Journal of the Operational Research Society, 59(9), 1269-1280.

Husseinzadeh Kashan, A., Karimi, B, & Ghomi, S. F. (2009). “A note on minimizing makespan on a single batch processing machine with nonidentical job sizes”. Theoretical Computer Science410(27-29), 2754-2758.

Husseinzadeh Kashan, A., Karimi, B., & Jolai, F. (2006). “Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes.” International Journal of Production Research, 44(12), 2337-2360.

Husseinzadeh Kashan, A., Karimi, B., & Jolai, F. (2010). “An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes”. Engineering Applications of Artificial Intelligence, 23(6), 911-922.

Koh S.G., Koo P.H., Kim D.C., Hur W.S. (2005). “Scheduling a Single Batch Processing Machine with Arbitrary Job Sizes and Incompatible Job Families”. International Journal of Production Economic, 98(1): 81–96.

Lee, C. Y. (1999). “Minimizing makespan on a single batch processing machine with dynamic job arrivals”. International Journal of Production Research, 37(1), 219-236.

Li S, (2012), “Makespan Minimization on Parallel Batch Processing Machines with Release Times and Job Sizes”. Journal of Software, 7(6): 1203-1210.

Li X., Huang Y., Tan Q., Chen H. (2013). “Scheduling Unrelated Parallel Batch Processing Machines with Non-Identical Job Sizes”. Computers & Operations Research, 40(12): 2983–2990.

Li, X., & Zhang, K. (2018). “Single batch processing machine scheduling with two-dimensional bin packing constraints”. International Journal of Production Economics196, 113-121.

Li, X., Huang, Y., Tan, Q., & Chen, H. (2013). “Scheduling unrelated parallel batch processing machines with non-identical job sizes.” Computers & Operations Research, 40(12), pp.2983-2990.

Malapert A., Guéret C., Rousseau L.M. (2012). “A Constraint Programming Approach for a Batch Processing Problem with Non-Identical Job Sizes”. European Journal of Operational Research, 221(3): 533–545.

Mathirajan, M., Sivakumar, A. I. (2006). “A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor”. The International Journal of Advanced Manufacturing Technology, 29(9-10), 990-1001.

Melouk, S., Damodaran, P., & Chang, P.Y. (2004). “Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing.” International journal of production economics, 87(2), 141-147.

Nong Q.Q., Ng C.T., Cheng T.C.E. (2012). “The Bounded Single-Machine Parallel-Batching Scheduling Problem with Family Jobs and Release Dates to Minimize Makespan”. Operations Research Letters, 36 (1): 61-66.

Oulamara, A. (2007). “Makespan minimization in a no-wait flow shop problem with two batching machines.” Computers & operations research, 34(4), pp. 1033-1050.

Parsa, N. R., Karimi, B., & Husseinzadeh Kashan, A. (2010). “A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes”. Computers & Operations Research, 37(10), 1720-1730.

Uzsoy, R., (1994), “Scheduling a single batch processing machine with non-identical job sizes”. The International Journal Of Production Research, 32(7), 1615-1635.

Wang, S., Liu, M., Chu, F., & Chu, C. (2016). “Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration”. Journal of Cleaner Production, 137, 1205-1215.

Xu, R., Chen, H., Li, X. (2012). “Makespan minimization on single batch-processing machine via ant colony optimization”. Computers & Operations Research, 39(3), pp. 582-593.

Yaghubian, A.R., Hodgson, T.J., Joines, J.A., Culbreth, C.T., & Huang, J.C. (1999). “Dry kiln scheduling in furniture production.” IIE transactions, 31(8), pp.733-738.

Zhang, G., Cai, X., Lee, C. Y., & Wong, C. K. (2001). “Minimizing makespan on a single batch processing machine with nonidentical job sizes”. Naval Research Logistics (NRL), 48(3), 226-240.

Zhou, S., Xie, J., Du, N., & Pang, Y. (2018). “A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes”. Applied Mathematics and Computation334, 254-268.