| |
While there is a large number of algorithms for shortest route search in a graph, all of them have a major drawback: exponential growth of operation time as the number of graph nodes and the route length increases. For practical use in production scheduling, an algorithm is required that would allow for quick estimation of the actual distance to be traveled by an object when moving from one point to another. The calculation time should be short due to vast number of cases enumerated by the system during schedule optimization. Classic algorithms involve a graph with a huge number of nodes, so long as it is possible to move in any direction within a production site (as contrasted with a highway graph). Hence, calculation time required to generate routes will be unacceptably large (by the moment of scheduling completion, the schedule will become obsolete). Therefore, in order to solve this problem, we will not use graphs, but introduce the concept of obstacles, and create a "passability" matrix (using the spatial partitioning). The route will be generated in two steps: first, go in sequence through all obstacles that prevent achieving the goal, and then optimize the generated route by "cutting the corners". A final route will be worse (longer) than ideal routes (generated by classic algorithms) by 3–16%, but the time used for its generation will be 85–920 times shorter. Of course, the accuracy is rather poor, and in most cases such route is not suitable for practical use. However, routes themselves are not needed for production scheduling, it is important just to estimate roughly the route length and displacement time by selecting and comparing a large number of cases. If routes will still be required, the considered algorithm can be used to determinate start and end points, and then the generated route may be improved using the classic algorithm.
Keywords:production scheduling, logistics, shortest path search
|
LEGAL
INFORMATION:
