Consider the assignment problem:
$$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$ s.t. $$ \sum_i x_{ij} = 1 \quad\forall j $$ $$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$ $$ x_{ij} \in \{0,1\}\quad\forall i,j $$
So, in scheduling terminology, $x_{ij}$ is $1$ if job $j$ is assigned to machine $i$, or $0$ otherwise, for $i = 1,\ldots,n$, $j = 1,\ldots,m$, and $k = 1,\ldots,m$.
The first constraint says that each job must be assigned to exactly one machine, and the second constraint says that the number of jobs assigned to each machine must fall on the interval $[a,b]$.
In the objective, there is no cost for assigning job $j$ to machine $i$, however there is a cost $c_{jk}$ of assigning job $j$ to machine $i$ and job $k$ to machine $i$. I suppose you could consider this cost the level of incompatibility between the two jobs - perhaps some sort of changeover cost. This problem is NP-Hard.
Now, suppose the first set of constraints are dualized:
$$ Z_\lambda = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} + \sum_j[\lambda_j(\sum_ix_{ij} - 1) ] $$ s.t. $$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$ $$ x_{ij} \in \{0,1\}\quad\forall i,j $$
Now, the constraints which couple each machine together have been dualized and the problem breaks apart into one subproblem for each machine.
I don't have a lot of experience with this sort of Lagrangean Relaxation-based decomposition. I believe, in theory, it should just be a case of solving each of the subproblems as a separate, self-contained problem, and update the lagrangian multipliers $\lambda$ at each iteration. I'm using the subgradient method converge on the optimal $\lambda$.
The problem I'm having is that there is no difference at all in the definition of the subproblems from one machine to another, and the lagrangian multipliers are shared between all subproblems. That means, if I have $n$ machines, then I have $n$ completely identical subproblems which, when I solve, I obtain an identical solution from each of them. Sure, I can update my $\lambda$ vector based on my primal infeasible solution, but the model definitions in the subsequent iterations remain identical.
Clearly I'm doing something wrong, but I'm not sure what, exactly. The paper I have here "Lagrangean Relaxation - Monique Guignard (2003)", as well as others I've discussed this with assert that dualizing the coupling constraints for this sort of model should produce $n$ subproblems.
First, always try and avoid non-linearity in your formulation. Usually logical conditions like "if both jobs $j$ and $k$ are assigned to machine $i$" can be expressed linearly by introducing more variables.
$$ z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0 $$ You can confirm that $z_{ijk}$ is 1 only if both $x_{ik},x_{ij}$ are 1. The problem then is
$$ Z = \min \sum_{ijk}c_{jk}z_{ijk}\\ \sum_{i}x_{ij} =1\\ a \leq \sum_j x_{ij} \leq b\\ z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0 $$
Decomposing leads to $$ Z^\lambda = \min \sum_{ijk}c_{jk}z_{ijk}+\sum_j\lambda_j\left(\sum_{i}x_{ij} -1\right)\\ a \leq \sum_j x_{ij} \leq b\\ z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0 $$ The constraint that is relaxed is the assignment constraint that all jobs must be assigned only one machine, so your relaxed solution would have more than one machine assigned per job. In your solution of the dual problem when you update $\lambda$ the penalty due to the dualization will increase to a point where this penalty will be very expensive and the program will start setting some of the $x_{ij}$s to 0, so go ahead with solving the dual problem.
There is however, another problem with complete symmetry in the machines $i$, specially if your problem is large, there are a lot of possible solutions. This is because any optimal assignment can be permuted to arrive at another solution. And you may be unnecessarily searching across essentially equal assignments. The way around this is to add symmetry breaking constraints of the form given in [1].
[1] Sherali, Hanif D., and J. Cole Smith. "Improving discrete model representations via symmetry considerations." Management Science 47.10 (2001): 1396-1407.