Article ID: | iaor20012325 |
Country: | United Kingdom |
Volume: | 6 |
Issue: | 4 |
Start Page Number: | 345 |
End Page Number: | 363 |
Publication Date: | Jul 1999 |
Journal: | International Transactions in Operational Research |
Authors: | Drozdowski Maciej, Dell'Olmo Paolo, Baewicz Jacek |
Keywords: | computers |
In this paper, we analyze the problem of deterministic scheduling of applications (programs) in a client-server environment. We assume that the client reads data from the server, processes it, and stores the results on the server. This paradigm can also model a wider class of parallel applications. The goal is to find the shortest schedule. It is shown that the general problem is computationally hard. However, any list scheduling algorithm delivers solutions not worse than twice the optimum when tasks are preallocated, and three times the optimum when tasks are not preallocated. A polynomially solvable case is also presented.