We define an integral form of the shuffle algebra and the deformed W-algebra of type gl_r, and show that they act on the K-theory groups of moduli spaces of rank r stable sheaves on a smooth projective surface, under certain assumptions. Our inspiration is the action studied by Nakajima, Grojnowski and Baranovsky in cohomology, although the appearance of deformed W-algebras by generators and relations is a new feature.