A rigorous theoretical investigation has been made on linear and nonlinear propagation of electrostatic perturbation modes in a dusty electron-positron-ion plasma. The linear dispersion properties of such perturbation modes in such a plasma system has been first examined by the normal mode analysis. The possibility for the formation of nonlinear coherent structures (viz. solitary waves and double layers) associated with such waves in the plasma system (under consideration) has been theoretically investigated. The reductive perturbation method, which is valid for small amplitude limit, and pseudopotential approach, which is valid for arbitrary amplitude waves, has been applied to study the basic features of solitary waves (SWs) and double layers (DLs). The co-existence of positive and negative SWs, and existence of either positive or negative DLs have been observed for certain range of different plasma parameters. The basic features and the underlying physics of the non-linear waves (SWs and DLs), which are relevant to some astrophysical compact objects (e.g. white dwarfs, neutron stars, etc.), have been pin-pointed and critically discussed.