The first Death Star was in construction at the end of Episode III (presumably 19 BBY). The ending shot is this picture, with only small portions of the superstructure completed:
19 years later, the Death Star has only been recently completed (the novel Death Star places the completion about 1 BBY). So we assume it took about 18 years to build, and that's with tons of Wookies working on it. Fast-forward to Return of the Jedi in 4 ABY, and the second Death Star is significantly built, and is "fully operational":
They had learned from their mistake on the first Death Star, and had covered up the thermal ports. Presumably they did not just make a patchwork fix, but re-engineered that portion. Anyway, it seems unlikely the progress made on the second Death Star occured in only 4 years. Both Death Stars cost huge amounts of money and resources, and having two in construction would have been much more difficult to hide. So were both in construction at the same time?