An Improved Local Search Genetic Algorithm with Multi-crossover for Job Shop Scheduling Problem
Recent works are using meta-heuristics to address the problem class known in the literature as Job Shop Scheduling Problem (JSSP) because of its complexity, since it consists of combinatorial problems and belongs to the set of NP-Hard computational proble
- PDF / 1,090,640 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 245 Views
Federal University of S˜ ao Carlos, S˜ ao Carlos, Brazil {monique.viana,orides}@ufscar.br 2 University of S˜ ao Paulo, S˜ ao Carlos, Brazil [email protected]
Abstract. Recent works are using meta-heuristics to address the problem class known in the literature as Job Shop Scheduling Problem (JSSP) because of its complexity, since it consists of combinatorial problems and belongs to the set of NP-Hard computational problems. In this type of problem, one of the most discussed goals is to minimize the makespan, which is the maximum production time of a series of jobs. A widely used meta-heuristic in JSSP is the Genetic Algorithm (GA) due to its good performance in scheduling problems. However, for problems with high complexity, some form of hybridization in GA may be required to improve search space performance, for example, by including specialized local search techniques. It is proposed in this work the use of specialized and improved local search operators in the meta-heuristic GA with multi-crossover strategies in order to minimize makespan in JSSP: The Multi-Crossover Local Search Genetic Algorithm (mXLSGA). Specifically, all operators of the proposed algorithm have local search functionality beyond their original inspirations and characteristics. The developed method has been evaluated on 58 instances from well-established benchmarks. Experimental results have proven that mXLSGA is competitive and versatile compared to the state-of-the-art methods. Keywords: Genetic Algorithm · Local search · Multi-crossover Shop Scheduling Problem · Combinatorial optimization
1
· Job
Introduction
Scheduling problems have been extensively researched in recent years because it is a high complexity combinatorial optimization problem and it is classified as NP-Hard. Among the machine scheduling problems, there are several variations, such as Job Shop Scheduling Problem (JSSP), Flexible Job Shop Scheduling Problem (FJSSP), Flow Shop Scheduling Problems, etc. In this paper, we will discuss the JSSP variant. c Springer Nature Switzerland AG 2020 L. Rutkowski et al. (Eds.): ICAISC 2020, LNAI 12415, pp. 464–479, 2020. https://doi.org/10.1007/978-3-030-61401-0_43
An Improved Local Search Genetic Algorithm with Multi-crossover for JSSP
465
In recent years, several meta-heuristic approaches have been proposed to treat the JSSP, such as Greedy Randomized Adaptive Search Procedure (GRASP) [8], Local Search Genetic Algorithm (LSGA) [22], Parallel Agentbased Genetic Algorithm (PaGA) [6], Agent-based Local Search Genetic Algorithm (aLSGA) [5], Golden Ball Algorithm (GB) [24], Initial Population Based Genetic Algorithm (IPB-GA) [17], Memetic Algorithm (MA) [19], Improved Biogeography-Based Optimization (IBBO) [23], Grey Wolf Optimization (GWO) [15], Hybrid Grey Wolf Optimization (HGWO) [14], Memetic Chicken Swarm Optimization (MeCSO) [25], Genetic Algorithm with a critical-path-guided Giffler and Thompson crossover operator (GA-CPG-GT) [18] and Discrete Wolf Pack Algorithm (DWPA) [26]. Most state-of-the-art studies on JSSP have validated t
Data Loading...
