He then went on tour with the Fletcher Henderson Orchestra .
He then toured with the Fletcher Henderson Orchestra ( 1943 â `` 4 ) .