An effective Iterated Greedy algorithm for the distributed permutation flowshop scheduling with due windows

Distributed Permutation Flowshop Scheduling Problem (DPFSP) has become a research hotspot in recent years. However, as a service level objective, the Total Weighted Earliness and Tardiness (TWET) has not been addressed so far. Due to the importance of the service level objective in modern industry, we deal with the minimization of the TWET for the DPFSP with due windows . An Iterated Greedy (IG) algorithm, namely IG with Idle Time insertion Evaluation (IG I T E ), is proposed. In the algorithm, an adapted NEH heuristic with five rules based on the unit earliness weight and unit tardiness weight, the due date, and the smallest slack on the last machine is used to generate an initial solution. Destruction procedure with a dynamic size is provided to enhance the exploration capability of the algorithm. Idle time insertion method is utilized to make the completion time of jobs within the due windows or as close to the due windows as possible. A large number of experiments show that the presented algorithm performs significantly better than the five competing algorithms adapted in the literature. The performance analysis shows that the IG I T E is the most appropriate for the DPFSP with due windows among the tested algorithms.