One prototypical instability in granular flows is the shear-banding instability, in which a uniform granular shear flow breaks into alternating bands of dense and dilute clusters of particles having low and high shear (shear stress or shear rate), respectively. In this work, the shear-banding instability in an arbitrarily inelastic granular shear flow is analyzed through the linear stability analysis of granular hydrodynamic equations closed with Navier-Stokes-level constitutive relations. It is shown that the choice of appropriate constitutive relations plays an important role in predicting the shear-banding instability. A parametric study is carried out to study the effect of the restitution coefficient, channel width, and mean density. Two global criteria relating the control parameters are found for the onset of the shear-banding instability. © 2019 American Physical Society. UK.