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 and George Q. Huang

Journal of the Operational Research Society, 2019, vol. 70, issue 9, 1554-1570

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.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2018.1500976 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:70:y:2019:i:9:p:1554-1570

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2018.1500976

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().