Scheduling with multiple servers

Scheduling with multiple servers

0.00 Avg rating0 Votes
Article ID: iaor20107557
Volume: 71
Issue: 10
Start Page Number: 2109
End Page Number: 2121
Publication Date: Oct 2010
Journal: Automation and Remote Control
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.