Scheduling with multiple servers |
| |
Authors: | F Werner S A Kravchenko |
| |
Affiliation: | 1.Otto-von-Guericke-Universit?t,Magdeburg,Germany;2.United Institute of Informatics Problems,Belarussian National Academy of Sciences,Minsk,Belarus |
| |
Abstract: | In this paper, we consider the problem of scheduling a set of jobs on a set of identical parallel machines. Before the processing
of a job can start, a setup is required which has to be performed by a given set of servers. We consider the complexity of
such problems for the minimization of the makespan. For the problem with equal processing times and equal setup times we give
a polynomial algorithm. For the problem with unit setup times, m machines and m − 1 servers, we give a pseudopolynomial algorithm. However, the problem with fixed number of machines and servers in the
case of minimizing maximum lateness is proven to be unary NP-hard. In addition, recent algorithms for some parallel machine scheduling problems with constant precessing times are generalized
to the corresponding server problems for the case of constant setup times. Moreover, we perform a worst case analysis of two
list scheduling algorithms for makespan minimization. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|