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

Abstract

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$)-approximate 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.

Keywords:

• Parallel machine scheduling
• single server
• worst-case analysis
• branch and bound
• SWPT

Acknowledgements

The authors would like to thank anonymous reviewers for their comments and useful suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was partially supported by the National Natural Science Foundation of China (71401044, 51475096, U1501248) and by the New Pearl River Star Program of Guangzhou City (201610010035).