4. In the manufacturing of printed circuit boards, holes need to be drilled on t
ID: 3145949 • Letter: 4
Question
4. In the manufacturing of printed circuit boards, holes need to be drilled on the boards through which chips and other components are later wired. It is required that these holes be drilled as quickly as possible; hence, the problem of the most efficient order to drill the holes is a traveling salesperson problem. In the table below are the distances (in millimeters) between any pair of hole locations. Hence, minimum time equals finding the minimum total distance traveled between the hole locations. Determine the minimum time required to drill all the needed holes Hole locations 1 2 T3 45 6 78 1 - 138 157 16 1921 213-5 T714 2211 14 38 5 - 1517 17913 12 4157 158 7910 57 1417 8- 12T18 1811 616 2297 128 14 7191 139 188- 15 821 1412 10111415-Explanation / Answer
since distance is maximum to hole 8 from other hole .
Hence start with hole 8
suppose first hole is drill at location 8
from 8 minimum distance hole is number 4 which is 10 unit diastance
from 4 minimum distance hole is number 2 which is 7 unit diastance
from 2 minimum distance hole is number 3 which is 5 unit diastance
from 3 minimum distance hole is number 1 which is 8 unit diastance
from 1 minimum distance hole is number 5 which is 7 unit diastance
from 5 minimum distance hole is number 6 which is 12 unit diastance
from 6 to hole 7 which is 8 unit diastance
thus total distance covered = 10+7+5+8+7+12+8=57
total minimum time required is = 57 unit
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.