Here is a better, more direct solution.

This problem can be cast as a *Generalized Eigenvalue Problem* as is shown by
Boyd, El Ghaoui, Feron, and Balakrishnan on page 39 (§3.3) of Linear Matrix Inequalities in System and Control Theory:

$$
s(A) = \inf \left\{\gamma \mid A^*PA < \gamma^2 P \textrm{ for diagonal } P > 0
\right\}
$$

**Previous answer**

Unfortunately behind a paywall, but following my own comment about chasing literature on matrix balancing, I found the following old paper that solves your problem (*EDIT*: As noted by Sebastian, this paper actually only provides a solution for a restricted case), not only for the operator norm, but for a variety of other norms.

T. Ström. Minimization of norms and logarithmic norms by diagonal similarities. Computing, March 1972, Volume 10, Issue 1–2, pp 1–7.