Can you live with the number not starting at 001 each year? That will be a whole lot simpler if you can accept that.
If you can live with that, then the formula will be
(not tested, so please post back if there are any syntax errors)
var text Dept = Case([Department ID],
"Construction", "10",
"Fabrication", "20", "error");
var text YY = Right(ToText(Year([Quote - Date of Bid])),2);
var text Number = Right("00" & ToText([Record ID#]),3);
$YY & $Number & "-" & $Dept
The formula above uses
formula variables to break up the syntax into smaller bite size units.