  In this paper, we introduce maximum composition ordering problems. The input
is $n$ real functions $f_1,\dots,f_n:\mathbb{R}\to\mathbb{R}$ and a constant
$c\in\mathbb{R}$. We consider two settings: total and partial compositions. The
maximum total composition ordering problem is to compute a permutation
$\sigma:[n]\to[n]$ which maximizes $f_{\sigma(n)}\circ
f_{\sigma(n-1)}\circ\dots\circ f_{\sigma(1)}(c)$, where $[n]=\{1,\dots,n\}$.
The maximum partial composition ordering problem is to compute a permutation
$\sigma:[n]\to[n]$ and a nonnegative integer $k~(0\le k\le n)$ which maximize
$f_{\sigma(k)}\circ f_{\sigma(k-1)}\circ\dots\circ f_{\sigma(1)}(c)$.
  We propose $O(n\log n)$ time algorithms for the maximum total and partial
composition ordering problems for monotone linear functions $f_i$, which
generalize linear deterioration and shortening models for the time-dependent
scheduling problem. We also show that the maximum partial composition ordering
problem can be solved in polynomial time if $f_i$ is of form
$\max\{a_ix+b_i,c_i\}$ for some constants $a_i\,(\ge 0)$, $b_i$ and $c_i$. We
finally prove that there exists no constant-factor approximation algorithm for
the problems, even if $f_i$'s are monotone, piecewise linear functions with at
most two pieces, unless P=NP.
