Totes dues locucions temporals són correctes.
Per tant, podem escriure tant Feu-ho al més aviat possible com Feu-ho el més aviat possible.
També podem dir Feu-ho com més aviat millor o Feu-ho tan aviat com sigui possible, locucions que considerem preferents.
Recordeu que *com abans millor i *quant abans millor no són correctes. Tampoc es pot fer servir la construcció *com més/menys... possible, que és un encreuament de dues locucions.