A simple mathematical model for efficient short-term scheduling of non-sequential multi-product-multi-unit batch processes with unit- and sequence-dependent setup/changeover times and mixed intermediate storage policies is proposed. The scheduling objective is to minimize the makespan or the earliness of the completion of orders. When some of the sequence-dependent changeover times are relatively large compared to the processing times, a rigid formulation is provided to achieve optimality, which is seldom attended to in previous studies. Several intermediate storage policies for the batch processes are considered, including unlimited intermediate storage (UIS), no intermediate storage (NIS), finite intermediate storage (FIS), zero wait (ZW), and mixed intermediate storage (MIS). The problem is then formulated as a mixed-integer linear program (MILP). Two numerical examples are supplied to demonstrate the efficiency and the wide applicability of the proposed scheduling model in face of various different environments.