A Hybrid Genetic Scatter Search Algorithm to Solve Flexible Job Shop Scheduling Problems: A Hybrid Algorithm for Scheduling Problems

Introduction

Meticulous planning and scheduling is one of the most important issues tackled by many researchers in production management. Scheduling is defined as a type of decision-making process that plays a crucial role in our daily life. It refers to setting of operation that it will start dates so that jobs will be completed with their due date. In manufacturing areas, the objective of scheduling is to satisfy the customers by minimizing the lead time and so on. Different types of scheduling environments were addressed by Pinedo (1995). Among them the flexible job shop environment plays a vital role as many industries resemble it. Flexible job-shop problem (FJSP) can be considered as an addition of the standard JSP that permits one operation which can be handled on one machine out of a set of different machines (Zhang et al., 2009). It is closer to the real manufacturing situation. Because of the additional needs to determine the assignment of operations on the machines, FJSP is more complex. The FJSP are non-deterministic polynomial time hard (NP-hard) type combinatorial optimization problems which means scarcely any algorithm exist can solve the problem in polynomial time. Hence, the exact algorithms cannot be used to solve the problems. Researchers have suggested many heuristics and meta-heuristics to resolve these problems. Tabu search (TS), ant colony optimization (ACO), artificial immune system (AIS), particle swarm optimization (PSO) and genetic algorithm (GA) have been projected to solve the FJSP. In this chapter, a hybrid genetic scatter search algorithm (HGSSA) is recommended to solve the FJSP. The objective considered in this chapter is to minimize the weighted sum of makespan and mean flow time. The layout of a flexible job shop environment is given in Figure 1.

Figure 1.

Layout of a Flexible Job Shop Environment