A Customized Branch and Bound Algorithm to Solve the Resource-Sharing and Scheduling Problem (RSSP)

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.