Meta-heuristics for scheduling flexible job shop problems with constraints

Flexible job-shop scheduling problem (FJSSP) is an extension of the classical job shop scheduling problem (JSSP) with practical applications. FJSSP has been proven as an NP-hard problem. Many researchers have focused on FJSSP in recent years. FJSSP includes two sub-problems: 1. machine assignment th...

Full description

Saved in:
Bibliographic Details
Main Author: Gao, Kaizhou
Other Authors: Chong Chin Soon
Format: Theses and Dissertations
Language:English
Published: 2015
Subjects:
Online Access:https://hdl.handle.net/10356/65649
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-65649
record_format dspace
spelling sg-ntu-dr.10356-656492023-07-04T16:34:02Z Meta-heuristics for scheduling flexible job shop problems with constraints Gao, Kaizhou Chong Chin Soon Ponnuthurai N. Suganthan School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering Flexible job-shop scheduling problem (FJSSP) is an extension of the classical job shop scheduling problem (JSSP) with practical applications. FJSSP has been proven as an NP-hard problem. Many researchers have focused on FJSSP in recent years. FJSSP includes two sub-problems: 1. machine assignment that is to select a machine from a set of candidate machines for operations; 2. operation sequencing that is to schedule the operations on machines to obtain a feasible solution. In the classical JSSP problem, one operation can be processed on only one machine. Hence, the FJSSP is more difficult than the classical JSSP. There is a great variety of real-world problems that can be modeled as FJSSP, e.g., optimization of crane operations, simulation and optimization of transport systems, and scheduling of manufacturing and remanufacturing systems. In this thesis, the scheduling problems in the remanufacturing industry are modeled as FJSSP with multiple constraints. The constraints are new job insertion and uncertain processing time. The uncertain processing time constraint is built into two models, one is based on most probable processing time and another is based on fuzzy processing time. A rescheduling operator is executed when a new job is inserted or processing time becomes larger than the most probable processing time. The problem size may change dynamically during scheduling and rescheduling stages. The objectives include minimizing maximum completion time (Makespan), minimizing maximum machine workload, minimizing the average of earliness and tardiness and so on. Compared to exact methods, approximate methods, especially meta-heuristics, are better for solving FJSSP because meta-heuristics can obtain satisfactory solutions in a reasonable time. Meta-heuristics are more suitable for large-scale FJSSP. A music-inspired algorithm, discrete harmony search (DHS), and a nature-inspired algorithm, artificial bee colony (ABC), are investigated and improved to solve FJSSP with constraints. Two encoding and decoding methods are developed for solution representation. Several simple and ensemble heuristics are employed to initialize population. An effective heuristic, named MinEnd heuristic is proposed to generate a high quality initial solution. Dynamic grouping strategies of harmony memory and new crossover method for improvising new harmonies are proposed. Effective local search operators are proposed to improve algorithms’ performance. For the rescheduling operator, three re-scheduling strategies are proposed and compared. A two-stage discrete harmony search algorithm and a two-stage artificial bee colony algorithm are proposed for rescheduling FJSSP with remanufacturing constraints. Extensive experiments have been conducted to test the performance of the proposed algorithms for solving FJSSP with remanufacturing constraints. The instance sets used in this thesis include three sets of benchmark instances and two sets from remanufacturing industry. Single objective, multi-objective and Pareto-based multi-objective formulations are considered in this thesis. The proposed algorithms are compared to more than ten existing heuristics and algorithms. The comparisons with literature show the effectiveness and efficiency of the proposed heuristics and algorithms. DOCTOR OF PHILOSOPHY (EEE) 2015-12-01T04:28:19Z 2015-12-01T04:28:19Z 2015 2015 Thesis https://hdl.handle.net/10356/65649 10.32657/10356/65649 en 214 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering::Electrical and electronic engineering
spellingShingle DRNTU::Engineering::Electrical and electronic engineering
Gao, Kaizhou
Meta-heuristics for scheduling flexible job shop problems with constraints
description Flexible job-shop scheduling problem (FJSSP) is an extension of the classical job shop scheduling problem (JSSP) with practical applications. FJSSP has been proven as an NP-hard problem. Many researchers have focused on FJSSP in recent years. FJSSP includes two sub-problems: 1. machine assignment that is to select a machine from a set of candidate machines for operations; 2. operation sequencing that is to schedule the operations on machines to obtain a feasible solution. In the classical JSSP problem, one operation can be processed on only one machine. Hence, the FJSSP is more difficult than the classical JSSP. There is a great variety of real-world problems that can be modeled as FJSSP, e.g., optimization of crane operations, simulation and optimization of transport systems, and scheduling of manufacturing and remanufacturing systems. In this thesis, the scheduling problems in the remanufacturing industry are modeled as FJSSP with multiple constraints. The constraints are new job insertion and uncertain processing time. The uncertain processing time constraint is built into two models, one is based on most probable processing time and another is based on fuzzy processing time. A rescheduling operator is executed when a new job is inserted or processing time becomes larger than the most probable processing time. The problem size may change dynamically during scheduling and rescheduling stages. The objectives include minimizing maximum completion time (Makespan), minimizing maximum machine workload, minimizing the average of earliness and tardiness and so on. Compared to exact methods, approximate methods, especially meta-heuristics, are better for solving FJSSP because meta-heuristics can obtain satisfactory solutions in a reasonable time. Meta-heuristics are more suitable for large-scale FJSSP. A music-inspired algorithm, discrete harmony search (DHS), and a nature-inspired algorithm, artificial bee colony (ABC), are investigated and improved to solve FJSSP with constraints. Two encoding and decoding methods are developed for solution representation. Several simple and ensemble heuristics are employed to initialize population. An effective heuristic, named MinEnd heuristic is proposed to generate a high quality initial solution. Dynamic grouping strategies of harmony memory and new crossover method for improvising new harmonies are proposed. Effective local search operators are proposed to improve algorithms’ performance. For the rescheduling operator, three re-scheduling strategies are proposed and compared. A two-stage discrete harmony search algorithm and a two-stage artificial bee colony algorithm are proposed for rescheduling FJSSP with remanufacturing constraints. Extensive experiments have been conducted to test the performance of the proposed algorithms for solving FJSSP with remanufacturing constraints. The instance sets used in this thesis include three sets of benchmark instances and two sets from remanufacturing industry. Single objective, multi-objective and Pareto-based multi-objective formulations are considered in this thesis. The proposed algorithms are compared to more than ten existing heuristics and algorithms. The comparisons with literature show the effectiveness and efficiency of the proposed heuristics and algorithms.
author2 Chong Chin Soon
author_facet Chong Chin Soon
Gao, Kaizhou
format Theses and Dissertations
author Gao, Kaizhou
author_sort Gao, Kaizhou
title Meta-heuristics for scheduling flexible job shop problems with constraints
title_short Meta-heuristics for scheduling flexible job shop problems with constraints
title_full Meta-heuristics for scheduling flexible job shop problems with constraints
title_fullStr Meta-heuristics for scheduling flexible job shop problems with constraints
title_full_unstemmed Meta-heuristics for scheduling flexible job shop problems with constraints
title_sort meta-heuristics for scheduling flexible job shop problems with constraints
publishDate 2015
url https://hdl.handle.net/10356/65649
_version_ 1772826230469427200