Due to the large variety of options offered to customers, batch production schemes are highly accepted in the paint industry implying that scheduling plays an important role in optimal allocation of plant resources among multiple products. Since in a batch process, the cleaning of equipment units is the major source of waste, waste minimization is also to be taken into account in determining the schedule. The formerly developed S-graph framework Sanmartí E, Holczinger T, Puigjaner L, Friedler F. Combinatorial framework for effective scheduling of multipurpose batch plants. AIChE Journal 2002;48(11):2557–70. proved to be highly effective in solving multipurpose batch scheduling; it has now been specialized for solving paint production scheduling problems including waste minimization. The efficacy of the new approach is illustrated with the solution of large-scale paint production scheduling problems.