A New Perspective on Machine Scheduling

Lee 9610229 该补助金为解决一类新的调度问题的算法开发提供资金。 与经典的调度问题，一台机器，一个工作模式，机器在任何时候都可用，这类新的问题包含一个工作，多台机器或多个工作，一台机器的模式，除了机器的可用性约束。 将开发基于大规模整数规划公式的最佳算法。 一个六节点的硅图形电源挑战桌面服务器，在很大程度上购买了从国家科学基金会的赠款，将被用作计算平台，以解决这些问题。还将开发基于动态规划的方法，可以有效地解决某些类别的限制性问题。 将开发和测试局部搜索技术，特别是禁忌搜索和遗传算法的有效性和效率。 还将进行近似方法的实证工作和理论误差界分析。 这项工作的主要目标是扩展目前的调度理论，包括新的模型，工业问题的动机，并有更大的应用潜力。 如果成功的话，这项研究的结果将拓宽机器调度领域，并引起更深入的了解到许多更现实的调度问题的结构。这项研究将导致新的计算发展的优化方法来解决复杂的调度问题。 在学术上，它不仅将有助于新的和有趣的结果在调度领域，但也有助于整数规划问题的计算工具和方法。本文工作的实际应用将为解决制造业和服务业中的实际调度问题提供有效的方法，最终使管理者能够实现节约成本、缩短交货期、提高质量的目标。 和客户满意度。

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.