  We study the scheduling of jobs on a single parallel-batching machine with
non-identical job sizes and incompatible job families. Jobs from the same
family have the same processing time and can be loaded into a batch, as long as
the batch size respects the machine capacity. The objective is to minimize the
total weighted completion time. The problem combines two classic combinatorial
problems, namely bin packing and single machine scheduling. We develop three
new mixed-integer linear-programming formulations, namely an assignment-based
formulation, a time-indexed formulation (TIF), and a set-partitioning
formulation (SPF). We also propose a column generation (CG) algorithm for the
SPF, which is the basis for a branch-and-price (B&P) algorithm and a CG-based
heuristic. We develop a preprocessing method to reduce the formulation size. A
heuristic framework based on proximity search is also developed using the TIF.
The SPF and B&P can solve instances with non-unit and unit job durations to
optimality with up to 80 and 150 jobs within reasonable runtime limits,
respectively. The proposed heuristics perform better than the methods from the
literature.
