zbMATH — the first resource for mathematics

A mathematical programming formulation for the multiprocessor scheduling problem with communication delays. (English) Zbl 1049.68026
Mladenović, Nenad (ed.) et al., 30th Yugoslavian symposium on operations research, SYM-OP-IS 2003. Proceedings, Herceg Novi, Yugoslavia, September 30–October 3, 2003. Beograd: Matematički Institut SANU (ISBN 86-80593-33-8). 331-334 (2003).
A mathematical programming formulation of the Multiprocessor Scheduling Problem with Communication Delays (MSPCD) is given. The problem consists of scheduling dependent tasks with communication delays onto homogeneous, arbitrarily connected multiprocessor architecture. The extension to the heterogeneous case is briefly discussed. The proposed mathematical formulation of MSPCD belongs to the class of mixed-integer linear programs: it contains variables of 0-1 type as well as continuous variables. Although containing a large number of variables, this formulation may be useful for determining the lower bounds when developing exact solution methods for the multiprocessor scheduling problem with communication delays.
For the entire collection see [Zbl 1031.90002].

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C05 Linear programming