THE SCHEDULING PROBLEM WHERE MULTIPLE MACHINES COMPETE FOR A COMMON LOCAL BUFFER

The problem of scheduling jobshops with restricted buffer space between machines to hold the work-in-process has received scant attention in the scheduling literature. One interesting aspect of this problem is to understand how jobs arriving simultaneously from different machines would compete for common limited buffer space. This paper considers this issue by studying a two-stage flowshop environment with multiple machines at the first stage, a single machine at the second stage and a finite-size buffer area between the two stages. Jobs are processed at a (pre-assigned) machine at the first stage and then at the machine at the second stage. We model the problem of minimizing the sum of weighted completion times of a given set of jobs as a mixed integer linear program. Two lower bounds to the problem are then developed using a Lagrangian and a combined Lagrangian-surrogate relaxation respectively. Heuristics for the problem based on priority rules are proposed and analysed computationally. We see that the multipliers from the relaxations carry sufficient information to be used to build successful priority rules for this problem.