ETM 645-9 (Spring '14)Lesson: Meta-Heuristics and Simulated AnnealingObjectives:1. Define meta-heuristics.2. Briefly describe the 5 primary meta-heuristics: Ant Colony, Iterated Local Search, Evolutionary Computing, Simulated Annealing, Tabu Search.3. Describe the classic simulated annealing algorithm.4. Discuss control parameters and extensions of simulated annealing.Assignment:1. MetaHeuristic Network Project Web Site.2. Johnson et al., pages 865-870, and 991-888.3. Schultz et al. "On Minimizing Lmax for large-scale, job-shop scheduling problems.pdf", pages 4897-4900.Homework:1. Develop a heuristic for the following problem:Using the following precedence diagram and job data, determine the days on which each job should be performed and the minimum number of workers by trade type, in order to complete the project within four 8-hour days. Jobs must be completed on the day the job is started. Note there is no limit to the number of workers who can be assigned to a job and the time to perform the job is a linear function of the number of workers assigned. There are two skilled- trade types, type 1 and 2. Only personnel with the correct trade type can be assigned to a job with the corresponding trade type.Jobprocessingtime Trade type1 1212 713 924 1425 1616 827 928 719 16210 141See next page for precedence diagram.2. (Optional, not to be turned in) Develop program (C++, Java, VB, etc…) to code Johnson’s classic simulated annealing algorithm for the knapsack problem using your neighborhood from homework #8, problem 2. 3. (Optional, not to be turned in) Test your simulated annealing algorithm using the following instance of the knapsack problem:1234567 8109Capacity = 100Jobvalue(p)Weight(w)1 3 62 6 73 6 74 3 105 3 126 4 27 6 48 5 69 7 210 8 511 10 1012 12 1113 20 514 5 2015 15 1516 16 1617 8 918 18 1019 19 2520 20
View Full Document
Unlocking...