Collaborative Research: Scheduling Multiple Product Types on Parallel Resources

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.