  This paper investigates the problem of energy-efficient packet transmission
with a non-FIFO Packet over a point-to-point additive white Gaussian noise
(AWGN) time-invariant channel under the feasibility constraints. More
specifically, we consider the scenario where there is a packet that has a
deadline that is earlier than that of the previously arrived packet. For this
problem, the First-In-First-Out (FIFO) transmission mode adopted in the
existing literatures is no longer optimal. We first propose a novel packet
split and reorder process which convert the inconsistency in the order of
deadlines and arrival instants of the packet sequence into a consistent one.
After the split and reorder process, the original problem considered in this
paper is transformed into the problem of finding the optimal split factor. We
propose an algorithm that finds the split factor which consists of checking
four possibilities by applying the existing optimal transmission strategy
\emph{"String Tautening"} for FIFO packets. In addition, we prove the
optimality of the proposed algorithm in the presence of a non-FIFO packet by
exploiting the optimality properties of the most energy efficient transmission
strategy. Based on the proposed optimal offline scheme, an efficient online
policy which assumes causal arrival information is also studied and shown to
achieve a comparable performance to the proposed optimal offline scheme.
