4.7 Article

A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 53, Issue 6, Pages 1832-1848

Publisher

TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2014.962113

Keywords

scheduling; flexible-job-shop problem; genetic algorithm; variable neighbourhood search; total tardiness

Ask authors/readers for more resources

This paper addresses the flexible-job-shop scheduling problem (FJSP) with the objective of minimising total tardiness. FJSP is the generalisation of the classical job-shop scheduling problem. The difference is that in the FJSP problem, the operations associated with a job can be processed on any set of alternative machines. We developed a new algorithm by hybridising genetic algorithm and variable neighbourhood search (VNS). The genetic algorithm uses advanced crossover and mutation operators to adapt the chromosome structure and the characteristics of the problem. Parallel-executed VNS algorithm is used in the elitist selection phase of the GA. Local search in VNS uses assignment of operations to alternative machines and changing of the order of the selected operation on the assigned machine to increase the result quality while maintaining feasibility. The purpose of parallelisation in the VNS algorithm is to minimise execution time. The performance of the proposed method is validated by numerical experiments on several representative problems and compared with adapted constructive heuristic algorithms' (earliest due date, critical ratio and slack time per remaining operation) results.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available