ON SOME GEOMETRIC METHODS IN SCHEDULING THEORY - A SURVEY

Suppose we are given a closed walk consisting of n steps in m-dimensional space, each step having at most unit length (in a certain norm s). We wish to include the walk into a given region of the space by reordering its steps. It turns out that our ability to solve this problem in polynomial time for certain regions of the space (such as the right triangle or hexagon in the plane, the ball in R(m), etc.), enables us to construct approximation algorithms with good performance guarantees and polynomial running time for scheduling flow shops, job shops and other problems of the type, known to be NP-hard. Some other geometric methods are also to be spoken of subject to their application to scheduling problems.