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

fYear

1998

fDate

10-14 Aug 1998

Firstpage

24

Lastpage

34

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICECCS.1998.706653

Filename

706653