M 353 Modern Computational Methods for Operational”Research”and”Logistics
M353 – Modern Heuristic Methods Coursework
Dr Banafsheh Khosravi
Due Date: Wednesday 27th January 2016 by 4pm
This coursework is worth 40% of the total unit mark. This is an individual assignment.
Group work and/or copying of work or reports are not permitted and will be dealt with
under the University rules on plagiarism.
What you need to submit
Please submit the following files via the coursework submission link on unit MOODLE page
and CAM office:
1. Soft copy of your report on Moodle and hard copy to CAM office. Your report
should be no longer than the specified word limits for each part. The font size
used must be 10 or greater.
2. Your Excel files only on Moodle.
Problem
A publication company is interested to optimise the publication process and
minimise general lead time of publication of books and journals. There are
currently 10 different tasks which need to be scheduled for 20 types of
publications which have certain due dates agreed with the customers. So
company is interested in minimizing the total tardiness of these tasks. Each
publication type is processed through a specific task with a certain time. All
publications are processed with the same sequence of tasks. Each publication
can be processed only under one specific task at a time, and each specific
task is assigned to only one publication at a time. Processing a task is not
preemptable and the processing times of the tasks are given both in Table 1 and in the
file “Coursework data 2015-16.xls” on MOODLE.
Company’s objective is to determine a schedule of 10 required tasks for 20 types of
publications so that the total tardiness is minimised.
1. Formulate and describe in detail the fitness function and decision variables of
the scheduling problem. Provide any reference you have used. [Maximum 500
words excluding references]
[10 marks]
2. Consider the data given in both Table 1 and in the file “Coursework data 2015-
16.xls” on MOODLE. The data shows the processing times of 20 publications with
10 specific tasks. Set up a model of the problem using Excel spreadsheets and
describe it in detail. A screenshot of your Excel model should accompany your
description. Marks will be given for the layout, clarity and presentation of the
model as well as its content and accuracy. [Maximum 1000 words]
[10 marks]
M 353 Modern Computational Methods for Operational”Research”and”Logistics
3. Set up the optimisation model on Evolver and explain clearly the implementation of
the fitness function, decision variables and constraints. Describe in detail the initial
feasible solution and its fitness value.
Choose Genetic Algorithm (GA) as the optimisation technique. Indicate which
solving method you have used to solve the problem. Solve the problem by
using the population size of 60 and experimenting with the following crossover
and mutation rates. Find the combination with the best minimum total tardiness:
i. Crossover rate = 0.9, mutation rate = 0.01.
ii. Crossover rate = 0.8, mutation rate = 0.03.
iii. Crossover rate = 0.6, mutation rate = 0.25.
iv. Crossover rate = 0.4, mutation rate = 0.005.
v. Any other combinations that you think will produce a good solution.
The stopping criterion for all the experiments should be set to 30000 generations.
Describe the optimisation model and the experiments conducted. For each
combination, provide a detailed description of the best solution including: sequence
of jobs, total tardiness, and the computation time required to generate the best
solution. [Maximum 1500 words]
[15 marks]
4. Analyse your results in question 3 and discuss the effect of different crossover and
mutation rates on the quality of the best solutions for each combination. Provide a
graphical illustration to compare the best solutions found for different crossover
and mutation rate combinations in question 3. [Maximum 300 words]
[15 marks]
5. Solve the problem by choosing OptQuest as the optimisation method. Calculate
the % deviation of the best minimum total tardiness value found for each
combination in question 3 from the OptQuest solution. Discuss how your best
solution compares to the OptQuest solution and how you could possibly improve
your GA best solution. [Maximum 300 words]
[20 marks]
6. Implement Simulated Annealing (SA) to solve this problem and explain in
detail the SA pseudo-code. Provide an example of the initial feasible solution,
neighbourhood structure, initial temperature, and cooling schedule strategy.
Run manually SA for 4 iterations to solve the problem. For each iteration,
describe in detail the search steps and the values of the parameters used.
Provide the best total tardiness found after 4 iterations. [Maximum 1500
words excluding references]
[30 marks]
M 353 Modern Computational Methods for Operational”Research”and”Logistics
Table 1. Processing times of 20 publications with 10 specific tasks
Pub
1
Pub
2
Pub
3
Pub
4
Pub
5
Pub
6
Pub
7
Pub
8
Pub
9
Pub
10
Pub
11
Pub
12
Pub
13
Pub
14
Pub
15
Pub
16
Pub
17
Pub
18
Pub
19
Pub
20
Task1 80 13 64 77 17 78 82 4 72 93 68 25 67 80 43 93 21 33 14 30
Task2 59 83 85 85 70 35 2 76 46 72 69 46 3 57 71 77 33 49 59 82
Task3 59 70 76 10 65 19 77 86 21 75 96 3 50 57 66 84 98 55 70 32
Task4 31 64 11 9 32 58 98 95 25 4 45 60 87 31 1 96 22 95 73 77
Task5 30 88 14 22 93 48 10 7 14 91 5 43 30 79 39 34 77 81 11 10
Task6 53 19 99 62 88 93 34 72 42 65 39 79 9 26 72 29 36 48 57 95
Task7 93 79 88 77 94 39 74 46 17 30 62 77 43 98 48 14 45 25 98 30
Task8 90 92 35 13 75 55 80 67 3 93 54 67 25 77 38 98 96 20 15 36
Task9 65 97 27 25 61 24 97 61 75 92 73 21 29 3 96 51 26 44 56 31
Task10 64 38 44 46 66 31 48 27 82 51 90 63 85 36 69 67 81 18 81 72
Due$
Date 870 1520 980 750 630 1210 1870 1270 1410 830 1360 1740 1250 1650 2040 950 520 1020 1550 730