Details

Autor(en) / Beteiligte

• Iyer, Srikanth K.
• Saxena, Barkha

Titel

Improved genetic algorithm for the permutation flowshop scheduling problem

Ist Teil von

• Computers & operations research, 2004-04, Vol.31 (4), p.593-606

Ort / Verlag

New York: Elsevier Ltd

Erscheinungsjahr

2004

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Genetic algorithms (GAs) are search heuristics used to solve global optimization problems in complex search spaces. We wish to show that the efficiency of GAs in solving a flowshop problem can be improved significantly by tailoring the various GA operators to suit the structure of the problem. The flowshop problem is one of scheduling jobs in an assembly line with the objective of minimizing the completion time or makespan. We compare the performance of GA using the standard implementation and a modified search strategy that tries to use problem specific information. We present empirical evidence via extensive simulation studies supported by statistical tests of improvement in efficiency. Scope and purpose Genetic algorithms (GAs) are intelligent random search strategies which have been used successfully to find near optimal solutions to many complex problems. Implementation of GA in solving problems often overlooks certain information available in a particular problem. Making use of this information may need modification of the coding of the search space and of the operators constituting GA. This is a problem specific task. This paper hopes to address this issue with regard to solving the permutation flowshop problem. Henceforth we will refer to this as the flowshop problem, since we consider only the permutation flowshops. The questions we pose in order to implement the improved search heuristic can be extended easily to a host of scheduling problems with single and multi-objective optimization criteria. Flowshops are useful tools in modeling manufacturing processes. A permutation flowshop is a job processing facility which consists of several machines and several jobs to be processed on the machines. In a permutation flowshop all jobs follow the same machine or processing order. Flowshop refers to the fact that job processing is not interrupted once started. Our objective is to find a sequence for the jobs so that the makespan or the completion time is minimum. It is well known that this is a difficult problem to solve in a reasonable amount of time. In this paper we propose a modification to the existing GA implementation which incorporates the underlying “physics” of the flowshop problem.