Flexible job-shop scheduling problem with variable lot-sizing: An early release policy-based matheuristic

Variable lot-sizing is a production pattern that allows operations of the same job type to conduct different lot-sizing plans, which brings better flexibility compared to the routine consistent lot-sizing. However, under the variable lot-sizing scheme, since jobs in a sublot are likely to be released from multiple sublots of the previous operation, the sublot is forced to start being processed until all the predecessors are finished, and therefore the production efficiency suffers from a negative impact to a certain extent. To address the inconsistency, this paper investigates a flexible job-shop scheduling problem with variable lot-sizing (FJSP-VLS) for the makespan minimization. First, an early release (ER) policy is proposed to check where jobs of a sublot are transferred from and to accurately identify a set of predecessors, thus ensuring an earlier and feasible release moment for each sublot. Then, a monolithic mixed integer linear programming (MILP) model of the FJSP-VLS with the ER idea is established for the validation. Afterwards, a matheuristic is developed following the ER policy (MHER), where a simplified MILP model only for improving lot-sizing plans is embedded in a genetic algorithm (GA) as a powerful local search function. Finally, four groups of instances are extended from the Fdata benchmark to evaluate the performance of the proposed methods. Extensive experimental results suggest that the ER policy prominently raises the production efficiency by determining earlier release time for sublots. On the basis of this idea, the MILP-based local search brings significant improvements to incumbent solutions provided by the GA, and the MHER is shown effective in a variety of FJSP-VLS scenarios.