Mixed Integer Programming Approaches to Production Planning Problems

尽管运筹学的应用帮助制造企业削减了成本，提高了效率，但生产和供应链规划中的根本问题仍然难以解决。这些问题涉及外部需求、内部物料清单结构、生产能力、持有成本和安装时间等因素的相互作用。大多数实施制造资源计划(MRP II)及相关方法的系统只能解决这些问题的粗略近似。由此产生的计划并不像可能的那样高效和具有成本效益，而且它们往往也没有准确地考虑到产能等基本限制。该项目将开发基本的混合整数规划(MIP)方法来解决这些问题。该项目旨在开发基本成果，以加强这些问题的MIP公式，从而改进为解决这些问题而设计的分支-切割算法。此外，该项目将把这些纳入基于MIP的启发式算法，以优化在大型实际问题上的性能。所开发的理论结果和启发式方法不仅适用于生产计划问题的大类，而且还适用于包括运输和分配以及生产决策的供应链计划问题。此外，该项目的成果将被纳入威斯康星大学的课程。这将使学生接触到使用MIP方法解决这类问题的可能性和挑战。这项研究将使新类型的工业问题得到有效解决。本项目目标的成功完成将使我们有可能考虑在制造和供应链企业的许多实际情况的计划系统中实施这些想法。它还将有助于一般工业工程/运筹学研究方法，特别是解决在各种工程应用中出现的混合整数规划领域的问题。最后，该项目将增加威斯康星大学课程的广度和深度，并将有助于研究助理的专业发展，研究助理将通过该项目得到支持。

While the application of operations research has aided manufacturing companies to cut costs and improve efficiency, fundamental problems in production and supply chain planning remain challenging to solve. These problems involve the interaction of factors such as external demands, internal bill-of-material structure, production capacities, holding costs, and setup times. Most systems implementing Manufacturing Resources Planning (MRP II) and related methods solve only rough approximations of these problems. The resulting plans are not as efficient and cost-effective as may be possible, and they also often do not accurately account for basic restrictions such as production capacity. This project will develop basic mixed integer programming (MIP) methods that can solve such problems. This project aims to develop fundamental results to strengthen the MIP formulations of these problems so as to improve branch-and-cut algorithms designed to solve them. In addition, the project will incorporate these into MIP-based heuristics in order to optimize the performance on large practical problems. The theoretical results and heuristics developed will apply not only to broad families of production planning problems, but also to supply chain planning problems incorporating transportation and distribution as well as production decisions. Moreover, the results of this project will be incorporated into classes in the University of Wisconsin curriculum. This will expose students to the possibilities of, and challenges involved in, using MIP methods to solve these kinds of problems. This research will allow new kinds of industrial problems to be solved efficiently. The successful completion of the goals of this project will make it possible to consider implementing these ideas in planning systems for many practical situations in manufacturing and supply chain enterprises. It will also contribute to general industrial engineering/operations research methodology, particularly to solving problems in the field of mixed integer programming that occur in a wide variety of engineering applications. Finally, this project will add breadth and depth to the curriculum of the University of Wisconsin, and it will contribute to the professional development of the research assistant who will be supported through it.