This article is cited in 43 papers

Multi-Machine and Multi-Stage Scheduling Environments

Scheduling with multiple servers

F. Werner^a, S. A. Kravchenko<sup>b

a</sup> Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik
^b 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.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 12.01.2010

 English version: Automation and Remote Control, 2010, 71:10, 2109–2121

Bibliographic databases:

• 
• 
• 
•