Herb -
There is a big difference between "can" and "should".
Technically, you might be able to get over Washington Pass in early May -
But the weather may also be brutal, most campgrounds will be closed,
and Going to the Sun Road in Glacier will still be closed, too.
You offer little info about your trip parameters and experience.
Nothing can ruin bike tour faster than a rigid itinerary.
Also, I doubt you are from the Mountain West -
Otherwise you would know that spring comes late to the high country -
And the snow melts even later.
I've toured almost 100,000 miles - including many ACA routes.
Generally, if you need to start early in the season, you go east to west.
Similarly, a late start favors a west to east direction.
Each of the ACA transcontinental routes presents weather issues in the West.
On the Western Express, you want to leave late enough to have reasonable conditions in the Sierra Nevadas.
but also early enough so that you do not roast in Nevada and Utah. Early May can be risky, late May may already be too hot.
On the TransAm, you have the greatest flexibility since the elevations are moderate until you get to Yellowstone. Still, Oregon stays pretty wet through May, McKenzie Pass is often closed until late May, and you don't want to be stuck in an early June snowstorm in Yellowstone. Late May to mid-June is the ideal time to start out.
On the Northern Tier, you should use not only Washington Pass, but also Going to the Sun as guides. Since Going to the Sun will not open until late June, you can backtrack three weeks to get an approximate earliest start date - June 1. And even then services may be limited in the North Cascades and you might get a late storm system, too.
So, in short -
Early May - Western Express
Late May - TransAm
Early June - Northern Tier.
Remember - the idea is to have a good time.