Title :
Inter-completion time scheduling (ICTS): non-preemptive scheduling to maximize the minimum inter-completion time
Author :
Amaro, Carlos C. ; Stoyen, Alexander D. ; Baruah, Sanjoy K.
Author_Institution :
Dept. of Comput. & Inf. Sci., New Jersey Inst. of Technol., Newark, NJ, USA
Abstract :
Temporal load-balancing, spreading out the executions of tasks over time, is desirable in many applications in complex systems. A form of temporal load balancing is discussed, scheduling to maximize minimum inter-completion time (MICT-scheduling) and minimum global inter-completion time (MGICT-scheduling). It is shown that MICT- and MGICT-scheduling are, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MICT- and MGICT-scheduled
Keywords :
computational complexity; distributed processing; resource allocation; scheduling; MGICT-scheduling; MICT-scheduling; NP-hard; complex systems; inter-completion time scheduling; minimum global inter-completion time; minimum inter-completion time; nonpreemptive scheduling; task systems; temporal load balancing; Load management; Processor scheduling; Real time systems;
Conference_Titel :
Engineering of Complex Computer Systems, 1998. ICECCS '98. Proceedings. Fourth IEEE International Conference on
Conference_Location :
Monterey, CA
Print_ISBN :
0-8186-8597-2
DOI :
10.1109/ICECCS.1998.706653
