  We consider a transmission scheduling problem in which multiple systems
receive update information through a shared Time Division Multiple Access
(TDMA) channel. To provide timely delivery of update information, the problem
asks for a schedule that minimizes the overall age of information. We call this
problem the Min-Age problem. This problem is first studied by He \textit{et
al.} [IEEE Trans. Inform. Theory, 2018], who identified several special cases
where the problem can be solved optimally in polynomial time. Our contribution
is threefold. First, we introduce a new job scheduling problem called the
Min-WCS problem, and we prove that, for any constant $r \geq 1$, every
$r$-approximation algorithm for the Min-WCS problem can be transformed into an
$r$-approximation algorithm for the Min-Age problem. Second, we give a
randomized 2.733-approximation algorithm and a dynamic-programming-based exact
algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem
is NP-hard.
