An approximation algorithm for parallel machine scheduling with a common server

Guoqing Wang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)


In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.
Original languageEnglish
Pages (from-to)234-237
Number of pages4
JournalJournal of the Operational Research Society
Issue number2
Publication statusPublished - 1 Jan 2001


  • Approximation algorithm
  • Parallel machine scheduling
  • Worst-case analysis

ASJC Scopus subject areas

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


Dive into the research topics of 'An approximation algorithm for parallel machine scheduling with a common server'. Together they form a unique fingerprint.

Cite this