Even today’s most powerful computers need billion years of computation time to get optimum solutions on most of the combinatorial problems. For this reason, algorithms (heuristics) are being developed to find near optimum solutions to these problems. These algorithms do not claim to get an exact solution but a satisfying one.
In a manufacturing environment like cable cutting machines (CCM) park, there is a considerable potential to increase the efficiency. More than thousand orders may be processed at any time in environments with more than 10-15 machines. The efficiency of these systems may considerably increase if orders are scheduled to get shorter setup times. That is, if similar orders are scheduled one after another, the setup times become shorter and the efficiency increases.
At first look, this kind of problem seems to be easy. In fact it is, and an exact solution is available if the number of orders are 3-6. But what is disappointing is that it will take billions of years for most of the powerful computers to get to an exact solution if the number of orders is more than 100. This is a combinatorial problem in which the time needed to get to the exact solutions increases dramatically compared with the increase in the number of objects. So optimization heuristics are developed to get at least satisfying solutions.
The optimization heuristic:
There are lots of researches for optimization heuristics on combinatorial problems in the literature. We used the “Traveling Salesman” problem as the starting point. After a long time of research on the literature, we found a similarity between the “Traveling Salesman Problem” (TSP) and our “Setup Time Problem (STP). Both problems include objects to be scheduled. The “Traveling Salesman Problem” is to find the shortest path (schedule) of cities to visit for marketing; and the setup time problem is to find the good list (schedule) of orders to charge on a machine. Here a good list consists of orders with shortest setup times.
The Traveling Salesman Problem:
In TSP, there is a traveling salesman who has to travel a set of n cities and market his products. He has to travel through the shortest path, start from a specific city and return back to that city. By traveling on the shortest path, the salesman will save time and money. For a TSP with 150 cities it will take 10236 times the age of the universe for the most powerful computers in the world to find the exact solution.
The TSP and STP analogy:
A solution to TSP naturally generates the necessary solution for the problems that are analog to TSP. After TSP is solved, the issue becomes to make the analogy between TSP and the others. If we compare TSP and STP, the distances between the cities in TSP is analog to the setup times in STP; the cities in TSP are analog to orders in STP and the traveling salesman is analog to the machine in STP.
Our solution to the TSP:
Lets present the algorithm developed for the TSP. Below is the diagram we will base our presentation:
Figure 1 : Cities of the TSP.
The traveling salesman has to start from city A and return back. A logical way to do this may seem to start from A and jump to the nearest city and then jump to next nearest city and so on. This approach generates the following path :
Figure 2 : Implementation of the nearest city method.
If we observe the above path, we can easily see that the path segments G-H, H-I and I-A make the path too long if the above method is used:
We can visually generate a better path as follows:
Figure 3 : Visual elimination of the longest paths.
There are several sample problems in literature available for researches to compare their heuristics. We tested our heuristic with some of these samples and found that we can get similar results.
The implementation of TSP in WireManager:
The factors affecting the setup times:
The TSP – STP analogy brings some questions. The TSP problem domain is two-dimensional as demonstrated above. These dimensions are the x-axis and y-axis that define the coordinates of a city on the map. How will we represent an order? What kind of a map will we use? How many dimensions will it have? How will we handle these multi-dimensions?
In fact all of these questions are natural but mind confusing. We make the analogy in terms of distances between objects not in terms of coordinates. So what we have to deal with is the absolute distances between the cities and the orders. That is, if we develop an algorithm that optimizes the paths of cities with respect to distances not to coordinates, this algorithm can easily be used to optimize the schedules of orders, provided that there is a formula to give the distances between the orders.
So it is not important how the cities are represented in the universe. They could be represented in spherical coordinates. That time, spherical distances would be used to get an optimized path. And with orders, the number of factors affecting the setup times is not important. The only thing we need is the formula that calculates the distances (setup times) between the orders.
Traveling salesman versus cable cutting machine:
After building an analogy between TSP and STP, we found that we needed to schedule all orders as they were to be charged to one cable cutting machine (CCM), since there was one traveling salesman in the TSP we have originated. But there isn’ t one CCM in our target manufacturing environments (otherwise it would not be feasible to use WireManager). So we have to find a way to distribute the optimized list of orders we generated to multiple CCMs. What we do for multiple CCMs is to cut the optimized list of orders from suitable places and charge to the CCMs in order.