Application of Hybrid Firefly Algorithm-Tabu Search Technique to Minimize the Makespan in Job Shop Scheduling problem

Application of Hybrid Firefly Algorithm-Tabu Search Technique to Minimize the Makespan in Job Shop Scheduling problem

Manoj Govind Kharat (National Institute of Industrial Engineering (NITIE), Mumbai, India), Siddhant Sanjeev Khadke (National Institute of Industrial Engineering (NITIE), Mumbai, India), Rakesh D. Raut (National Institute of Industrial Engineering (NITIE), Mumbai, India), Sachin S. Kamble (National Institute of Industrial Engineering (NITIE), Mumbai, India), Sheetal Jaisingh Kamble (National Institute of Industrial Engineering (NITIE), Mumbai, India) and Mukesh Govind Kharat (National Institute of Industrial Engineering (NITIE), Mumbai, India)
Copyright: © 2016 |Pages: 21
DOI: 10.4018/IJAIE.2016070101
OnDemand PDF Download:
List Price: $37.50


The Job shop scheduling problem is an important concern in the manufacturing systems. In this paper, the authors have proposed a hybrid firefly algorithm-tabu search combination technique to solve the Job shop scheduling problems. In the proposed algorithm, a complete scheme of algorithm for Job shop scheduling problems is designed and tabu search algorithm is incorporated with the aim of searching for local optimum of each individual. In order to improve the quality of solutions, in each step of the hybrid algorithms, an effective heuristic is proposed. The proposed heuristic reduces the overtime costs of operations by efficient use of the operation's slack. The performance of the proposed algorithm is tested and evaluated solving well-known benchmarked problems. Finally, the computational results are provided for evaluating the performance and effectiveness of the proposed solution approaches. The results have proved the superiority of proposed approach to other methods such as particle swarm optimization, genetic algorithm in terms of both efficiency and success rate.
Article Preview


Scheduling is one of the most important issues in the design of production system (Pinedo & Chao, 1999); it has gained much attention in the recent years (Pinedo, 2012). The principle aim of scheduling is to plan the sequence of work so that production can be systematically arranged towards the end of completion of all products by due date. The proper scheduling of machines in an industry can reduce the production hours that contributes to produce goods much faster (Harjunkoski et al., 2014).

Scheduling problems in their static and deterministic forms are simple to describe and formulate, but are difficult to solve as it involves complex combinatorial optimization. For example, if there are m machines, each of which is required to perform n independent operations. The combination can be potentially exploded up to (n!)m operational sequences. The Job shop scheduling problem (JSSP) is an important concern in the manufacturing systems. It has been known as one of the worst combinatorial optimisation problems ever since the 1950s in production scheduling categorized into Non-deterministic Polynomial-time hard (NP-hard) (Graham, 1966; Lenstra et al., 1977; Wang et al., 2008; Asadzadeh & Zamanifar, 2010). This means that due to the combinatorial explosion, even a computer can take unacceptably large amount of time to seek a satisfied solution on even moderately large scheduling problem. Another potential issue of complexity is the assembly relationship. Job shop scheduling problem is comprised of a set of independent jobs or tasks (J), each of which consists of a sequence of operations (O). Each operation is performed on machine (M) without interruption during processing time. The main purpose of JSSP is usually to find the best machine schedule for tuning all jobs in order to optimize either single criterion or multiple scheduling objectives (measures of performance) such as the minimization of the makespan (Cmax) or the penalty costs of tardiness and/or earliness.

In manufacturing environments, the scheduling problems are very complex and cannot usually be solved in reasonable time using the conventional optimization techniques. The JSSP involves the optimization of many manufacturing parameters, such as minimizing the total tardiness time (Lei & Guo, 2011; Tasgetiren et al., 2011), the makespan (Seo & Kim, 2010; Noorul Haq et al., 2010; Yang & Yang, 2010; Low et al., 2010; Wang & Wang, 2012), the machine idle time (Khorshidian et al., 2011), and the average completion time (Sitters, 2010) etc. of these parameters, the makespan is commonly used. Numerous studies have addressed the problem of minimizing the job makespan (Rajendran & Ziegler, 2004; Allahverdi & Aydilek, 2010; Zhang et al., 2011; Mokhtari et al., 2011; Ben Chihaoui et al., 2011).

Various optimization approaches have been widely applied to solve the JSSP. Conventional methods based on mathematical model and/or full numerical search (for example, Branch and Bound and Lagrangian Relaxation) can guarantee the optimum solution. They have been successfully used to solve JSSP. However, these methods may highly consume computational time and resources even for solving a moderate-large size problem and therefore are impractical if the computational limitation is existing. Due to the complexity involved in JSSP, recent research has focused on metaheuristic approaches, such as genetic algorithms (GAs) (Sakawa & Kubota, 2000; Prakash et al., 2011; Zhang et al., 2011), particle swarm optimisation (PSO) (Lei, 2012a, b), ant colony optimisation (ACO) (Rossi & Dini, 2007; Xing et al., 2010) tabu search (TS) (Nowicki & Smutnicki, 2005) memetic algorithm (MA) (Lacomme et al., 2012 and Gao et al., 2011), and a differential evolution (DE) algorithm (Tasgetiren et al., 2006). However, the approximation optimization methods or metaheuristics (e.g. Tabu search and simulated annealing) usually conduct stochastic steps in their search process for solving a large size problem, these methods guarantee no optimum solution.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 4: 2 Issues (2017)
Volume 3: 2 Issues (2016)
Volume 2: 2 Issues (2014)
Volume 1: 2 Issues (2012)
View Complete Journal Contents Listing