Let $\mathbb{N}^{d}$ be the $d$-dimensional monoid of non-negative integers. A generalized numerical semigroup is a submonoid $ S\subseteq \mathbb{N}^d$ such that $H(S)=\mathbb{N}^d \setminus S$ is a finite set. We introduce irreducible generalized numerical semigroups and characterize them in terms of the cardinality of a special subset of $H(S)$. In particular, we describe relaxed monomial orders on $\mathbb N^d$, define the Frobenius element of $S$ with respect to a given relaxed monomial order, and show that the Frobenius element of $S$ is independent of the order if the generalized numerical semigroup is irreducible.