Improved exact and meta-heuristic methods for minimizing makespan of large-size SMSP

- The latest efficient MILP model is adapted to general cases.
- Improvements on an existing heuristic method are proposed.
- Global way to update a new generation.
- Consideration of the asymmetry of the problem.
- Effectiveness of the improved methods is verified by case study.

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.