Article ID: | iaor20133926 |
Volume: | 206 |
Issue: | 1 |
Start Page Number: | 311 |
End Page Number: | 339 |
Publication Date: | Jul 2013 |
Journal: | Annals of Operations Research |
Authors: | Rabinowitz Gad, Pinto Gaby, Ben-Dov Yariv |
Keywords: | scheduling, programming: branch and bound |
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 and 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.