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.
Categories: cs.DS cs.DM