Optimizing Scheduling for Academic Meetings: Minimizing Makespan and Managing Breaks
An analysis of optimizing scheduling for academic meetings, focusing on minimizing makespan and efficiently managing breaks to enhance productivity.
Ryan Scott
Contributor
4.2
30
4 months ago
Preview (3 of 8)
Sign in to access the full document!
Optimizing Scheduling for Academic Meetings: Minimizing Makespan and
Managing Breaks
1. My colleague Dr Wu wishes to visit all the attractions in the Park of Assessment
Three. (For ease of reference, direct distances within the park are given below.)
road EL EP EG LW LT LP GP GW TW TP PW
length (m) 170 350 240 530 290 330 240 600 250 220 240
Use the nearest-neighbour method to find such routes. Which is the shortest? Are any
of them Hamiltonian cycles?
Given Data:
Road lengths (in meters) between various locations in the Park of Assessment Three:
Nearest-Neighbor Method:
The nearest-neighbor method involves starting at a particular point (e.g., Entrance (EL)) and
selecting the closest unvisited point at each step until all points are visited. Steps for Nearest-
Neighbour Method:
1. Start at EL (Entrance)
2. Find the nearest point:
The distances from EL to other locations are:
o EL to EP = 170
o EL to EG = 350
o EL to LW = 240
o EL to LT = 530
o EL to LP = 290
o EL to GP = 330
o EL to GW = 240
o EL to TW = 600
o EL to TP = 220
o EL to PW = 240
The closest point is EP (170 meters).
3. From EP, find the nearest point to EP that has not been visited:
The remaining points are:
o EP to EG = 240
o EP to LW = 530
o EP to LT = 290
o EP to LP = 330
o EP to GP = 240
o EP to GW = 600
o EP to TW = 250
o EP to TP = 220
o EP to PW = 240
The closest point is EG (240 meters).
4. From EG, find the nearest point:
The remaining points are:
o EG to LW = 530
Managing Breaks
1. My colleague Dr Wu wishes to visit all the attractions in the Park of Assessment
Three. (For ease of reference, direct distances within the park are given below.)
road EL EP EG LW LT LP GP GW TW TP PW
length (m) 170 350 240 530 290 330 240 600 250 220 240
Use the nearest-neighbour method to find such routes. Which is the shortest? Are any
of them Hamiltonian cycles?
Given Data:
Road lengths (in meters) between various locations in the Park of Assessment Three:
Nearest-Neighbor Method:
The nearest-neighbor method involves starting at a particular point (e.g., Entrance (EL)) and
selecting the closest unvisited point at each step until all points are visited. Steps for Nearest-
Neighbour Method:
1. Start at EL (Entrance)
2. Find the nearest point:
The distances from EL to other locations are:
o EL to EP = 170
o EL to EG = 350
o EL to LW = 240
o EL to LT = 530
o EL to LP = 290
o EL to GP = 330
o EL to GW = 240
o EL to TW = 600
o EL to TP = 220
o EL to PW = 240
The closest point is EP (170 meters).
3. From EP, find the nearest point to EP that has not been visited:
The remaining points are:
o EP to EG = 240
o EP to LW = 530
o EP to LT = 290
o EP to LP = 330
o EP to GP = 240
o EP to GW = 600
o EP to TW = 250
o EP to TP = 220
o EP to PW = 240
The closest point is EG (240 meters).
4. From EG, find the nearest point:
The remaining points are:
o EG to LW = 530
o EG to LT = 290
o EG to LP = 330
o EG to GP = 240
o EG to GW = 600
o EG to TW = 250
o EG to TP = 220
o EG to PW = 240
The closest point is LP (240 meters).
5. From LP, find the nearest point:
The remaining points are:
o LP to LW = 530
o LP to LT = 290
o LP to GP = 330
o LP to GW = 600
o LP to TW = 250
o LP to TP = 220
o LP to PW = 240
The closest point is PW (240 meters).
6. From PW, find the nearest point:
The remaining points are:
o PW to LW = 530
o PW to LT = 290
o PW to GP = 330
o PW to GW = 600
o PW to TW = 250
o PW to TP = 220
The closest point is TP (220 meters).
7. From TP, find the nearest point:
The remaining points are:
o TP to LW = 530
o TP to LT = 290
o TP to GP = 330
o TP to GW = 600
The closest point is GW (250 meters).
8. From GW, find the nearest point:
The remaining points are:
o GW to LW = 530
o GW to LT = 290
o GW to GP = 330
The closest point is LT (290 meters).
9. From LT, find the nearest point:
The remaining point is LW (530 meters).
10. Route Summary:
The nearest-neighbour path is:
EL → EP → EG → LP → PW → TP → GW → LT → LW
11. Hamiltonian Cycle:
A Hamiltonian cycle requires visiting all vertices and returning to the starting point. In this case, the
route does not return to the starting point (EL), so this is not a Hamiltonian cycle.
o EG to LP = 330
o EG to GP = 240
o EG to GW = 600
o EG to TW = 250
o EG to TP = 220
o EG to PW = 240
The closest point is LP (240 meters).
5. From LP, find the nearest point:
The remaining points are:
o LP to LW = 530
o LP to LT = 290
o LP to GP = 330
o LP to GW = 600
o LP to TW = 250
o LP to TP = 220
o LP to PW = 240
The closest point is PW (240 meters).
6. From PW, find the nearest point:
The remaining points are:
o PW to LW = 530
o PW to LT = 290
o PW to GP = 330
o PW to GW = 600
o PW to TW = 250
o PW to TP = 220
The closest point is TP (220 meters).
7. From TP, find the nearest point:
The remaining points are:
o TP to LW = 530
o TP to LT = 290
o TP to GP = 330
o TP to GW = 600
The closest point is GW (250 meters).
8. From GW, find the nearest point:
The remaining points are:
o GW to LW = 530
o GW to LT = 290
o GW to GP = 330
The closest point is LT (290 meters).
9. From LT, find the nearest point:
The remaining point is LW (530 meters).
10. Route Summary:
The nearest-neighbour path is:
EL → EP → EG → LP → PW → TP → GW → LT → LW
11. Hamiltonian Cycle:
A Hamiltonian cycle requires visiting all vertices and returning to the starting point. In this case, the
route does not return to the starting point (EL), so this is not a Hamiltonian cycle.
Preview Mode
Sign in to access the full document!
100%
Study Now!
XY-Copilot AI
Unlimited Access
Secure Payment
Instant Access
24/7 Support
Document Chat
Document Details
Subject
Operations Management