We present a real-time scheduling algorithm called VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times with variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, VCFs, and the scheduling objective of assuring that the maximum interval between any two consecutive successful completion of jobs of a task must not exceed a specified bound, and maximizing the system?s total utility. We establish that VCUA achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate VCUA?s effectiveness and superiority.