Bilkent University Principles of Engineering Management Course (IE 400) Project Fall 2019-2020
In the process of manufacturing electronic circuit boards, holes have to be drilled in prints of rectangular shape; these holes have to be pairwise connected by conductive material. The head of the drilling equipment can only be moved horizontally and vertically from one hole to another (moves according to the shortest Manhattan distance between two holes). Usually, a large amount of holes has to be drilled in a board. Since moving the head of drill is a time consuming operation, the total distance that the head has to be moved should be minimized. Moreover, after the drilling process is completed, the head must return to its starting position. Suppose that there are some blocks on the circuit board, such that some paths between points may be closed due to the position of these blocks. In this project, you are given the Cartesian coordinates of 50 points that must be drilled and 20 rectangular blocks (data.xls) and drilling machine is not allowed to pass through these blocks. For instance, in the figure below; The drill cannot move from A to C via the path marked with X. The drill can move from A to D. The drill can move from A to B etc.
