ارایه مدلی برای حل مساله زمان‌بندی جریان کارگاهی مختلط با جریان کالا و درنظر گرفتن زمان آماده‌سازی وابسته به توالی و زمان حمل‌ونقل

روح‌بخش, روجا; مهدی زاده, اسماعیل; ادیبی, محمد امین

doi:10.22105/dmor.2022.296154.1450

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

نویسندگان

گروه مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران.

https://doi.org/10.22105/dmor.2022.296154.1450

چکیده

هدف: جریان کالا یک تکنیک موثر برای افزایش کارایی تولید در یک سیستم تولیدی، با تبدیل یک کار به چندین قسمت کوچک‌تر می‌باشد که در سال‌های اخیر توجه‌های زیادی را به خود جلب کرده است؛ اما همواره از مفروضات مهمی که در محیط واقعی زمان‌بندی وجود دارد چشم‌پوشی شده است. هدف از انجام این مقاله ارایه‌ یک مدل ریاضی چندهدفه برای حل مساله‌ زمان‌بندی جریان کارگاهی مختلط با جریان کالا و درنظر گرفتن زمان آماده‌سازی وابسته به توالی و زمان حمل‌و‌نقل می‌باشد.
روش‌شناسی پژوهش: در ابتدا برای حل مساله‌ یک مدل برنامه‌ریزی ریاضی چندهدفه ارایه و آن‌گاه برای بررسی کارایی مدل ارایه‌شده، مدل به‌صورت وزنی به تک‌هدفه تبدیل شده و مثال‌هایی در ابعاد کوچک طراحی و با استفاده از سالور Cplex نرم‌افزار GAMS حل می‌شود. سپس با الهام از مطالعات پیشین برای حل مساله در ابعاد بزرگ، از الگوریتم‌های فرا ابتکاری مبتنی‌بر الگوریتم ژنتیک چندهدفه بهره گرفته می‌شود. برای بررسی کارایی الگوریتم‌ها، نتایج حاصل از سالور Cplex نرم‌افزار GAMS با خروجی حاصل از الگوریتم‌های فرا ابتکاری در حالت تک‌هدفه مقایسه می‌شود.
یافته‌ها: برای اعتبارسنجی مدل پیشنهادی نمونه مساله‌ای در ابعاد کوچک آورده شده است که با استفاده از سالور Cplex نرم‌افزار GAMS حل شده است و برای اعتبارسنجی الگوریتم‌های فرا ابتکاری مثال‌هایی در ابعاد کوچک حل و با جواب‌های حاصل از سالور Cplex نرم‌افزار GAMS مقایسه شده است. مقایسه نشان می‌دهد که الگوریتم‌های فرا ابتکاری از کارایی مناسبی برخوردار هستند. سپس برای حل مدل در ابعاد بزرگ‌تر از دو الگوریتم پیشنهادی استفاده شده است. برای این منظور، 30 نمونه مساله به‌صورت تصادفی تولید شده و از شش شاخص برای مقایسه‌ الگوریتم‌ها استفاده شده است. بعد از انجام آزمایش‌ها و مقایسه الگوریتم‌ها با یکدیگر، نتایج به‌دست‌آمده، کارایی بیش‌تر الگوریتم ژنتیک رتبه‌بندی نا‌مغلوب‌ها را نسبت به الگوریتم NSGA-II در حداقل سه شاخص نشان می‌دهد.
اصالت/ارزش افزوده علمی: در این مقاله محدودیت‌های زمان آماده‌سازی وابسته به توالی و زمان حمل‌و‌نقل بین ایستگاه‌های متوالی برای مساله‌ زمان‌بندی جریان کارگاهی مختلط با جریان کالا به‌منظور حل یک مدل ریاضی با هدف کمینه‌سازی ماکزیمم زمان تکمیل و مجموع تاخیر کار‌ها درنظر گرفته شده که فرض شده است زمان حمل‌ونقل مستقل از کار‌ها است و تنها یک وسیله نقلیه بین هر دو ایستگاه متوالی وجود دارد. جهت حل مدل در ابعاد بزرگ و با توجه به NP-hard بودن مساله از الگوریتم‌های NSGA-II و NRGA استفاده شد.

کلیدواژه‌ها

20.1001.1.25385097.1402.8.2.2.6

موضوعات

مدل‌های زمان‌بندی

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

Presenting a model for solving lot-streaming hybrid flow shop scheduling problem by considering independent setup time and transportation time

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

Roja Ruhbakhsh
Esmaeil Mehdizadeh
Mohammad Amin Adibi

Department of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

چکیده [English]

Purpose: Lot streaming, which has much attention in recent years, is an effective technique to increase production efficiency in a production system by splitting a job into several smaller parts in a multi-stage production system. But important assumptions that exist in the real-world scheduling environment are always ignored. Hence, in this paper, these assumptions are discussed and the results are reviewed. In this paper, the aim is solving a multi objective mathematical model for solving hybrid flow shop scheduling problem with lot-streaming, setup time and transportation time.
Methodology: At first, a multi objective mathematical programming model is presented for solving the problem. Then, by wighting method, the multi objective model convert to single objective model and GAMS software is used to solve the small size problems to show the performance of the mathematical mothel. Inspired by previous studies, two multi objective metaheuristic algorithms based on the genetic algorithm is used to solve the large-scale problems. To illustrate the performance of the proposed metaheuristic algorithms, the obtained results of the algorithms compared with GAMS outputs in single mode.
Findings: To validate the proposed model, a sample is solved using GAMS software and compared with the genetic algorithm. The obtained results show the performance of the mathematical model. Then, two proposed algorithms are used to solve the large-scale problems. For this purpose, 30 instance problems are randomly generated and six indicators are used to compare the algorithms. After performing the experiments and comparing the algorithms with each other, the results show NRGA algorithm performs bether than NSGA-II.
Originality/Value: In this paper, for solving a multi objective hybrid flow shop scheduling problem with lot-streamingm mathematical model with the aim of minimizing the makespan and total tardiness, the sequence-dependent setup time and the transportation time constraints between consecutive stages are considered. Since the problem is NP-hard, NSGA-II and NRGA algorithms were used to solve the proposed problem.

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

Scheduling
Hybrid flow shop
Lot-streaming
Transportation time
Setup time

مراجع

[1] Gupta, J. N. D. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the operational research society, 39(4), 359–364.

[2] Reiter, S. (1966). A system for managing job-shop production. The journal of business, 39(3), 371–393.

[3] Truscott, W. G. (1986). Production scheduling with capacity-constrained transportation activities. Journal of operations management, 6(3–4), 333–348.

[4] Pan, Q.-K., & Ruiz, R. (2012). An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega, 40(2), 166–180.

[5] Feldmann, M., & Biskup, D. (2008). Lot streaming in a multiple product permutation flow shop with intermingling. International journal of production research, 46(1), 197–216.

[6] Marimuthu, S., Ponnambalam, S. G., & Jawahar, N. (2008). Evolutionary algorithms for scheduling m-machine flow shop with lot streaming. Robotics and computer-integrated manufacturing, 24(1), 125–139.

[7] Martin, C. H. (2009). A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming. Omega, 37(1), 126–137.

[8] Tseng, C.-T., & Liao, C.-J. (2008). A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. European journal of operational research, 191(2), 360–373.

[9] Ulungu, E. L., Teghem, J., Fortemps, P. H., & Tuyttens, D. (1999). MOSA method: a tool for solving multiobjective combinatorial optimization problems. Journal of multicriteria decision analysis, 8(4), 221.

[10] Fatemi Qomi, M. T., Zandieh, M., & Moatarasini, S. M. (1384). Hybrid flow shop scheduling problem with sequence-dependent setup time [Thesis]. https://doi.org/10.1016/j.apm.2013.10.061.

[11] Fattahi, P., & Daneshamooz, F. (2016). A model for job shop scheduling with lot streaming and a parallel assembly stage. Journal of operational research in its applications, 13(3), 53–73.

[12] Lalitha, J. L., Mohan, N., & Pillai, V. M. (2017). Lot streaming in [N-1](1)+ N (m) hybrid flow shop. Journal of manufacturing systems, 44, 12–21.

[13] Chen, T.-L., Cheng, C.-Y., & Chou, Y.-H. (2020). Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming. Annals of operations research, 290, 813–836.

[14] Bagheri, M., Babaei Meybodi, N., & Enzebati, A. H. (2018). Modeling and optimizing a multi-objective flow shop scheduling problem to minimize energy consumption, completion time and tardiness. Journal of decisions and operations research, 3(3), 204–222. DOI:10.22105/dmor.2018.81214

[15] Wang, S., Kurz, M., Mason, S. J., & Rashidi, E. (2019). Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups. International journal of production research, 57(22), 6893–6907.

[16] Wang, S., Wang, X., & Yu, L. (2020). Two-stage no-wait hybrid flow-shop scheduling with sequence-dependent setup times. International journal of systems science: operations & logistics, 7(3), 291–307.

[17] Han, Y., Li, J., Liu, Y., Zheng, Z., Pan, Y., Sang, H., & Liu, L. (2019). Migrating birds optimization for lot-streaming flow shop scheduling problem [presentation]. 2019 ieee congress on evolutionary computation (cec) (pp. 667–672).

[18] He, X., Dong, S., & Zhao, N. (2019). Research on rush order insertion rescheduling problem under hybrid flow shop based on NSGA-III. International journal of production research, 58, 1–17. DOI:10.1080/00207543.2019.1613581

[19] Liu, S., Pei, J., Cheng, H., Liu, X., & Pardalos, P. M. (2019). Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes. Applied soft computing, 84, 105701. https://doi.org/10.1016/j.asoc.2019.105701

[20] Marichelvam, M. K., Geetha, M., & Tosun, Ö. (2020). An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors--A case study. Computers & operations research, 114, 104812. https://doi.org/10.1016/j.cor.2019.104812

[21] Li, Y., Li, X., Gao, L., Zhang, B., Pan, Q.-K., Tasgetiren, M. F., & Meng, L. (2021). A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. International journal of production research, 59(13), 3880–3899.

[22] Cai, J., Zhou, R., & Lei, D. (2020). Fuzzy distributed two-stage hybrid flow shop scheduling problem with setup time: collaborative variable search. Journal of intelligent & fuzzy systems, 38(3), 3189–3199.

[23] Li, J. qing, Tao, X. rui, Jia, B. xian, Han, Y. yan, Liu, C., Duan, P., … Sang, H. yan. (2020). Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots. Swarm and evolutionary computation, 52, 100600. DOI:10.1016/j.swevo.2019.100600

[24] Wang, P., Sang, H., Tao, Q., Guo, H., Li, J., Gao, K., & Han, Y. (2020). Improved migrating birds optimization algorithm to solve hybrid flowshop scheduling problem with lot-streaming. IEEE access, 8, 89782–89792.

[25] Shao, W., Shao, Z., & Pi, D. (2021). Multi-objective evolutionary algorithm based on multiple neighborhoods local search for multi-objective distributed hybrid flow shop scheduling problem. Expert systems with applications, 183, 115453. DOI:10.1016/j.eswa.2021.115453

[26] Dabiri, M., Yazdani, M., Naderi, B., & Haleh, H. (2022). Modeling and solution methods for hybrid flow shop scheduling problem with job rejection. Operational research, 22(3), 2721–2765. DOI:10.1007/s12351-021-00629-2

[27] Madenoğlu, F. (2021). Solving optimization problem with particle swarm optimization: solving hybrid flow shop scheduling problem with particle swarm optimization algorithm. In Applying particle swarm optimization: new solutions and cases for optimized portfolios (pp. 263–277). Cham: Springer International Publishing. DOI: 10.1007/978-3-030-70281-6_14

[28] Amirteimoori, A., Kia, R., & Tavakkoli-Moghaddam, R. (2021). Hybrid flow shop with limited transportation scheduling problem: a comparison between genetics algorithm, and a novel recursive local search heuristic. Research Square. DOI: 10.21203/rs.3.rs-687470/v1

[29] Engin, O., & İşler, M. (2022). An efficient parallel greedy algorithm for fuzzy hybrid flow shop scheduling with setup time and lot size: a case study in apparel process. Journal of fuzzy extension and applications, 3(3), 249–262.

[30] Zanjani, B., Amiri, M., Hanafizadeh, P., & Salahi, M. (2021). Robust multi-objective hybrid flow shop scheduling. Journal of applied research on industrial engineering, 8(1), 40–55.

[31] Zhang, B., Pan, Q., Gao, L., Zhang, X., Sang, H., & Li, J. (2017). An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming. Applied soft computing, 52, 14–27.

[32] Al Jadaan, O., Rao, C. R., & Rajamani, L. (2006). Parametric study to enhance genetic algorithm performance, using ranked based roulette wheel selection method [presentation]. International conference on multidisciplinary information sciences and technology (inscit2006) (Vol. 2, pp. 274–278).

[33] Deb, K. (2000). Multi-objective evolutionary optimization: past, present, and future. In Evolutionary design and manufacture: selected papers from acdm’00 (pp. 225–236). Springer.

[34] Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE transactions on evolutionary computation, 3(4), 257–271. DOI:10.1109/4235.797969

[35] Schott, J. R. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization. https://dspace.mit.edu/bitstream/handle/1721.1/11582/33945300-MIT.pdf?sequence=2%0Ahttp://oai.dtic
.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA296310

[36] Rahmati, S. H. A., Hajipour, V., & Niaki, S. T. A. (2013). A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem. Applied soft computing, 13(4), 1728–1740.

تصمیم گیری و تحقیق در عملیات

ارایه مدلی برای حل مساله زمان‌بندی جریان کارگاهی مختلط با جریان کالا و درنظر گرفتن زمان آماده‌سازی وابسته به توالی و زمان حمل‌ونقل

مراجع

مراجع

دوره 8، شماره 2
شهریور 1402
صفحه 307-332

ارایه مدلی برای حل مساله زمان‌بندی جریان کارگاهی مختلط با جریان کالا و درنظر گرفتن زمان آماده‌سازی وابسته به توالی و زمان حمل‌ونقل

مراجع

مراجع

دوره 8، شماره 2شهریور 1402صفحه 307-332

دوره 8، شماره 2
شهریور 1402
صفحه 307-332