حل مسأله زمان‏بندی چند عاملی در محیط جریان کارگاهی با در نظر گرفتن اثر زمانی و رد کردن کارها با استفاده از یک الگوریتم فراابتکاری

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

نویسندگان

1 دانشیار گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه شاهد، تهران، ایران.

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

چکیده

در این پژوهش یک مسأله زمان‏بندی چند عاملی، در محیط جریان کارگاهی مورد بررسی قرار گرفته است. مسأله زمان‏بندی چند عاملی، زیرمجموعه‏ای از مسائل زمان‏بندی چند هدفه است که در آن هر عامل، دارای مجموعه‏ای از کارها است و هدف آن، بهینه کردن تابع هدف مربوط به خود است. جهت واقعی‏تر کردن مسأله، دو مفروض کاربردی «اثر زمانی» و «رد کردن» در نظر گرفته شده است. یک مدل برنامه‏ریزی عدد صحیح مختلط برای مسأله ارائه شده است. همچنین با توجه به پیچیدگی مدل و عدم توانایی روش‏های حل دقیق در حل مسائل با ابعاد بزرگ، الگوریتم فراابتکاری ژنتیک مبتنی بر مرتب‏سازی نامغلوب پیشنهاد شده است. راه‌حل‏های حاصل از این الگوریتم و روش دقیق محدودیت جزئی تعمیم‌یافته، با هم مقایسه شده است و نتایج به دست آمده، عملکرد آن را تأیید می‏نماید.

کلیدواژه‌ها

موضوعات

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

Solving a multi-agent scheduling problem in a flow shop environment considering rejection and deteriorating jobs: using a meta-heuristic algorithm

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

  • Rashed Sahraeian 1
  • Majid Hosseinzadeh 2
1 Department of Industrial Engineering, Shahed University, Tehran,
2 Department of Industrial Engineering, Shahed University, Tehran,
چکیده [English]

A multi-agent scheduling problem in a flow shop environment has been considered in this study. Multi-agent scheduling problem is a subset of multi-objective scheduling problems in which each agent has a set of jobs and its aim is to optimize its own objective function. To make the proposed problem more realistic, two practical assumptions such as deteriorating jobs and rejection has been considered. A mixed integer programming model is presented for the problem. The main contribution of the proposed model is to consider multi-agent with two mentioned assumptions. Also, due to the complexity of the model and its inability to solve large-scale problems, a meta-heuristic Non-Dominated sorting Genetic Algorithm (NSGA-II) are developed. Obtained solutions of this algorithm are compared with exact augmented ε-constraint method and the results confirm its performance.

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

  • Scheduling
  • Agent
  • Rejection
  • Deteriorating jobs
  • MIP

مراجع

[1]       Pinedo, M., (2015). Scheduling. Springer.
[2]        Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D., Souhal, A., (2014). “Multi-agent scheduling”. Berlin Heidelberg: Springer Berlin Heidelberg. doi, 10(1007): 978-3.
[3]       Wu, W.H., Yin, Y., Wu, W.H., Wu, C.C., Hsu, P.H. (2014). “A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents”, Journal of Industrial and Management Optimization, 10(2): 591-611.
[4]       Shabtay, D., Gaspar, N., Kaspi, M. (2013). “A survey on offline scheduling with rejection”, Journal of Scheduling, 16(1): 3-28.
[5]       Baker, K.R., Smith, J.C., (2003). “A multiple-criterion model for machine scheduling”, Journal of Scheduling, 6(1): 7-16.
[6]        Agnetis, A., Mirchandani, P.B., Pacciarelli, D., Pacifici, A. (2004). “Scheduling problems with two competing agents”, Operations Research, 52(2): 229-242.
[7]        Fan, B.Q., Cheng, T.C.E. (2016). “Two-agent scheduling in a flowshop”, European Journal of Operational Research, 252(2): 376-384.
[8]        Choi, J.Y. (2015). “Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects”, Computers & Industrial Engineering, 83: 237-243.
[9]        Cheng, S.R., (2014). “Some new problems on two-agent scheduling to minimize the earliness costs”, International Journal of Production Economics, 156: 24-30.
[10]    Lei, D. (2015). “Variable neighborhood search for two-agent flow shop scheduling problem”, Computers & Industrial Engineering, 80: 125-131.
[11]    Lee, W.C., Chen, S.K., Chen, C.W., Wu, C.C. (2011). “A two-machine flowshop problem with two agents”, Computers & Operations Research, 38(1): 98-104.
[12]    Shiau, Y.R., Lee, W.C., Kung, Y.S., Wang, J.Y. (2016). “A lower bound for minimizing the total completion time of a three-agent scheduling problem”, Information Sciences, 340: 305-320.
[13]    Kunnathur, A.S., Gupta, S.K. (1990). “Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem”, European Journal of Operational Research, 47(1): 56-64.
[14]    Cheng, T.C.E., Lee, W.C., Wu, C.C. (2010). “Single-machine scheduling with deteriorating functions for jobs procedding times”, Applied Mathematical Modeling, 34(12): 4171-4178.
[15]    Yin, Y., Cheng, T.C.E., Wan, L., Wu, C.C.,  Liu, J. (2015). “Two-agent single-machine scheduling with deteriorating jobs”, Computers and Industrial Engineering, 81: 177-185.
[16]    Lee, W.C., Wang, W.J., Shiau, Y.R. Wu, C.C. (2010). “A single machine scheduling problem with two agent and deteriorating jobs”, Applied Mathematical Modeling, 34(10): 3098-3107.
[17]    Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L. (2000). “Multiprocessor scheduling with rejection”, SIAM Journal on Discrete Mathematics, 13(1): 64-78.
[18]    Feng, Q., Fan, B., Li, S., Shang, W., (2015). “Two-agent scheduling with rejection on a single machine”, Applied Mathematical Modelling, 39(3): 1183-1193.
[19]    Li, S., Yuan, J., (2010). “Parallel-machine scheduling with deteriorating jobs and rejection”, Theoretical Computer Science, 411(40): 3642-3650.
[20]    Wu, C.C., Lee, W.C., (2008). “Single-machine group-scheduling problems with deteriorating setup times and job-processing times”, International Journal of Production Economics, 115(1): 128-133.
[21]    Chen, D.S., Batson, R.G., Dang, Y., (2010). “Applied integer programming: modeling and solution”,1st edition, John Wiley & Sons.
[22]    Sadjadi, S.J., Heidari, M., Esboei, A.A., (2014). “Augmented ε-constraint method in multi objective staff scheduling problem: a case study”, The International Journal of Advanced Manufacturing Technology, 70(5-8): 1505-1514.
[23]    Ciro, G.C., Dugardin, F., Yalaoui, F., Kelly, R., (2016). “A NSGA-II and NSGA-III comparison for solving an open shop scheduling problem with resource constraints”, IFAC-Papers Online, 49(12): 1272-1277.
[24]    Asefi, H., Jolai, F., Rabiee, M., Araghi, M.T., (2014). “A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem”, The International Journal of Advanced Manufacturing Technology, 75(5-8): 1017-1033.
[25]    Zitzler, E., Deb, K., Thiele, L. (2000). “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation, 8(2): 173-195.
[26]    Zitzler, E., Deb, K., Thiele, L. (2000). “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation, 8(2): 173-195.
[27]    Goh, C.K., Tan, K.C., Liu, D.S., Chiam, S.C., (2010). “A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design”, European Journal of Operational Research, 202(1): 42-54.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 5، شماره 10
مرداد 1396
صفحه 17-29

فایل ها

هم رسانی

ارجاع به این مقاله

آمار