Abstract




 
   

IJE TRANSACTIONS C: Aspects Vol. 30, No. 12 (December 2017) 1863-1869    Article in Press

PDF URL: http://www.ije.ir/Vol30/No12/C/7-2624.pdf  
downloaded Downloaded: 58   viewed Viewed: 513

  PARETO-BASED MULTI-CRITERIA EVOLUTIONARY ALGORITHM FOR PARALLEL MACHINES SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES
 
J. Rezaeian Zeidi, M. Zarei and K. Shokoufi
 
( Received: October 28, 2016 – Accepted in Revised Form: September 08, 2017 )
 
 

Abstract    This paper addresses an unrelated multi-machine scheduling problem with sequence-dependent setup time, release date and processing set restriction to minimize the sum of weighted earliness/tardiness penalties and the sum of completion times, which is known to be NP-hard. A Mixed Integer Programming (MIP) model is proposed to formulate the considered multi-criteria problem. Also, to solve the model for real-sized applications, a Pareto-based algorithm, namely controlled elitism non-dominated sorting genetic algorithm (CENSGA), is proposed. To validate its performance, the algorithm is examined under six performance metric measures, and compared with a Pareto-based algorithm, namely NSGA-II. The results are statistically evaluated by the Mann–Whitney test and t-test methods. From the obtained results based on the t-test, the proposed CENSGA significantly outperforms the NSGA-II in four out of six terms. Additionally, the statistical results from Mann–Whitney test show that the performance of the proposed CENSGA is better than the NSGA- II in two out of six terms. Finally, the experimental results indicate the effectiveness of the proposed algorithm for different problems.

 

Keywords    Multi-objective optimization, Unrelated parallel machine, Just-in-time scheduling, Controlled elitism non-dominated sorting genetic algorithm, Mixed integer programming, Sequence-dependent setup time

 

چکیده    این تحقیق، مسئله ماشین­های موازی نامرتبط با زمان آماده­سازی وابسته به توالی، زمان دسترس کارها و محدودیت پردازش کارها را مورد مطالعه قرار داده است. هدف، کمینه­سازی مجموع وزنی هزینه­های زود کرد و دیر کرد کارها و همچنین کمینه­سازی مجموع زمان­های تکمیل کارها می­باشد. برای مسئله مورد نظر، یک مدل خطی عدد صحیح مختلط ارائه گردیده شده است. همچنین از آنجایی که مسئله در دسته مسائل NP-Hard قرار دارد، برای حل مسائل در اندازه واقعی، یک الگوریتم مبتنی بر پارتو با نام CENSGA ارائه شده است. الگوریتم ارائه شده در شش معیار عملکردی با الگوریتم NSGA-II مورد مقایسه و اعتبار سنجی قرار گرفته شده است. نتایج بدست ­آمده به صورت آماری توسط آزمایش میانگین Mann–Whitney و آزمایش t مورد ارزیابی قرار داده شده­ است. نتایج حاصل از آزمایش t نشان می­دهد که الگوریتم CENSGA در چهار معیار از شش معیار به طور قابل توجهی عملکرد بهتری نسبت به الگوریتم NSGA-II داشته است. همچنین، نتایج آماری حاصل از آزمایش میانگین Mann–Whitney نشان می­دهد که عملکرد الگوریتم CENSGA در دو معیار از شش معیار بهتر از عملکرد الگوریتم NSGA-II بوده­ است. از اینرو، نتایج آزمایشات تجربی نشان دهنده کارایی بالا الگوریتم معرفی شده برای مسائل محتلف می­باشد.

References   

1.      Tavakkoli-Moghaddam, R., Taheri, F. and Bazzazi, M., "Multi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints", International Journal of Engineering, Transactions A: Basics,  Vol. 21, No. 3, (2008), 269-278.

2.      Behnamian, J., Zandieh, M. and Ghomi, S.F., "Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique", Soft Computing,  Vol. 15, No. 7, (2011), 1313-1331.

3.      Zarandi, M.F. and Kayvanfar, V., "A bi-objective identical parallel machine scheduling problem with controllable processing times: A just-in-time approach", The International Journal of Advanced Manufacturing Technology,  Vol. 77, No. 1-4, (2015), 545-563.

4.      Lin, Y.-K., Fowler, J.W. and Pfund, M.E., "Multiple-objective heuristics for scheduling unrelated parallel machines", European Journal of Operational Research,  Vol. 227, No. 2, (2013), 239-253.

5.      Tavakkoli-Moghaddam, R., Jolai, F., Khodadadeghan, Y. and Haghnevis, M., "A mathematical model of a multi-criteria parallel machine scheduling problem: A genetic algorithm (research note)", International Journal of Engineering-Transactions A: Basics,  Vol. 19, No. 1, (2006), 79-86.

6.      Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M. and Sassani, F., "Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints", Computers & Operations Research,  Vol. 36, No. 12, (2009), 3224-3230.

7.      Amin-Tahmasbi, H. and Tavakkoli-Moghaddam, R., "Solving a bi-objective flowshop scheduling problem by a multi-objective immune system and comparing with spea2+ and spga", Advances in Engineering Software,  Vol. 42, No. 10, (2011), 772-779.

8.      Deb, K., "Multi-objective optimization using evolutionary algorithms, John Wiley & Sons,  Vol. 16,  (2001).

9.      Zitzler, E. and Thiele, L., "Multiobjective optimization using evolutionary algorithms—a comparative case study", in international conference on parallel problem solving from nature, Springer., (1998), 292-301.

10.    Li, X., Amodeo, L., Yalaoui, F. and Chehade, H., "A multiobjective optimization approach to solve a parallel machines scheduling problem", Advances in Artificial Intelligence,  Vol. 2010, (2010), 1-10.

11.    Fakhrzad, M., Sadeghieh, A. and Emami, L., "A new multi-objective job shop scheduling with setup times using a hybrid genetic algorithm", International Journal of Engineering-Transactions B: Applications,  Vol. 26, No. 2, (2012), 207-218.

12.    Rahmati, S.H.A., "Proposing a pareto-based multi-objective evolutionary algorithm to flexible job shop scheduling problem", World Academy of Science, Engineering and Technology, International Journal of Mechanical, Aerospace, Industrial, Mechatronic and Manufacturing Engineering,  Vol. 6, No. 1, (2012), 316-321.

13.    Graham, R.L., Lawler, E.L., Lenstra, J.K. and Kan, A.R., "Optimization and approximation in deterministic sequencing and scheduling: A survey", Annals of discrete mathematics,  Vol. 5, (1979), 287-326.

14.    Chaudhry, I.A. and Drake, P.R., "Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms", The International Journal of Advanced Manufacturing Technology,  Vol. 42, No. 5, (2009), 581-594.

15.    Karimi, N., Zandieh, M. and Karamooz, H., "Bi-objective group scheduling in hybrid flexible flowshop: A multi-phase approach", Expert Systems with Applications,  Vol. 37, No. 6, (2010), 4024-4032.

16.    Rodriguez, F.J., Lozano, M., Blum, C. and GarcíA-MartíNez, C., "An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem", Computers & Operations Research,  Vol. 40, No. 7, (2013), 1829-1841.

17.    Schott, J.R., Fault tolerant design using single and multicriteria genetic algorithm optimization. 1995, Air Force Inst of Tech Wright-Patterson AFB OH.

18.    Chambari, A., Rahmati, S.H.A. and Najafi, A.A., "A bi-objective model to optimize reliability and cost of system with a choice of redundancy strategies", Computers & Industrial Engineering,  Vol. 63, No. 1, (2012), 109-119.

19.             Hollander, M., Wolfe, D.A. and Chicken, E., "Nonparametric statistical methods, John Wiley & Sons,  (2013).


Download PDF 



International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir