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

Guo Sheng Liu, Jin Jin Li, Hai Dong Yang, George Q. Huang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1554-1570
Number of pages17
JournalJournal of the Operational Research Society
Volume70
Issue number9
DOIs
Publication statusPublished - 2 Sept 2019
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Fingerprint

Dive into the research topics of 'Approximate and branch-and-bound algorithms for the parallel machine scheduling problem with a single server'. Together they form a unique fingerprint.

Cite this