Reference no: EM132267913
Problem 1 - Johnson's rule
Consider the following instance of the two machine flow shop with the makespan as objective (i.e., an instance of F2||Cmax), which is a special case of J2||Cmax)
|
Jobs
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
|
p1j
|
3
|
6
|
4
|
3
|
4
|
2
|
7
|
5
|
5
|
6
|
12
|
|
p2j
|
4
|
5
|
5
|
2
|
3
|
3
|
6
|
6
|
4
|
7
|
2
|
A) Write a python program to construct a schedule implementing the Johnson's rule.
B) Map out the solution of this problem on a Gantt chart and calculate the makespan.
Problem 2 - Tabu search
Write a python program to apply Tabu search to the following instance of F3|prmu, pij = pj|ΣwjTj with the following 4 jobs.
|
Jobs
|
1
|
2
|
3
|
4
|
|
pj
|
9
|
9
|
12
|
3
|
|
dj
|
10
|
8
|
5
|
28
|
|
wi
|
14
|
12
|
1
|
12
|
Choose as the neighbourhood all schedules that can be obtained through adjacent pairwise interchanges.
Start out with sequence 3, 1, 4, 2 (the starting sequence needs to be a parameter of the algorithm).
Keep the length to the Tabu list equal to 2 (this needs to be a parameter of the algorithm).
Problem 3 - Timetabling
Edmund, Graham, Kath and Sanja are university lecturers attending a conference. During this conference they have to attend in total 7 meetings. The table below contains the meetings that each of the lecturers has to attend. The field in the table contains 1 if the lecturer has to attend the meeting.
|
Meetings
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
Edmund
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
|
Graham
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
|
Kath
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
|
Sanja
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
Write a python program to formulate this problem as a graph coloring problem to schedule all seven meetings in a single afternoon between 2pm and 6pm so that the four lecturer can be present at all the meetings that he/she has to attend.
Implement the largest degree first heuristic and another heuristic of your choice to solve this problem. Give a brief description of the two heuristics and critically compare them.