ArticlePublisher preview available

Optimization of Multi Objective Job Shop Scheduling Problems Using Firefly Algorithm

Trans Tech Publications Ltd
Applied Mechanics and Materials
Authors:
Kuppusamy Udaiyakumar at SRM Institute of Science and Technology
Kuppusamy Udaiyakumar
Dr.M. Chandrasekaran at Vels institute of Science Technology and Advanced Studies
Dr.M. Chandrasekaran
  • Vels institute of Science Technology and Advanced Studies
Read publisher preview
Download citation
To read the full-text of this research, you can request a copy directly from the authors.

Abstract

Scheduling is the allocation of resources over time to carry out a collection of tasks assigned in any field of engineering and non engineering. Majority of JSSP are categorized into non deterministic (NP) hard problem because of its complexity. Scheduling are generally solved by using heuristics to obtain optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using available resources in many cases. Many researchers attempted to solve the problem by applying various optimization techniques. While using traditional methods they observed huge difficulty in solving high complex problems and meta-heuristic algorithms were proved most efficient algorithms to solve various JSSP so far. The objective of this paper i) to make use of a newly developed meta heuristic called Firefly algorithm (FA) because of inspiration on Firefly and its characteristic. ii) To find the combined objective function by determining optimal make span, mean flow time and tardiness of different size problems (using Lawrence 1-40 problems) as a bench marking dataset and to find the actual computational time. Iii) to prove that the proposed FFA algorithm is a good problem solving technique for JSSP with multi criteria.
A preview of this full-text is provided by Trans Tech Publications Ltd.
Learn more
Content available from Applied Mechanics and Materials 
This content is subject to copyright. Terms and conditions apply.
Optimization of multi objective Job Shop Scheduling problems using
Firefly algorithm
K.C.Udaiyakumar 1a* , M.Chandrasekaran 2
1Research Scholar, Sathyabama University, Chennai, India.
2Director, Department of Mechanical Engineering,Vels University, Chennai, India
akcudaiyakumar1967@gmail.com
Key words: Job shop scheduling problem, fire-fly, make span, mean flow time, tardiness,
benchmark.
Abstract. Scheduling is the allocation of resources over time to carry out a collection of tasks
assigned in any field of engineering and non engineering. Majority of JSSP are categorized into non
deterministic (NP) hard problem because of its complexity. Scheduling are generally solved by
using heuristics to obtain optimal or near optimal solutions because problems found in practical
applications cannot be solved to optimality using available resources in many cases. Many
researchers attempted to solve the problem by applying various optimization techniques. While
using traditional methods they observed huge difficulty in solving high complex problems and
meta-heuristic algorithms were proved most efficient algorithms to solve various JSSP so far. The
objective of this paper i) to make use of a newly developed meta heuristic called Firefly algorithm
(FA) because of inspiration on Firefly and its characteristic. ii) To find the combined objective
function by determining optimal make span, mean flow time and tardiness of different size
problems (using Lawrence 1-40 problems) as a bench marking dataset and to find the actual
computational time. iii) The analysis of the experimental results on Firefly algorithm based on
computational time is compared with other algorithms.
Introduction.
Job shop scheduling problem is one of the most difficult combinatorial problems. Scheduling is the
allocation of resources over time to perform a collection of tasks.The job shop scheduling
problem(JSP) consists of a set of m machines {M1,M2,........Mm}, and a collection of n jobs
{J1,J2.....Jn} to be scheduled, where each job must pass through each machine once only.
Each job has its own processing order and this may bear no relation to the processing order
of the any other job. Job Shop Scheduling problems are NP-hard problem, so its complexity is
more. Various optimization approaches have been widely applied to solve the JSSP. Conventional
methods based on mathematical methods and /or full numerical search (for example, Branch
and Bound [3,4] and Lagrangian Relaxation [5,6]) can guarantee the optimal solution. They
have been successfully used to solve the JSSP. However, these methods highly consume
computational time and resources even for solving moderately-large problem size and therefore
impractical if the computational limitation exists. Later, a larger size JSSP has been solved by an
approximation methods metaoroptimization -heuristics as such searchTabu [6], simulated
annealing [7], and nature inspired algorithms such as PSO[10]. The objective of this paper is i) to
make use of a recently developed meta heuristic called Firefly algorithm (FA) because of
inspiration on Firefly and its characteristic. ii) to find the combined objective function on,multi
objectives of JSSP[11,12] (i.e. make span minimization, tardiness and mean flow time) using 1-40
Lawrance problems[8,9,13]and iii) The analysis of the experimental results( computational time)
on Firefly algorithm is compared with HGA[14].
Firefly algorithm.
Inspiration and algorithm. Firefly algorithm idealizes some of the characteristics of the firefly
behavior. They follow three rules: a) all the fireflies are unisex, b) each firefly is attracted only
to the fireflies ,that are brighter than itself; Strength of the attractiveness is proportional to
Applied Mechanics and Materials Submitted: 2014-05-08
ISSN: 1662-7482, Vol. 591, pp 157-162 Revised: 2014-05-23
doi:10.4028/www.scientific.net/AMM.591.157 Accepted: 2014-05-23
© 2014 Trans Tech Publications Ltd, All Rights Reserved Online: 2014-07-18
All rights reserved. No part of contents of this paper may be reproduced or transmitted in any form or by any means without the written permission of Trans
Tech Publications Ltd, www.scientific.net. (Research Gate for subscription journals-27/02/25,11:47:31)
... The authors analyzed the results with ANOVA. Udaiyakumar and Chandrasekaran (2014) used a standard FA to combine the objective problem in FJSP. The parameter setting was done ad hoc. ...
INTEGRATED APPROACH OF SCHEDULING A FLEXIBLE JOB SHOP USING ENHANCED FIREFLY AND HYBRID FLOWER POLLINATION ALGORITHMS
Article
Full-text available
  • Dec 2022
  • Int J Ind Eng Appl Pract
Manufacturing industries are undergoing tremendous transformation due to Industry 4.0. Flexibility, consumer demands, product customization, high product quality, and reduced delivery times are mandatory for the survival of a manufacturing plant, for which scheduling plays a major role. A job shop problem modified with flexibility is called flexible job shop scheduling. It is an integral part of smart manufacturing. This study aims to optimize scheduling using an integrated approach, where assigning machines and their routing are concurrently performed. Two hybrid methods have been proposed: 1) The Hybrid Adaptive Firefly Algorithm (HAdFA) and 2) Hybrid Flower Pollination Algorithm (HFPA). To address the premature convergence problem inherent in the classic firefly algorithm, the proposed HAdFA employs two novel adaptive strategies: employing an adaptive randomization parameter (α), which dynamically modifies at each step, and Gray relational analysis updates firefly at each step, thereby maintaining a balance between diversification and intensification. HFPA is inspired by the pollination strategy of flowers. Additionally, both HAdFA and HFPA are incorporated with a local search technique of enhanced simulated annealing to accelerate the algorithm and prevent local optima entrapment. Tests on standard benchmark cases have been performed to demonstrate the proposed algorithm's efficacy. The proposed HAdFA surpasses the performance of the HFPA and other metaheuristics found in the literature. A case study was conducted to further authenticate the efficiency of our algorithm. Our algorithm significantly improves convergence speed and enables the exploration of a large number of rich optimal solutions.
View
... Fister et al. [17] did a comprehensive review of the firefly algorithm, which provided a good insight into the firefly algorithm with its modified versions. Ong et al. [18] compared the prey-predator algorithm with the Firefly algorithm and conducted a Mann-Whitney test to demonstrate the algorithm's efficiency. ...
A Dynamic Adaptive Firefly Algorithm for Flexible Job Shop Scheduling
Article
Full-text available
  • Sep 2021
An NP-hard problem like Flexible Job Shop Scheduling (FJSP) tends to be more complex and requires more computational effort to optimize the objectives with contradictory measures. This paper aims to address the FJSP problem with combined and contradictory objectives, like minimization of make-span, maximum workload, and total workload. This paper proposes ‘Hybrid Adaptive Firefly Algorithm’ (HAdFA), a new enhanced version of the classic Firefly Algorithm (FA) embedded with adaptive parameters to optimize the multi objectives concurrently. The proposed algorithm has adopted two adaptive strategies, i.e., an adaptive randomization parameter (α) and an effective heterogeneous update rule for fireflies. The adaptations proposed by this paper can help the optimization process to strike a balance between diversification and intensification. Further, an enhanced local search algorithm, Simulated Annealing (SA), is hybridized with Adaptive FA to explore the local solution space more efficiently. This paper has also attempted to solve FJSP by a rarely used integrated approach where assignment and sequencing are done simultaneously. Empirical simulations on benchmark instances demonstrate the efficacy of our proposed algorithms, thus providing a competitive edge over other nature-inspired algorithms to solve FJSP.
View
... Ong et al. [18] compared the prey-predator algorithm with the Firefly algorithm and conducted a Mann-Whitney test to demonstrate the algorithm's efficiency. Udaiyakumar et al. [19] solved the instances of Lawrence benchmark by FA for combined objective optimization. Bottani et al. [20] solved Flexible Manufacturing System's (FMS) loading problem by discrete FA with bi-objective. ...
A Dynamic Hybrid Firefly Algorithm to Minimize Make-span for Flexible Job Shop Scheduling
Article
Full-text available
  • Sep 2021
Among NP hard problems, Flexible Job Shop Scheduling Problem (FJSP) is the one with high computational intricacy for optimizing objectives. This paper addresses to solve a FJSP with an objective to minimize make-span. Meta heuristics based on swarm intelligence is gaining popularity among researchers due to less computational time required to optimize. Firefly algorithm (FA) is based on swarm intelligence that has less parameter. Nevertheless, FA has the disadvantage of premature convergence due to fixed values of certain parameters during optimization. The authors propose a new novel hybrid algorithm christened as Hybrid Adaptive Firefly Algorithm (HAdFA) in order to avert this issue. In the proposed technique two adaptive strategies have been adopted- i) An adaptive randomization parameter (α) and ii) An effective heterogeneous update rule for fireflies. Further, a local search algorithm with enriched features has been hybridized with Adaptive FA to explore local solution range more effectually. The adaptations proposed for FA in this article aids the optimization process to maintain a balance between diversification and intensification. The proposed algorithm has been tested on standard benchmark problems and comparing it with other similar approaches validates the results. The results indicate that the proposed HAdFA will be a competitive alternative to solve FJSP.
View
... The term production lead time is used for different purposes. It is usually used in the sense of flow time, which is defined as the time between the release time and the finishing time [16,17], and job-shop scheduling considering average flow time has been discussed by various research groups [18][19][20][21][22]. It is sometimes defined as the time between the release time and the due date, and a release time determination method using backward and forward scheduling based on dispatching rules was proposed [23]. ...
A Neighborhood Limitation Method for Job-Shop Scheduling Based on Simulated Annealing
Article
  • Jun 2020
Because of non-deterministic polynomial time hardness of job-shop scheduling problem (JSP), approximate optimization based on meta-heuristics has been actively discussed. Considering position of planners in production sites, it is desirable to develop a method in which their know-how is respected. An approach for meeting this requirement is to set the schedule generated by a planner as the initial solution and then gradually improve the solution by repeating a search in its neighborhood so that he/she can follow and thoroughly examine the improved solution. For this reason, this research is focused on scheduling using simulated annealing (SA). Because SA has a disadvantage that good solutions cannot be obtained efficiently if the initial solution has not been given appropriately, methods for solving this problem have been proposed for JSPs aiming at minimizing makespan. In high-mix low-volume manufacturing, it is also important to minimize production lead time to reduce work-in-process inventory. This research takes up production lead time defined as the time between the starting and the finishing times of a job considering strong constraint on places for putting works-in-process in production of large equipment, and deals with development of an efficient method using SA for JSPs aiming at minimizing the average value of the production lead times. Two methods of neighborhood limitation in SA for reducing the evaluation value were developed by focusing on waiting time of operations. It was proven that using one of the proposed methods in SA with appropriate probabilities is effective to JSPs of a certain size by numerical examples.
View
Firefly algorithm applied to the job-shop scheduling problem
Article
  • Dec 2021
The job shop scheduling problem (JSSP) is one of the most researched scheduling problems. This problem belongs to the NP-hard class. An optimal solution for this category of problems is rarely possible. We try to find suboptimal solutions using heuristics or metaheuristics. The firefly algorithm is a great example of a metaheuristic. In this paper, this algorithm is used to solve JSSP. We used some benchmarking JSSP datasets for experiments. The experimental program was implemented in the aitoa library. We investigated the optimal parameter settings of this algorithm in terms of JSSP. Analysis of the experimental results shows that the algorithm is useful to solve scheduling problems.
View
View
Multi Objective Optimization for Spur Gear Design Using Sheep Flocks Heredity Model Algorithm
Article
Full-text available
  • Jul 2014
In a perspective of stable industrial development to manufacture added consistent and economical industrial product, gears are ever more focus to requirements in terms of power capability, efficiency and compactness etc. In order to increase the performance factors of gears such as transmission capacity, efficiency, gear life, etc. is a difficult criteria for a design engineers as these are all progress in a conflicting behavior. This paper deals with the multi-objective optimization of spur gear drive design with two contradictory objective functions such as maximization of power transmission and minimization of volume of the gear drive. These objectives are approached by an optimization technique based on a Sheep Flocks Heredity Model Algorithm (SFHM) with design constraints like stress, center distance etc. A spur gear problem is solved with traditional trial method and results are compared with proposed algorithm.
View
Multiobjective Scheduling by Genetic Algorithms
Book
Full-text available
  • Jan 1999
Multiobjective Scheduling by Genetic Algorithms describes methods for developing multiobjective solutions to common production scheduling equations modeling in the literature as flowshops, job shops and open shops. The methodology is metaheuristic, one inspired by how nature has evolved a multitude of coexisting species of living beings on earth. Multiobjective flowshops, job shops and open shops are each highly relevant models in manufacturing, classroom scheduling or automotive assembly, yet for want of sound methods they have remained almost untouched to date. This text shows how methods such as Elitist Nondominated Sorting Genetic Algorithm (ENGA) can find a bevy of Pareto optimal solutions for them. Also it accents the value of hybridizing Gas with both solution-generating and solution-improvement methods. It envisions fundamental research into such methods, greatly strengthening the growing reach of metaheuristic methods. This book is therefore intended for students of industrial engineering, operations research, operations management and computer science, as well as practitioners. It may also assist in the development of efficient shop management software tools for schedulers and production planners who face multiple planning and operating objectives as a matter of course.
View
An Evolutionary Approach for Solving the Multi-Objective Job-Shop Scheduling Problem
Chapter
Full-text available
  • Apr 2007
In this chapter, we present an evolutionary approach for solving the multi-objective Job-Shop Scheduling Problem (JSSP) using the Jumping Genes Genetic Algorithm (JGGA). The jumping gene operations introduced in JGGA enable the local search process to exploit scheduling solutions around chromosomes, while the conventional genetic operators globally explore solutions from the population. During recent decades, various evolutionary approaches have been tried in efforts to solve JSSP, but most of them have been limited to a single objective, which is not suitable for real-world, multiple objective scheduling problems. The proposed JGGA-based scheduling algorithm heuristically searches for near-optimal schedules that optimize multiple criteria simultaneously. Experimental results using various benchmark test problems demonstrate that our proposed approach can search for the near-optimal and non-dominated solutions by optimizing the makespan and mean flow time. The proposed JGGA based approach is compared with another well established multi-objective evolutionary algorithm (MOEA) based JSSP approach and much better performance of the proposed approach is observed. Simulation results also reveal that this approach can find a diverse set of scheduling solutions that provide a wide range of choice for the decision makers.
View
View
Multiobjective Scheduling by Genetic Algorithms
Book
  • Jan 1999
http://www.amazon.com/Multiobjective-Scheduling-Genetic-Algorithms-Bagchi/dp/0792385616#reader_0792385616 Multiobjective Scheduling by Genetic Algorithms describes methods for developing multiobjective solutions to common production scheduling equations modelling in the literature as flowshops, job shops and open shops. The methodology is metaheuristic, one inspired by how nature has evolved a multitude of coexisting species of living beings on earth. Multiobjective flowshops, job shops and open shops are each highly relevant models in manufacturing, classroom scheduling or automotive assembly, yet for want of sound methods they have remained almost untouched to date. This text shows how methods such as Elitist Nondominated Sorting Genetic Algorithm (ENGA) can find a bevy of Pareto optimal solutions for them. Also it accents the value of hybridizing Gas with both solution-generating and solution- improvement methods. It envisions fundamental research into such methods, greatly strengthening the growing reach of metaheuristic methods. This book is therefore intended for students of industrial engineering, operations research, operations management and computer science, as well as practitioners. It may also assist in the development of efficient shop management software tools for schedulers and production planners who face multiple planning and operating objectives as a matter of course.
View
OR-Library: Distributing Test Problems by Electronic Mail
Article
  • Nov 1990
In this note we present a system (OR-Library) that distributes test problems by electronic mail (e-mail). This system currently has available test problems drawn from a number of different areas of operational research.
View
A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective
Article
  • May 2011
  • COMPUT OPER RES
In modern manufacturing systems, due date related performance is becoming increasingly important in maintaining a high service reputation. However, compared with the extensive research on makespan minimization, research on the total weighted tardiness objective is comparatively scarce, partly because this objective function is more difficult and complex to optimize. In this paper, we focus on the job shop scheduling problem with the objective of minimizing total weighted tardiness. First, we discuss the mathematical programming model and its duality when the processing orders for each machine are fixed. Then, a block-based neighborhood structure is defined and its important properties are shown. Finally, a simulated annealing algorithm is designed which directly utilizes the features of this neighborhood. According to the computational results, the new neighborhood considerably promotes the searching capability of simulated annealing and helps it converge to high-quality solutions.
View
An efficient job-shop scheduling algorithm based on particle swarm optimization
Article
  • Mar 2010
  • EXPERT SYST APPL
The job-shop scheduling problem has attracted many researchers’ attention in the past few decades, and many algorithms based on heuristic algorithms, genetic algorithms, and particle swarm optimization algorithms have been presented to solve it, respectively. Unfortunately, their results have not been satisfied at all yet. In this paper, a new hybrid swarm intelligence algorithm consists of particle swarm optimization, simulated annealing technique and multi-type individual enhancement scheme is presented to solve the job-shop scheduling problem. The experimental results show that the new proposed job-shop scheduling algorithm is more robust and efficient than the existing algorithms.
View
A new neighborhood and tabu search for the Blocking Job Shop
Article
  • Oct 2009
  • DISCRETE APPL MATH
The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.
View
Lagrangian bounds for just-in-time job-shop scheduling
Article
  • Mar 2008
  • COMPUT OPER RES
We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.
View