Approximate and branch-and-bound algorithms for the parallel machine scheduling problem with a single server

摘要

In this paper, we consider the scheduling problem of minimising the total weighted job completion time when a set of jobs must be processed on m parallel machines with a single server. This problem has various applications to networks, manufacturing, logistics, etc. The shortest weighted processing time (SWPT) sequencing by Hasani et al. is (3 - 2/m)-approxi-mate for general problem cases and (2 - 1 /m)-approximate for problems subjected to regular job restrictions. At present, these findings are the best-known results available for the worst-case analyses. Furthermore, dominance properties are discussed and several rules for improving a given schedule are given. To solve the problem, a branch-and-bound (B&B) algorithm is developed by integrating SWPT sequencing, a new lower bound, and dominance properties. A number of numerical experiments are illustrated to validate the performance of our algorithms and identify implications for the considered problem.