Journal
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 53, Issue 6, Pages 1832-1848Publisher
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
Recommended
No Data Available