We consider the Multimessage Multicasting problem for complete static networks. We present problem instances that require d^2 time to transmit all their messages, where d is the maximum number of messages that each processor may send (receive). We show that when messages have fan-out k = 1, the problem is polynomially solvable, and becomes NP-complete when k \geqslant 2. We present an algorithm to generate schedules with total communication time 2d-1 when k = 2. We present an efficient algorithm with an approximation bound of qd + k_q^2 (d - 1), for any integer k > q \geqslant 2 Our algorithms are centralized and require all the com- munication information ahead of time. We discuss several applications when all of this information is available. By doubling the number of communication phases, our results apply to the Meiko CS-2 machine and in general to dynamic networks.