Lee 9610229 This grant provides funding for the development of algorithms to solve a new class of scheduling problems. In contrast to classical scheduling problems with a one-machine-one-job pattern where machines are available at all times, this new class of problems contains jobs with one-job-on-multiple-machine or multiple-job-on-one-machine patterns in addition to machine availability constraints. Optimal algorithms based on a large-scale integer programming formulation will be developed. A six node Silicon Graphics Power Challenge Deskside server, purchased in large part with a grant from the National Science Foundation, will be used as the computational platform to address these problems. Dynamic programming based methods that can efficiently solve certain classes of restricted problems will also be developed. Local search techniques, especially tabu search and genetic algorithms, will be developed and tested for effectiveness and efficiency. Empirical work and theoretical error bound analysis for the approximation methods will also be conducted. The primary goal of this work is to extend the current scheduling theories to include new models that are motivated by industrial problems and have greater potential for application. If successful, the results of this research will broaden the field of machine scheduling and elicit deeper insights into the structure of many more realistic scheduling problems. The research will lead to new computational developments in optimization methods for solving complex scheduling problems. Academically, it will not only contribute new and interesting results in the scheduling field but also contribute to the computational tools and methodologies for integer programming problems. Practical applications of the proposed work will lead to effective methods in solving real-life scheduling problems in the manufacturing and service industries, and will eventually enable managers to achieve the goal of cost saving, lead-time reduction, quality improve ment and customer satisfaction.
