Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling

Many real-world production scheduling problems involve the simultaneous optimization of multiple conflicting objectives that are challenging to solve without the aid of powerful optimization techniques. This includes the multi-objective Job-shop Scheduling Problem (JSP), which is among the most diff...

Full description

Saved in:

Bibliographic Details
Main Author:	Anuar, Nurul Izah
Format:	Thesis
Language:	English English
Published:	2022
Subjects:	T Technology (General) TS Manufactures
Online Access:	http://eprints.utem.edu.my/id/eprint/26914/1/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf http://eprints.utem.edu.my/id/eprint/26914/2/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utem-ep.26914
record_format	uketd_dc
institution	Universiti Teknikal Malaysia Melaka
collection	UTeM Repository
language	English English
advisor	Md Fauadi, Muhammad Hafidz Fazli
topic	T Technology (General) TS Manufactures
spellingShingle	T Technology (General) TS Manufactures Anuar, Nurul Izah Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
description	Many real-world production scheduling problems involve the simultaneous optimization of multiple conflicting objectives that are challenging to solve without the aid of powerful optimization techniques. This includes the multi-objective Job-shop Scheduling Problem (JSP), which is among the most difficult to solve owing to the existence of an intractably large, highly complex solution space. Particle Swarm Optimization (PSO) is a population-based metaheuristic that possesses many advantages compared to other metaheuristics in solving scheduling problems. However, due to the complex nature of the multi-objective JSP, a single approach like PSO is not sufficient to explore the search space effectively owing to its shortcoming such as the tendency to become trapped in local optima. Besides, since PSO operates in the continuous domain, it cannot be applied directly to solve a discrete problem like the JSP efficiently. This research first proposes an improved continuous MOPSO to address the rapid clustering problem that exists in the basic PSO algorithm using three improvement strategies: re-initialization of particles, systematic switch of best solutions and mutation on global best selection. In order to establish an efficient mapping between the particle’s position in the continuous MOPSO and the scheduling solution in the JSP, this research proposes the JSP to be adopted within a discrete MOPSO through a modified solution representation using the permutation-based representation and a modified setup of the particle’s position and velocity. The discrete MOPSO also includes the modified maximin fitness function to promote solution diversity in the selection of global best solutions. In order to accomplish better performance by improving the search quality and efficiency of the discrete MOPSO, this research proposes a hybrid with the Diversification Generation Method in Scatter Search, the non-dominated sorting mechanism in non-dominated sorting Genetic Algorithm II (NSGA-II) and the local search mechanism in Tabu Search. The experimentations of the proposed algorithm are conducted using existing benchmark instances and a published case study on an energy-efficient job-shop model. The computational results are evaluated against other optimization techniques published in the literature. From the results, it is found that the proposed improved algorithm is effective in solving the benchmark instances compared to when no improvement is implemented and with a reasonable increase in computational costs. It is also discovered that the hybrid-discrete MOPSO (HD-MOPSO) algorithm manages to obtain higher values in the performance metrics consisting of non-dominance ratio and hypervolume compared to the competing algorithms. For the non-dominance ratio, HD-MOPSO is able to contribute 89% to 100% of solutions to the reference Pareto front. For the hypervolume values, HD-MOPSO manages to obtain a minimum of 1.0172 to 1.2862 out of the optimum value of 1.44. As higher values of metrics indicate better performance, HD-MOPSO thus outperforms the competing algorithms in solving the benchmark instances and the published case study. For these types of problems, the proposed algorithm is demonstrated to be capable of producing higher percentages of solutions in the overall non-dominated set with better quality in terms of convergence and diversity than those obtained by the competing algorithms.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Anuar, Nurul Izah
author_facet	Anuar, Nurul Izah
author_sort	Anuar, Nurul Izah
title	Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
title_short	Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
title_full	Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
title_fullStr	Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
title_full_unstemmed	Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
title_sort	hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling
granting_institution	Universiti Teknikal Malaysia Melaka
granting_department	Faculty of Manufacturing Engineering
publishDate	2022
url	http://eprints.utem.edu.my/id/eprint/26914/1/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf http://eprints.utem.edu.my/id/eprint/26914/2/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf
_version_	1783728749913571328
spelling	my-utem-ep.269142023-10-16T11:09:57Z Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling 2022 Anuar, Nurul Izah T Technology (General) TS Manufactures Many real-world production scheduling problems involve the simultaneous optimization of multiple conflicting objectives that are challenging to solve without the aid of powerful optimization techniques. This includes the multi-objective Job-shop Scheduling Problem (JSP), which is among the most difficult to solve owing to the existence of an intractably large, highly complex solution space. Particle Swarm Optimization (PSO) is a population-based metaheuristic that possesses many advantages compared to other metaheuristics in solving scheduling problems. However, due to the complex nature of the multi-objective JSP, a single approach like PSO is not sufficient to explore the search space effectively owing to its shortcoming such as the tendency to become trapped in local optima. Besides, since PSO operates in the continuous domain, it cannot be applied directly to solve a discrete problem like the JSP efficiently. This research first proposes an improved continuous MOPSO to address the rapid clustering problem that exists in the basic PSO algorithm using three improvement strategies: re-initialization of particles, systematic switch of best solutions and mutation on global best selection. In order to establish an efficient mapping between the particle’s position in the continuous MOPSO and the scheduling solution in the JSP, this research proposes the JSP to be adopted within a discrete MOPSO through a modified solution representation using the permutation-based representation and a modified setup of the particle’s position and velocity. The discrete MOPSO also includes the modified maximin fitness function to promote solution diversity in the selection of global best solutions. In order to accomplish better performance by improving the search quality and efficiency of the discrete MOPSO, this research proposes a hybrid with the Diversification Generation Method in Scatter Search, the non-dominated sorting mechanism in non-dominated sorting Genetic Algorithm II (NSGA-II) and the local search mechanism in Tabu Search. The experimentations of the proposed algorithm are conducted using existing benchmark instances and a published case study on an energy-efficient job-shop model. The computational results are evaluated against other optimization techniques published in the literature. From the results, it is found that the proposed improved algorithm is effective in solving the benchmark instances compared to when no improvement is implemented and with a reasonable increase in computational costs. It is also discovered that the hybrid-discrete MOPSO (HD-MOPSO) algorithm manages to obtain higher values in the performance metrics consisting of non-dominance ratio and hypervolume compared to the competing algorithms. For the non-dominance ratio, HD-MOPSO is able to contribute 89% to 100% of solutions to the reference Pareto front. For the hypervolume values, HD-MOPSO manages to obtain a minimum of 1.0172 to 1.2862 out of the optimum value of 1.44. As higher values of metrics indicate better performance, HD-MOPSO thus outperforms the competing algorithms in solving the benchmark instances and the published case study. For these types of problems, the proposed algorithm is demonstrated to be capable of producing higher percentages of solutions in the overall non-dominated set with better quality in terms of convergence and diversity than those obtained by the competing algorithms. 2022 Thesis http://eprints.utem.edu.my/id/eprint/26914/ http://eprints.utem.edu.my/id/eprint/26914/1/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf text en public http://eprints.utem.edu.my/id/eprint/26914/2/Hybrid-discrete%20multi-objective%20particle%20swarm%20optimization%20for%20multi-objective%20job-shop%20scheduling.pdf text en validuser https://plh.utem.edu.my/cgi-bin/koha/opac-detail.pl?biblionumber=122094 phd doctoral Universiti Teknikal Malaysia Melaka Faculty of Manufacturing Engineering Md Fauadi, Muhammad Hafidz Fazli

Hybrid-discrete multi-objective particle swarm optimization for multi-objective job-shop scheduling

Similar Items