Abstract
An admissible multiprocessor preemptive scheduling problem is solved for the given execution intervals. In addition, a number of generalizations are considered—interprocessor communications are arbitrary and may vary in time; costs for processing interruptions and switches from one processor to another are taken into account; and besides the processors, additional resources are used. Algorithms based on reducing the original problem to finding paths of a specific length in a graph, a flow problem, and an integer system of linear restrictions are developed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. S. Tanaev, V. S. Gordon, and Ya. M. Shafranskii, Scheduling Theory. One-Stage Systems (Nauka, Moscow, 1984) [in Russian].
T. Gonzales and S. Sahni, “Preemptive scheduling of uniform processor systems,” J. Assoc. Comput. Machin. 25, 92–101 (1978).
A. Federgruen and H. Groenevel, “Preemptive scheduling of uniform machines by ordinary network flow technique,” Manage. Sci. 32, 341–349 (1986).
P. Brucker, Scheduling Algorithms (Springer, Heidelberg, 2007).
D. S. Guz and M. G. Furugyan, “Computation scheduling in multiprocessor real-time automatic control systems with constrained processor memory,” Autom. Remote Control 66, 295 (2005).
B. V. Grechuk and M. G. Furugyan, “Optimal preemptive scheduling in multiprocessor systems with incomplete communication graph,” Cybern. Syst. Anal. 41, 397–402 (2005).
E. O. Kosorukov and M. G. Furugyan, “Some algorithms for resource allocation in multiprocessor systems,” Moscow Univ. Comput. Math. Cybernet. 33, 202 (2009).
M. G. Furugyan, “Computation planning in multiprocessor real time automated control systems with an additional resource,” Autom. Remote Control 76, 487 (2015).
M. G. Furugyan, “Making schedules in multiprocessing systems with several additional resources,” J. Comput. Syst. Sci. Int. 56, 227 (2017).
M. G. Furugyan, “Computation scheduling in multiprocessor systems with several types of additional resources and arbitrary processors,” Moscow Univ. Comput. Math. Cybernet. 41, 145 (2017).
A. A. Mironov and V. I. Tsurkov, “Hereditarily minimax matrices in models of transportation type,” J. Comput. Syst. Sci. Int. 37, 927 (1998).
A. A. Mironov and V. I. Tsurkov, “Minimax under nonlinear transportation constraints,” Dokl. Math. 64, 351 (2001).
A. A. Mironov and V. I. Tsurkov, “Transportation problems with minimax criteria,” Dokl. Math. 53, 119 (1996).
A. A. Mironov and V. I. Tsurkov, “Minimax in transportation models with integral constraints: I,” J. Comput. Syst. Sci. Int. 42, 562 (2003).
A. A. Mironov, V. V. Fedorchuk, and V. I. Tsurkov, “Minimax in transportation models with integral constraints: II,” J. Comput. Syst. Sci. Int. 44, 732 (2005).
A. A. Mironov and V. I. Tsurkov, “Network models with fixed parameters at the communication nodes. 1,” J. Comput. Syst. Sci. Int. 32 (6), 1–11 (1994).
A. A. Mironov and V. I. Tsurkov, “Network models with fixed parameters at the communication nodes. 2,” J. Comput. Syst. Sci. Int. 33 (3), 107–116 (1995).
Yu. E. Malashenko and N. M. Novikova, “Analysis of multiuser network systems taking into account uncertainty,” J. Comput. Syst. Sci. Int. 37, 292 (1998).
Yu. E. Malashenko and N. M. Novikova, “The analysis of multiuser network systems under uncertainty: 7. The problem of standard vulnerability analysis of a multicommodity flow network,” J. Comput. Syst. Sci. Int. 38, 589 (1999).
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (The MIT Press, Cambridge, MA, 2009).
B. Korte and J. Vygen, Combinatorial Optimization. Theory and Algorithms (Springer, Berlin, Heidelberg, 2006).
D. T. Fillips and A. Garcia-Diaz, Fundamentals of Network Analysis (Prentice-Hall, Englewood Cliffs, NJ, 1981).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © M.G. Furugyan, 2018, published in Izvestiya Akademii Nauk, Teoriya i Sistemy Upravleniya, 2018, No. 2, pp. 52–59.
Rights and permissions
About this article
Cite this article
Furugyan, M.G. Scheduling in Multiprocessor Systems with Additional Restrictions. J. Comput. Syst. Sci. Int. 57, 222–229 (2018). https://doi.org/10.1134/S1064230718020077
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064230718020077