Search

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.

We propose a customized branch and bound (B&B) algorithm (which we refer to as B&B#2) to solve the resource-sharing and scheduling problem (RSSP). The RSSP has previously been formulated as a continuous-time mixed-integer linear programming model and was optimally solved using a branch-and-bound (B&B) algorithm (which we refer to as B&B#1). The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of resources needed. An operation may share different resources simultaneously. The problem is to select a single mode for each operation (i.e., the allocation decision) and accordingly to schedule the resources (i.e., the sequencing decision) while minimizing the makespan time. The B&B algorithm we propose is based on a minimal branching process at the allocation decision level. We compare the runtime of B&B#2 algorithm versus B&B#1 algorithm on a set of problem instances. The results showed that the average runtime of the B&B#2 algorithm was the smallest.