  Makespan minimization in restricted assignment $(R|p_{ij}\in \{p_j,
\infty\}|C_{\max})$ is a classical problem in the field of machine scheduling.
In a landmark paper in 1990 [8], Lenstra, Shmoys, and Tardos gave a
2-approximation algorithm and proved that the problem cannot be approximated
within 1.5 unless P=NP. The upper and lower bounds of the problem have been
essentially unimproved in the intervening 25 years, despite several remarkable
successful attempts in some special cases of the problem [2,4,12] recently.
  In this paper, we consider a special case called graph-balancing with light
hyper edges, where heavy jobs can be assigned to at most two machines while
light jobs can be assigned to any number of machines. For this case, we present
algorithms with approximation ratios strictly better than 2. Specifically,
  Two job sizes: Suppose that light jobs have weight $w$ and heavy jobs have
weight $W$, and $w < W$. We give a $1.5$-approximation algorithm (note that the
current 1.5 lower bound is established in an even more restrictive setting
[1,3]). Indeed, depending on the specific values of $w$ and $W$, sometimes our
algorithm guarantees sub-1.5 approximation ratios.
  Arbitrary job sizes: Suppose that $W$ is the largest given weight, heavy jobs
have weights in the range of $(\beta W, W]$, where $4/7\leq \beta < 1$, and
light jobs have weights in the range of $(0,\beta W]$. We present a
$(5/3+\beta/3)$-approximation algorithm.
  Our algorithms are purely combinatorial, without the need of solving a linear
program as required in most other known approaches.
