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

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

Mariappan Kadarkarainadar Marichelvam (Mepco Schlenk Engineering College, India) and Geetha Mariappan (Kamaraj College of Engineering and Technology, India)
DOI: 10.4018/978-1-5225-3035-0.ch009
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Scheduling is one of the most important problems in production planning systems. It is a decision-making process that plays a crucial role in many Industries. Different scheduling environments were addressed in the literature. Among them Flexible job-shop problem (FJSP) is an important one and it is an extension of the classical JSP that allows one operation which can be processed on one machine out of a set of alternative machines. 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 than JSP, and incorporates all the difficulties and complexities of JSP. This chapter addresses a hybrid genetic scatter search algorithm for solving multi-objective FJSP. Makespan and flow time are the objective functions considered in this chapter. The computational results prove the effectiveness of the proposed algorithm for solving flexible job-shop scheduling problem.
Chapter Preview
Top

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

Complete Chapter List

Search this Book:
Reset