MRP rescheduling heuristics with capacity extension under deterministic demand

The multi-stage, multi-machine capacitated lot-sizing problem (MSMMCLSP) consists of scheduling the production of one product in a multi-machine production system with a multi-stage structure. Machine capacity is reserved for the production of the end item but can be extended by working overtime (overtime capacity). When a lot size is positive in a specific period, it can be loaded on all machines without exceeding the sum of the regular and overtime capacity limits. In previous research, we have proposed a rescheduling heuristic to determine a feasible and sufficient solution for the MSMMCLSP with only regular capacity limits, in comparison with Franca et al.'s heuristic method. However, the mechanism of rescheduling in regular time has not optimum (or near optimum) performance for the MSMMCLSP with capacity extension. Preliminary examination revealed that overtime production also has situation-dependent advantages and disadvantages with the combination of various planning parameters. This study, therefore, develops an integrated heuristic that guarantees an optimal solution for general MSMMCLSP by combining the rescheduling mechanism and overtime production. We also evaluate the effectiveness of the proposed heuristics by using computational tests with various planning parameters.