The single-stage multi-product scheduling problem (SMSP) in a batch plant with unrelated parallel units has been solved by both exact and meta-heuristic methods. Although new ideas have been put forward continually, large-size instances are still challenging due to the NP-hardness of the problem. This paper extends the fastest mixed integer linear programming (MILP) model so far for SMSP with sequence-dependent changeovers to general cases where unit/order release times need to be considered. Improved versions of the line-up competition algorithm (LUCA) are also proposed. Computational tests with representative examples indicate that the improved versions are more effective in solving large-size SMSP.