Accelerated Evaluation of Blocking Flowshop Scheduling With Total Flow Time Criteria Using A Generalized Critical Machine-Based Approach

Abstract

Despite the considerable advances in the research of the blocking flowshop scheduling problem (BFSP), several unresolved challenges persist. Algorithmic complexity presents hurdles. Although the insertion-based method is considered to generate superior solutions, its high computational demand diminishes the efficiency of algorithms, especially within large-scale sequences. The existing accelerated evaluation methods cannot utilize the existing information to quickly calculate the total flow time or the total tardiness time of the changed sequence after the job insertion, but recalculates it from scratch. This does not significantly reduce computational effort and needs to be further improved. In this paper, we delve into the intrinsic features of these challenges, proposing a generalized accelerated critical machine-based evaluation tailored for the total flow time and tardiness criteria of the BFSP with and without sequence-dependent setup times. First, we propose three theorems, one corollary, and their proofs based on the critical machine. Second, we propose the accelerated evaluation procedure based on these theorems to calculate the objectives related to the total flow time. Third, we also extend the proposed accelerated evaluation method to the BFSP with sequence-dependent setup times, aiming to significantly reduce the time complexity. Finally, we conduct four experiments on five well-known benchmarks (a total of 3540 test instances). Through statistical analysis, it becomes evident that our computational efforts have significantly decreased in computing both the total flow time and the total tardiness time. This performance enhancement is superior to the effectiveness of existing acceleration techniques.