Distributed hybrid flowshop scheduling with consistent sublots under delivery time windows: A penalty lot-assisted iterated greedy algorithm

Abstract

Integrating the delivery time windows into the distributed hybrid flow shop scheduling contributes to ensuring the timely delivery of products and enhancing customer satisfaction. In view of this, this study focuses on distributed hybrid flowshop scheduling with consistent sublots under the delivery time windows constraint, denoted as DHFm|lotcs|εTWET/DTW. However, there exist some challenges of problem model modeling and algorithmic design for the problem to be addressed. Therefore, we first construct a mixed integer linear programming (MILP) model tailored to DHFm|lotcs|εTWET/DTW with the aim of minimizing the total weighted earliness and tardiness (TWET). Additionally, we introduce a penalty lot-assisted iterated greedy (PL_IG_ITI) and idle time insertion to coincide better with delivery time windows, in which a delivery-time-based multi-rule NEH, an adaptive insertion-based reconstruction based on the changing of the delivery status, a trilaminar penalty lot-assisted local search, and an elitist list-based acceptance criterion are designed to save convergence time and reduce the late deliveries attempts. Lastly, we also introduce a completely new method to generate delivery time windows and create 400 distinct instances. Based on the average results from five runs of 400 instances, PL_IG_ITI demonstrates improvements of 59.0 %, 72.3 %, 76.9 %, and 25.5 % compared to HIGT, DABC, CVND, and IG_MR, respectively. When considering the minimum values from each instance, PL_IG_ITI exhibits enhancements of 59.4 %, 71.8 %, 74.9 %, and 25.4 % over HIGT, DABC, CVND, and IG_MR, respectively, it evident that PL_IG_ITI can effectively solve DHFm|lotcs|εTWET/DTW.

Keywords

• Distributed hybrid flow shop
• Lot streaming
• Iterative greedy algorithm
• Delivery time windows