Lot-streaming flowshop scheduling under stochastic due dates

The lot-streaming flowshop scheduling problem with stochastic due dates is addressed in this paper, aiming to minimise the sum of expected tardiness. Closed-form expressions for the expected tardiness of jobs are derived under various due date distributions. A mathematical model is then formulated for the problem. To tackle the highly nonlinear nature of the model, a linearisation method is proposed. Furthermore, based on the problem structure, a logic-based Benders decomposition methodology is designed, incorporating a branch-and-bound algorithm to solve its subproblem. A new tight lower bound is introduced based on the stochastic order property of the due dates. For due dates lacking stochastic order relationships, a valid lower bound can still be achieved by scaling and unifying the standard deviation of due dates. Moreover, three effective acceleration strategies are introduced to enhance the algorithm's efficiency. Numerical experiments demonstrate the importance of incorporating stochastic due dates and the effectiveness of the proposed algorithms.