By formulating the problem of minimizing the makespan on a single batch machine with non-identical job sizes as a problem of minimizing the wasted space minimization, a candidate set strategy is designed to narrow the search space when constructing the batches, combined with a heuristic based on the wasted space to update the pheromone information. Incorporated with a local optimization method to further improve the performance, an improved max-min ant system algorithm is presented. Moreover, the parameter setting in the proposed algorithm is analyzed by experimental designs to determine the appropriate parameter values. The simulation results show the effectiveness and robustness of the proposed algorithm that outperforms several previously studied algorithms.