| Scheduling problems arise in diverse areas such as manufacturing, compiler design, databases, information dispersal, inventory management etc. Designing efficient solutions for these problems is critical for effective resource utilization and good system performance. Unfortunately, most of these optimization problems are NP-hard, and no polynomial time algorithms are known to find the optimal solutions. Heuristics that trade quality for tractability are therefore promising tools for coping with these problems.;My dissertation research is on the design of approximation algorithms for scheduling problems arising in many different contexts. In all these problems the cost of scheduling the activities is minimized when certain activities are scheduled "close" to each other. This may be because these activities overlap in the work needed to accomplish them and by scheduling them together we are able to minimize the total work incurred for the schedule. Some of these scheduling problems have application to minimizing the mean response time of clients in a client-server application that uses broadcast as a means of information dispersal, machining metal parts on a numerically controlled machining center, design of code optimization compilers for multiprocessor architecture, multi-item stock replenishment in inventory management etc.;This dissertation employs many novel mathematical tools and techniques to analyze the complexity of these scheduling problems and to design efficient as well as practical heuristics for effectively solving them. The concepts of "universal sequences", "golden ratio sequences" etc. are demonstrated to yield elegant yet simple approximation algorithms which in many cases are significantly better than the previously known approximation algorithms. These tools and techniques may be of independent interest due to their underlying mathematical sophistication and due to their potential applicability to many other problems. |
