Two important issues that need to be addressed when designing medium access control (MAC) protocols for Wavelength Division Multiplexing networks are message sequencing and channel assignment. Channel assignment addresses the problem of choosing an appropriate data channel via which a message is transmitted. This problem has been addressed extensively in the literature. On the other hand, message sequencing, which addresses the order in which messages are sent, has rarely been addressed. In this paper, we propose a new reservation-based message scheduling algorithm called RO-EATS that addresses both the channel assignment and message sequencing during its scheduling process. We formulate an analytical model and conduct extensive simulations to evaluate the performance of this algorithm. We compare the performance results of a well-known algorithm which only addresses the channel assignment issue with those of our new algorithm. The comparison shows that our new algorithm gives significant improvement over scheduling algorithms that do not consider message sequencing. As a result, we anticipate that these research results will lead to new approaches to message scheduling on WDM networks.