Abstract




 
   

IJE TRANSACTIONS C: Aspects Vol. 27, No. 9 (September 2014) 1395-1404    Article Under Proof

downloaded Downloaded: 359   viewed Viewed: 2777

  MULTI-OBJECTIVE DIFFERENTIAL EVOLUTION FOR THE FLOW SHOP SCHEDULING PROBLEM WITH A MODIFIED LEARNING EFFECT
 
H. Amirian and R. Sahraeian
 
( Received: January 26, 2014 – Accepted: May 22, 2014 )
 
 

Abstract    This paper proposes an effective multi-objective differential evolution algorithm (MDES) to solve a permutation flow shop scheduling problem (PFSSP) with modified Dejong's learning effect. The proposed algorithm combines the basic differential evolution (DE) with local search and borrows the selection operator from NSGA-II to improve the general performance. First the problem is encoded with an appropriate rule to make the continuous nature of DE suitable for flow shop problems. Second, insert based local search is added in the initialization stage, as well as in each iteration to speed up convergence. The former guarantees that the algorithm commences with better solutions while the latter focuses the algorithm on promising areas. Third, in each generation, in order to improve diversity, two populations are introduced, current pop and advanced pop. The best solutions of each iteration are stored in the current pop, while the less desirable solutions are added to the advanced pop. At the end of each generation, the two are combined and better individuals are selected for the next generation. The algorithm is then tested on benchmark problems to demonstrate its effectiveness and the results are discussed. Finally, a truncated version of Dejong's learning effect is proposed and MDES is used to solve the permutation flow shop with the modified learning effect.

 

Keywords    Learning Effect, Differential Evolution, Multi-Objective Scheduling, Flowshop, Dejong’s Learning Effect

 

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

References   

 

1.     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-211.

2.     Cheng, H.C., Chiang, T.C. and Fu, L.C., "Multiobjective permutation flow shop scheduling by an adaptive genetic local search algorithm", IEEE World Congress on Computational Intelligence, Hong Kong: Evolutionary Computation. CEC,  (2008), 1596 - 1602.

3.     Eren, T. and Güner, E., "A bicriteria flowshop scheduling with a learning effect", Applied Mathematical Modelling,  Vol. 32, No. 9, (2008), 1719-1733.

4.     Biskup, D., "Single-machine scheduling with learning considerations", European Journal of Operational Research,  Vol. 115, No. 1, (1999), 173-178.

5.     Biskup, D., "A state-of-the-art review on scheduling with learning effects", European Journal of Operational Research,  Vol. 188, No. 2, (2008), 315-329.

6.     Chung, Y. and Tong, L., "Make-span minimization for m-machine permutation flow shop scheduling problem with learning considerations", Internationl Journal of Advanced Manufacturing Technology,  Vol. 56, No. 1-4, (2011), 355-367.

7.     Okołowski, D. and Gawiejnowicz, S., "Exact and heuristic algorithms for parallel-machine scheduling with dejong’s learning effect", Computers & Industrial Engineering,  Vol. 59, No. 2, (2010), 272-279.

8.     Cheng, T., Wu, C.-C., Chen, J.-C., Wu, W.-H. and Cheng, S.-R., "Two-machine flowshop scheduling with a truncated learning function to minimize the makespan", International Journal of Production Economics,  Vol. 141, No. 1, (2013), 79-86.

9.     Qian, B., Wang, L., Huang, D.-x., Wang, W.-l. and Wang, X., "An effective hybrid de-based algorithm for multi-objective flow shop scheduling with limited buffers", Computers & Operations Research,  Vol. 36, No. 1, (2009), 209-233.

10.   Sun, Y., Zhang, C., Gao, L. and Wang, X., "Multi-objective optimization algorithms for flow shop scheduling problem: A review and prospects", The International Journal of Advanced Manufacturing Technology,  Vol. 55, No. 5-8, (2011), 723-739.

11.   Chung, Y. and Tong, L., "Bi-criteria minimization for the permutation flow shop scheduling problem with machine based learning effects", Computers & Industrial Engineering,  Vol. 63, No. 1, (2012), 302-312.

12.   Corne, D.W., Jerram, N.R., Knowles, J.D. and Oates, M.J., "Pesa-ii: Region-based selection in evolutionary multiobjective optimization", in Proceedings of the Genetic and Evolutionary Computation Conference , GECCO’, Citeseer. (2001).

13.   Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T., "A fast and elitist multiobjective genetic algorithm: Nsga-ii", Evolutionary Computation, IEEE Transactions on,  Vol. 6, No. 2, (2002), 182-197.

14.   Suresh, R. and Mohanasundaram, K., "Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives", in Cybernetics and Intelligent Systems, Conference on, IEEE. Vol. 2, , (2004), 712-717.

15.   Varadharajan, T.K. and Rajendran, C., "A multi-objective simulated annealing algorithm for scheduling in flow shops to minimize the make-span and total flow time of jobs", European Journal of Operation Research,  Vol. 167, No. 3, (2005), 772-795.

16.   Pasupathy, T., Rajendran, C. and Suresh, R., "A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs", The International Journal of Advanced Manufacturing Technology,  Vol. 27, No. 7-8, (2006), 804-815.

17.   Qian, B., Wang, L., Huang, D.-X. and Wang, X., "Scheduling multi-objective job shops using a memetic algorithm based on differential evolution", The International Journal of Advanced Manufacturing Technology,  Vol. 35, No. 9-10, (2008), 1014-1027.

18.   Qian, B., Wang, L., Huang, D.-X. and Wang, X., "Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution", Soft Computing,  Vol. 13, No. 8-9, (2009), 847-869.

19.   Ali, M., Siarry, P. and Pant, M., "An efficient differential evolution based algorithm for solving multi-objective optimization problems", European Journal of Operational Research,  Vol. 217, No. 2, (2012), 404-416.

20.   Storn, R. and Price, K., "Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces, ICSI Berkeley,  (1995).

21.   Mahmoodabadi, M., Taherkhorsandi, M. and Safikhani, H., "Modeling and hybrid pareto optimization of cyclone separators using group method of data handling (gmdh) and particle swarm optimization (PSO)", International Journal of Engineering-Transactions C: Aspects,  Vol. 26, No. 9, (2012), 1089.

22.   Namakshenas, M. and Sahraeian, R., "Real-time scheduling of a flexible manufacturing system using a two-phase machine learning algorithm", International Journal of Engineering-Transactions C: Aspects,  Vol. 26, No. 9, (2013), 1067.

23.   Ghafari, E. and Sahraeian, R., "Appling metaheuristic algorithms on a two stage hybrid flowshop scheduling problem with serial batching", International Journal of Engineering, Vol. 27, No. 6, (2014).

24.   Hamta, N., Ghomi, S.F., Bahalke, U. and Golpaigani, H., "Single machine scheduling problem with precedence constraints and deteriorating jobs", International Journal of Engineering-Transactions A: Basics,  Vol. 24, No. 2, (2011), 115.

 





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