Delay performance of downlink non-orthogonal multiple access (NOMA) networks is investigated. To fully realize advantages offered by NOMA, we need to consider more realistic network environment; as such, departing from the literature on NOMA, this paper relaxes the full-buffer assumption and allows each user in the network to have its individual delay-cost function. The former captures the sporadic nature of data arrivals in some applications, while the latter accepts potential coexistence of heterogeneous users. In this context, we propose three transmission scheduling algorithms, namely the MDP-based, the $c- \mu$ -based, and the learning-based scheduling algorithms. While the MDP-based scheduling algorithm is shown to be delay-optimal, the other two scheduling algorithms enjoy the online feature where transmitters are oblivious to arrival statistics. Moreover, it turns out that the $c-\mu$ -based scheduling algorithm is a greedy version of the MDP-based scheduling algorithm and the learning-based scheduling algorithm is asymptotically delay-optimal. Simulation results corroborate our theoretical analysis and fortify the common belief about the superiority of NOMA over OMA, even without the full-buffer assumption and with heterogeneous users.