Create a number by multi by $2$ and divide by $3$ (integer part)

I hope I did not miss it somewhere in the many wonderful comments and partial answers above, but did you try a brute-force forward approach?

For instance, the following python lines:

from collections import deque

Q = deque([(2,"2")])
seen = {}
consecutive=-1

def eval(s): # to check results
        i=0
        resu=1
        while i<len(s):
                if s[i]=='2':
                        resu *= 2
                else:
                        resu /= 3
                i+=1
        return(resu)

while True:
        (x,s) = Q.popleft()
        if x not in seen:
                seen[x] = s
                Q.append((x*2,s+"2"))
                Q.append((int(x/3),s+"3"))
                while x==consecutive+1 and x in seen:
                        assert(x==eval(seen[x]))
                        print x,seen[x]
                        consecutive+=1
                        seen[x]="" # to save space
                        x += 1

enumerate all possible solutions in increasing length order, and output them in increasing value order, if I am correct.

It reaches 1434 in seconds on my laptop, and then get stuck (because of memory limitations, I think, and because 1435 has a significantly longer decomposition). It goes above 2400 in minutes on my server with more memory, then gets stuck for a while, then goes above 4400, then gets stuck.

BTW, it finds a decompositions, but there may be several decompositions of same, minimal length.

Once this minimal length is known for a given number $N$, another brute-force approach consists in sampling random decompositions of this length and check if they are decompositions of $N$. For instance, after establishing with Gottfried (see comments) that the shortest decompositions of 4535 have length 77, I sampled 20 billions decompositions (in a few minutes) and obtained the following decompositions of 4535:

22222322223323222232222232323322223222232222222223222233322233233223333222233
22222322232232322232232222323232222322232232222223232233222233222233222333233
22223222322232322232232222322232232232322232222222333223322233232223322322233

They were obtained only once each, suggesting that there are many more solutions, and is consistent with the fact that we are far from sampling all $2^{77} > 10^{23}$ possible decompositions.

This is a terrible waste of computational resources, of course!

I am not sure if it is optimum, but it shouldn't be too bad to
Find the highest power of $2$ that divides $N$. Let this be $c$
Let $M=N/2^c$
Start with $a=b=0$
If $\lfloor \frac {2^a}{3^b}\rfloor \lt M: a=a+1$
If $\lfloor \frac {2^a}{3^b}\rfloor \gt M: b=b+1$
Else return $a,b,c$
Loop to first If

Maybe you want to loop over $0$ to this $c$ for the final exponent and try all the possibilities.

After a few dozen tries, I always found the best answer with $c$ as large as possible, but have not proven it to be the best.