An approximation algorithm for parallel machine scheduling with a common server

Guoqing Wang and T C Edwin Cheng ()
Additional contact information
Guoqing Wang: Jinan University
T C Edwin Cheng: The Hong Kong Polytechnic University

Journal of the Operational Research Society, 2001, vol. 52, issue 2, 234-237

Abstract: Abstract 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.

Keywords: parallel machine scheduling; approximation algorithm; worst-case analysis (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601074 Abstract (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:pal:jorsoc:v:52:y:2001:i:2:d:10.1057_palgrave.jors.2601074

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601074

Access Statistics for this article

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

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().