brew outdated | parallel --keep-order brew fetch --deps && brew upgrade

# without GNU parallel (output will be out of order):
brew outdated -q | xargs -L1 -P8 brew fetch --deps