Temporal load-balancing-"spreading out" the executions of tasks over time-is desirable in many applications. A form of temporal load-balancing is discussed, scheduling to maximize minimum minimum global inter-completion time (MGICT-scheduling). It is shown that MGICT-scheduling is, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MGICT-scheduled. The technique is applied to a Defense Network System. Simulation results indicate that the proposed strategy achieves higher communication performance in multiprocessor systems. Specifically, our strategy significantly reduces average message delay and percentage of delayed messages. (C) 2003 Elsevier Science Ltd. All rights reserved.