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

Document Type : Industry Article

Authors

1 babol noshirvani university of technology

2 Babol Noshirvani University of Technology

Abstract

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.

Keywords

Main Subjects

References

بهشتی­نیا،م. قاضی وکیلی،ن. (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.
 
Journal of Modeling in Engineering
Volume 16, Issue 54
October 2018
Pages 283-293

Files

History

  • Receive Date: 03 May 2017
  • Revise Date: 13 September 2017
  • Accept Date: 25 October 2017

Share

How to cite

Statistics