Parallel machine scheduling with a common server Academic Article

abstract

• This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness. The results provide a mapping of the computational complexity of these problems. 2000 Elsevier Science B.V.

authors

• Sriskandarajah, Chelliah

published proceedings

• Discrete Applied Mathematics

author list (cited authors)

• Hall, N. G., Potts, C. N., & Sriskandarajah, C.

citation count

• 101

complete list of authors

• Hall, Nicholas G||Potts, Chris N||Sriskandarajah, Chelliah

publication date

• June 2000

publisher

• Elsevier  Publisher

published in

• DISCRETE APPLIED MATHEMATICS  Journal

Digital Object Identifier (DOI)

• 10.1016/s0166-218x(99)00206-1

start page

• 223

end page

• 243

volume

• 102

issue

• 3

URL

• http://dx.doi.org/10.1016/s0166-218x(99)00206-1