Call for Paper - November 2022 Edition
IJCA solicits original research papers for the November 2022 Edition. Last date of manuscript submission is October 20, 2022. Read More

Pareto- Front Generation by Classical and Meta-heuristic Methods in Flexible Job Shop Scheduling with Multiple Objectives

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Maryam Ghasemi, Ali Farzan
10.5120/ijca2017913476

Maryam Ghasemi and Ali Farzan. Pareto- Front Generation by Classical and Meta-heuristic Methods in Flexible Job Shop Scheduling with Multiple Objectives. International Journal of Computer Applications 165(1):15-21, May 2017. BibTeX

@article{10.5120/ijca2017913476,
	author = {Maryam Ghasemi and Ali Farzan},
	title = {Pareto- Front Generation by Classical and Meta-heuristic Methods in Flexible Job Shop Scheduling with Multiple Objectives},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2017},
	volume = {165},
	number = {1},
	month = {May},
	year = {2017},
	issn = {0975-8887},
	pages = {15-21},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume165/number1/27537-2017913476},
	doi = {10.5120/ijca2017913476},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Planning and scheduling are as decision making processes which they have important roles in production systems and industries. According that, job shop scheduling is one of NP-hard problems to solve multi-objective decision making approaches. So, the problem is known as uncertain with many variables in optimal solution view. Finding optimal solutions are essential task in scheduling of jobs between machines in the industries. In this paper, we present classical sum weighted (WS) method and non-dominated sorting genetic algorithm II (NSGA-II) to solve flexible job shop scheduling problem (FJSSP) with multiple objectives and find Pareto-fronts: minimizing completion time of jobs and maximizing machine employment. To generate Pareto-fronts, a search algorithm uses mechanism of variable weights and random selection to change directions in search spaces. The experiment results indicate that NSGA-II solve the problem more acceptable than WS method with considering computing time and consuming memory.

References

  1. N. Kundakci, O. Kulak, "Hybrid Genetic Algorithms for Minimizing Makespan in Dynamic Job Shop Scheduling Problem", Computers & Industrial Engineering, Vol. 96, pp 31-51, 2016.
  2. M. R.Garey, D. S. Johnson, R. Sethi, "The complexity of Flow Shop and Job Shop Scheduling", Journal of Mathematics and Operations Research, Vol. 1, No. 2, 1976.
  3. Ryu, J. H., Kim, S. and Wan, H. 2009. Pareto Front Approximation with Adaptive Weighted Sum Method in Multi-Objective Simulation Optimization. IEEE Proceedings of the 2009 Winter Simulation Conference, pp. 623-633.
  4. Kim, Y. and Weck, O. D. 2004. Adaptive weighted-sum method for bi-objective Optimization: Pareto front generation. Structural and Multidisciplinary Optimization.
  5. A. Motaghedi, K. Sabri-Laghaie, M. Heydari, "Solving Flexible Job Shop Scheduling with Multi Objective Approach", International Journal of Industrial Engineering & Production Research, Vol. 21, No. 4, 2010.
  6. G. Zhang, L. Gao, Y. Y. Shi, "An effective genetic algorithm for the Flexible Job-Shop Scheduling problem", Expert Systems with Applications, Vol. 38, Vo. 4, pp. 3563-3573, 2011.
  7. A. Thammano, A. Phuang, "A Hybrid Artificial Bee Colony Algorithm with Local search for Flexible Job-Shop Scheduling Problem”, Procedia Computer Science, 20, pp. 96-101, 2013.
  8. K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, C. S. Chong, T. X. Cai, "An Improved Artificial Bee Colony Algorithm for Flexible Job-Shop Scheduling Problem with Fuzzy Processing Time", Expert Systems with Applications, Vol. 65, pp. 52-67, 2016.
  9. X. Li, L. Gao, "An effective hybrid Genetic Algorithm and Tabu Search for Flexible Job Shop Scheduling Problem", International Journal of production Economics, Vol. 174, pp. 93-110, 2016.
  10. G. Kanaani, R. Mogaddam, M. Tabari, Y. Zarandini, M. Arianezhad, "Resolving a New Multi-objective Scheduling Problem in cellular Production System by Using a Fusion Algorithm", Production and Operation Management Scientific-Research Journal, No. 2, pp. 1-28, 2012, in Persian.
  11. Fattahi, P, Arkat, K. Salehi, M. 2012. Scheduling Flexible Job Shop Systems with Setup Time Dependent on the Job Families, 5th International Conference on Industrial Engineering, in Persian.
  12. M. Milosevic, D. Lukic, M. Durdev, A. Antic, S. Borojevic, "An Overview Of Genetic Algorithms for Job Shop Scheduling Problems", Journal of Production Engineering, Vol. 8, No. 2, 2015.
  13. T. Murata, H. Ishibuchi, H. Tanaka, "Genetic Algorithms for Flow-Shop Scheduling Problems", Computers & Industrial Engineering, Vol. 30, Iss. 4, pp.1061-1071, 1996.
  14. L. Asadzadeh, "A Parallel artificial Colony Algorithm for the Job Shop scheduling Problem with a Dynamic Migration Strategy, Computers & Industrial Engineering", Vol. 102, pp. 359-367, 2016.
  15. A. Jamili, "Robust Job Shop Scheduling Problem: Mathematical Models, Exact and Heuristic Algorithms", Expert systems with Applications, Vol. 55, pp. 341-350, 2016.
  16. M. Beheshtiniya, N. Vakili, "Evaluation of Flexible Job Shop Scheduling algorithms and Comparing them with Bipartite Genetic Algorithm", Modeling in Engineering Journal, Vol. 13, No. 40, 2016, in Persian.
  17. N. b. Ho, J. C. Tay, M. Edmund, K. Lai, "An Effective Architecture for Learning and Evolving Flexible Job Shop Schedules", European Journal of Operational Research, Vol. 179, pp. 316–333, 2007.
  18. R. Shahryar, R. T. Hamid, M.A.S. Magdy, "A Novel Population Initialization Method for Accelerating Evolutionary Algorithms", Computers and Mathematics with Application, Vol. 53, pp. 1605–1614, 2007.
  19. Y. Yuan, H. Xu, "Flexible Job Shop Scheduling Using Hybrid Differential Evolution Algorithms", Computers & Industrial Engineering, Vol. 65. Iss. 2, pp 246-260, 2013.
  20. Ghaderi, H. Lotfi, S. and Esfahlan. M. 2011. An Introduction to Some Artificial Optimization Methods, First Edition, Islamic Azad University, Shabestar, Iran, in Persian.

Keywords

Multi-Objective Optimization, Flexible Job Shop Scheduling Problem, Weighted Sum Method, NSGA-II, Production Systems.