Collaborative Research: Scheduling Multiple Product Types on Parallel Resources

这一合作研究拨款为开发一种新的调度模型提供了资金，该模型通过假设一个作业由可以同时并行处理的多个操作组成，从而推广了各种经典调度模型。有许多并行的机器，但每台机器只能生产特定的产品类型子集。如果在一台机器上连续加工两种不同类型的产品，则可能需要进行设置。在生产工厂收到的订单通常要求特定数量的各种不同类型的产品，期望所有订购的项目都在相同的到期日交货。这个项目的目标有三个方面。第一个目标是研究这类问题的理论性质。这包括为这些问题的更容易的版本搜索多项式时间算法，为更一般的版本建立NP难度结果，以及建立支配结果或消除标准。第二个目标涉及启发式算法的开发和评估。启发式方法将基于分解、局部搜索以及混合方法。第三个目标是与几家表示对该项目感兴趣的公司合作，开发和评估启发式方法。这些公司将提供真实数据来验证启发式算法的性能。这些公司包括与大型制造公司有正在进行的项目的软件开发公司以及大型制造公司本身。这项研究的结果预计将导致许多制造环境中生产调度的改善，从而为相关公司带来更低的成本和更高的盈利能力。

This collaborative research grant provides funding for the development of a new scheduling model that generalizes various classical scheduling models by assuming that a job consists of multiple operations which may be processed simultaneously in parallel. There are a number of machines in parallel but each machine is only capable of producing a specific subset of the product types. If two products of different types are processed on a machine one after another, then a setup may be required. An order coming in at a production facility usually asks for specific quantities of various different product types with the expectation that all the items ordered are delivered at the same due date. The objectives of this project are three-fold. The first goal is to study the theoretical properties of this class of problems. This includes searching for polynomial time algorithms for the easier versions of these problems, establishing NP-hardness results for the more general versions, and establishing dominance results or elimination criteria. A second goal involves the development and evaluation of heuristics. The heuristics will be based on decomposition, local search, as well as hybrid approaches. A third goal is to collaborate with several companies that have expressed interest in the project regarding the development and evaluation of heuristics. These companies will provide real-life data to validate the performance of the heuristics. These companies include software development companies that have ongoing projects with larger manufacturing companies as well as large manufacturing companies themselves.The results of this research are expected to lead to improvements in production scheduling in a number of manufacturing settings, leading to lower cost and higher profitability for the companies involved.