A heuristic combination method for solving job-shop scheduling problems.

Hart, Emma; Ross, Peter

Abstract

This paper describes a heuristic combination based genetic algorithm, (GA), for tackling dynamic job-shop scheduling problems. Our approach is novel in that the genome encodes a choice of algorithm to be used to produce a set of schedulable operations, alongside a choice of heuristic which is used to choose an operation from the resulting set. We test the approach on 12 instances of dynamic problems, using 4 different objectives to judge schedule quality. We find that our approach outperforms other heuristic combination methods, and also performs well compared to the most recently published results on a number of benchmark problems

• Start Date: Sep 27, 1998
• End Date: Sep 30, 1998
• Publication Date: 1998
• Deposit Date: Aug 27, 2010
• Peer Reviewed: Peer Reviewed
• Volume: 1498
• Pages: 845-854
• Book Title: Parallel Problem Solving from Nature V
• ISBN: 3-540-65078-4
• DOI: https://doi.org/10.1007/BFb0056926
• Keywords: genetic algorithm, (GA); job-shop scheduling; heuristic combination
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3180
• Publisher URL: http://dx.doi.org/10.1007/BFb0056926