توسعه روش های فراابتکاری برای حل مسئله زمانبندی نیروی انسانی در محیط جریان کارگاهی

نوع مقاله : مقاله صنایع

نویسندگان

دانشگاه صنعتی نوشیروانی بابل

چکیده

در این تحقیق مسئله یکپارچه زمانبندی کارها و نیروی انسانی در محیط جریان کارگاهی مورد بررسی قرار گرفته است که در آن تعدادی نیروی انسانی با مهارت‌های مختلف وجود دارند که قابلیت انجام کارهای متفاوت با سرعت‌های مختلف را دارند. هدف مسئله تعیین زمانبندی کارها در مراحل مختلف و تخصیص نیروی انسانی به این مراحل است به‌گونه‌ای که بیشنه زمان تکمیل کارها (Cmax) کمینه شود. برای این منظور یک مدل ریاضی خطی عدد صحیح مختلط ارائه شده است که این مدل در نرم‌افزار CPLEX اجرا شده است که می‌تواند مسائل با ابعاد کوچک را در مدت‌زمان معقول حل‌شده است؛ اما به دلیل NP-hard بودن مسئله، این نرم‌افزار قادر به تولید جواب‌های بهینه برای مسائل با ابعاد بزرگ نمی‌باشد. برای این منظور، دو روش فراابتکاری مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات ارائه‌شده است؛ چون احتمال قرار گرفتن الگوریتم بهینه‌سازی ازدحام ذرات (PSO) در بهینه محلی زیاد است، عملکرد این الگوریتم با استفاده از الگوریتم تبرید شبیه‌سازی شده (SA) بهبود داده‌شده است (IPSO). نتایج نشان می‌دهد که الگوریتم IPSO عملکرد بهتری نسبت به الگوریتم PSO در تمامی ابعاد دارد و با بزرگ‌تر شدن ابعاد مسئله برتری الگوریتم IPSO محسوس‌تر می‌باشد.

کلیدواژه‌ها

موضوعات


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

Developing metaheuristic approaches to solve flow shop scheduling problem with worker assignment

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

  • Ebrahim Asadi Gangraj
  • Fatemeh Bozorgnezhad
  • Mohamad Mahdi Paydar
babol noshirvani university of technology
چکیده [English]

This research addresses a simultaneous jobs scheduling and worker assignment problem in flow shop environment in which there are some workers with different skills who can operate the jobs with different speed. The primary aim of the research is to schedule the jobs and assign the worker so that maximum completion time (Cmax) is minimized. To tackle this problem, a mixed integer linear programming model is introduced and is coded in CPLEX software so that it can obtain the optimal solutions in reasonable time. Due to NP-hardness of the research problem, CPLEX cannot achieve the optimal solutions for large-scale problems. Thus, two metaheuristic approaches based on particle swarm optimization (PSO) is proposed here. In order to trapping the PSO algorithm in local optima with high probability, the performance of the PSO algorithm is improved by simulated annealing (SA) algorithm (IPSO). The experimental results show that the IPSO algorithm can generate better results in entire scales and the superiority of the IPSO is significant in the large scale.

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

  • Flow shop
  • worker scheduling
  • mixed integer linear programming
  • particle swarm optimization algorithm
  • Simulated annealing algorithm
بهشتی­نیا،م. قاضی وکیلی،ن. (1394)، ارزیابی الگوریتم های زمانبندی تولید کارگاهی انعطاف­پذیر و مقایسه آنها با الگوریتم ژنتیک دوبخشی، مجله علمی پژوهشی مدل سازی در مهندسی، سال 13، شماره40.
[2] Asadi Gangraj, E, & Nahavandi, N. (2014) “A Metaheuristic approach for Batch Sizing and Scheduling Problem in Flexible Flow Shop with Unrelated Parallel Machines”. International Journal of Computer Applications, 97, 31-36.
[3]  Sadjadi, SJ,  Aryanezhad, MB &  Ziaee, M. (2008) “The General Flowshop Scheduling Problem: Mathematical Models The General Flowshop Scheduling Problem: Mathematical Models”,  Mathematical  Models. Journal of Applied Sciences, 8, 3032-3037.
[4] Shahnazari-Shahrezaei, P, Tavakkoli-Moghaddam, R & Kazemipoor, H. (2011) “Solving a bi-objective manpower scheduling problem considering the utility of objective functions”, IJE Transactions, 24, 251-262.
[5] Benavides, AJ, Ritt, M, & Miralles, C. (2014) “Flow shop scheduling with heterogeneous workers”, European Journal of Operational Research, 237, 713–720.
[6] Carniel, GC, Benavides, AJ & Ritt, M. (2013) “Models for the inclusion of workers with disabilities in flow shop scheduling problems”, Simpósio Brasileiro de Pesquisa Operacional.
[7] Mehravaran, Y & Logendran R. (2013) “Non-permutation flowshop scheduling with dual resources”, Expert Systems with Applications, 40, 5061–5076.
[8] Sánchez, HS & Montoya Torres, JR. (2009) “Mathematical model of workforce scheduling problem in flow shop with makespan minimization”, Journal of Computational Design and Engineering, 4, 190–201.
[9] Behnamian, J. (2014) “Scheduling and worker assignment problems on hybrid flow shop with cost-related objective function”, International Journal of Advanced Manufacturing Technology, 74, 267-283.
[10] Carniel, GC, Benavides, AJ & Ritt, M. (2015) “Including workers with disabilities in flow shop scheduling”,  IEEE International Conference on Automation Science and Engineering.
[11] Huq, F, Cutright, K & Martin C. (2004) “Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study”, international journal of management science, 32, 121 – 129.
[12] همتیان،ح. فریدون،ع. رجب­پور، م (1389)، بهینه سازی پانل ساندویچی هسته منشوری براساس الگوریتم گروه ذرات، مجله علمی پژوهشی مدل سازی در مهندسی، سال 8، شماره20.
[13] Pal, A, Singh, SB, & Deep, K. (2011) “Use of Particle Swarm Optimization Algorithm for Solving Integer and Mixed Integer Optimization Problems”, International Journal of Computing Science and Communication Technologies, 4, 663-667.
[14] Ramanan, TR, Iqbal, M & Umarali, K. (2014) “A particle swarm optimization approach for permutation flow shop scheduling problem”, International Journal for Simulation and Multidisciplinary Design Optimization, 5, 2014.
[15] Liu, B, Wang, L, & Jin, Y. (2008) “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”, Computers & Operations Research, 35, 2791 – 2806.
[16] Sha, DY, & Lin, H. (2010) “A multi-objective PSO for job-shop scheduling problems”, Expert Systems with Applications, 37, 1065–1070.
[17] Qiu, X, & Lau, HYK. (2010) “An AIS-based Hybrid Algorithm with PSO for Job Shop Scheduling Problem”, IFAC Proceedings, 43, 350–355.
[18] Eddaly, M, Jarbouia, B, & Siarry, P. (2016) “ Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem”, Journal of Computational Design and Engineering, 3, 295–311.
] رستمی،ع. نوروزی،ا. مختاری، ه. نعمتی، ی. (1394)، مسئله بهینه­سازی پورتفولیوی چندهدفه با اهداف حداکثر کردن بازده، حداقل کردن ریسک و حداقل کردن تعداد دارایی، مجله علمی پژوهشی مدل سازی در مهندسی، سال 14، شماره45.
[20] Nouri, BV, Fattahi, P, Tavakkoli-Moghaddam, R, & Ramezanian, R. (2014) “A general flow shop scheduling problem with consideration of position based learning effect and multiple availability constraints”, The International Journal of Advanced Manufacturing Technology, 73, 601-611.
[21] Naderi, B, Zandieh, M, & Ghomi, SMT. (2009) “Scheduling Sequence-Dependent Set-up Time Job Shops with       Preventive Maintenance”, International Journal of Advanced Manufacturing Technology, 43, 170–181.
[22] Jabbarzadeh, F, Zandieh, M, & Talebi, D. (2009) “Hybrid flexible Flow Shops with Sequence-Dependent Setup Times and Machine Availability Constraints”, Computers & Industrial Engineering, 57, 949–957.