Formulating and Solving a Multi-Mode Resource-Collaboration and Constrained Scheduling Problem (MRCCSP)

Gaby Pinto  - Department of Industrial Engineering and Management, Jerusalem Collage of Engineering

Abstract:

The main motivation of this study is to provide for the first time a formulation and solution for a class of production scheduling problems (as in cluster tools) characterized mainly by resource collaboration to perform an operation, while allowing batches and considering alternative production methods. We develop a formulation for the new problem and term it a multiple mode per operation, resource collaboration, and constrained scheduling problem (MRCCSP). Some of the important new characteristics we consider are: multiple products (families); Multiple orders (jobs) per family; Precedence restrictions among the operations that constitute a job; Alternative modes for the performance of an operation (each of which needs a set of collaborating resources) may be defined; Complementary and exclusive restrictions between operation-modes; Batch production is allowed; and setup times may depend on sequence and batch-size. The objective of the MRCCSP is to minimize makespan. We formulate the MRCCSP as a mixed integer linear programming model, and acknowledging the considerable size of the monolithic formulation required, we prescribe a specific method to achieve size reduction. Finally, a customized branch and bound algorithm for optimally solving this problem is proposed and examined experimentally.