VOLTERRA-TYPE INTEGRAL EQUATION WITH TIME-VARYING KERNEL FOR MODELING HISTORICAL RESOURCE DECISIONS IN DYNAMIC TASK SCHEDULING
- Authors
-
-
Sharipov Elbek Jumanazarovich
Department of Software Engineering Tashkent University of Information Technologies named after Muhammad al-Khwarizmi Tashkent, Uzbekistan
-
- Keywords:
- Volterra integral equation multi-scale kernel distributed lag memory effect resolvent kernel Neumann series quasi-nilpotent operator task scheduling resource allocation
- Abstract
-
This paper develops a Volterra integral equation model of the second kind with a time-varying, multi-scale kernel for dynamic task scheduling in multi-resource systems. Departing from the single-exponential kernels commonly adopted in the literature, we derive the kernel from first principles of a distributed-lag service mechanism, in which the service capacity committed at a given instant is realised over a spectrum of relaxation times. The resulting kernel K(t,s) = μ(s)u(s)·G(t−s) with G(τ) = Σᵢaᵢ[1 − exp(−γᵢτ)] admits an arbitrary number m of memory scales and reduces to the classical formulation when m = 1. We establish existence and uniqueness of the solution on the whole interval [0,T] without imposing a global contraction condition, relying instead on the quasi-nilpotency of the Volterra operator; this resolves an inconsistency present in earlier treatments, where geometric convergence was claimed despite a kernel norm exceeding unity. For the model parameters the kernel norm attains q = 3.337 > 1, yet the Neumann series converges geometrically with an empirical ratio of 0.354. The resolvent kernel is computed numerically and shown to reproduce the Neumann solution to machine precision. An independent cross-verification against an augmented ordinary differential system yields a maximum discrepancy of 1.61e-3. The trapezoidal quadrature scheme is confirmed to be second-order accurate with an empirically measured order of 2.004. Numerical experiments over a horizon T = 12.00 demonstrate that neglecting memory leads to a systematic underestimation of the queue length reaching 21.51 %, and that the effective memory horizon contracts from 6.66 to 2.65 time units as the number of scales increases from one to three.
- References
-
[1] V. Volterra, Theory of Functionals and of Integral and Integro-Differential Equations. New York: Dover, 1959.
[2] G. Gripenberg, S.-O. Londen, and O. Staffans, Volterra Integral and Functional Equations. Cambridge: Cambridge University Press, 1990.
[3] H. Brunner, Collocation Methods for Volterra Integral and Related Functional Differential Equations. Cambridge: Cambridge University Press, 2004.
[4] P. Linz, Analytical and Numerical Methods for Volterra Equations. Philadelphia: SIAM, 1985.
[5] K. E. Atkinson, The Numerical Solution of Integral Equations of the Second Kind. Cambridge: Cambridge University Press, 1997.
[6] E. A. Coddington and N. Levinson, Theory of Ordinary Differential Equations. New York: McGraw-Hill, 1955.
[7] L. Kleinrock, Queueing Systems, Vol. 1: Theory. New York: Wiley-Interscience, 1975.
[8] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed. Springer, 2016.
[9] P. Brucker, Scheduling Algorithms, 5th ed. Berlin: Springer, 2007.
[10] H. A. Taha, Operations Research: An Introduction, 10th ed. Pearson, 2017.
[11] L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko, The Mathematical Theory of Optimal Processes. New York: Wiley, 1962.
[12] W. H. Fleming and R. W. Rishel, Deterministic and Stochastic Optimal Control. New York: Springer, 1975.
[13] S. A. Belbas, "A new method for optimal control of Volterra integral equations," Applied Mathematics and Computation, vol. 189, pp. 1902–1915, 2007.
[14] J. C. Butcher, Numerical Methods for Ordinary Differential Equations, 3rd ed. Chichester: Wiley, 2016.
[15] A. Quarteroni, R. Sacco, and F. Saleri, Numerical Mathematics, 2nd ed. Berlin: Springer, 2007.