Minimising maximum tardiness in assembly flowshops with setup times
研究两阶段装配流水车间调度问题，目标是最小化最大延迟，提出混合模拟退火与插入算法，相比现有最优算法平均降低误差超90%。
This paper addresses a two-stage assembly flowshop scheduling problem with the objective of minimising maximum tardiness where set-up times are considered as separate from processing times. The performance measure of maximum tardiness is important for some scheduling environments, and hence, it should be taken into account while making scheduling decisions for such environments. Given that the problem is strongly NP-hard, different algorithms have been proposed in the literature. The algorithm of Self-Adaptive Differential Evolution (SDE) performs as the best for the problem in the literature. We propose a new hybrid simulated annealing and insertion algorithm (SMI). The insertion step, in the SMI algorithm, strengthens the exploration step of the simulated annealing algorithm at the beginning and reinforces the exploitation step of the simulated annealing algorithm towards the end. Furthermore, we develop several dominance relations for the problem which are incorporated in the proposed SMI algorithm. We compare the performance of the proposed SMI algorithm with that of the best existing algorithm, SDE. The computational experiments indicate that the proposed SMI algorithm performs significantly better than the existing SDE algorithm. More specifically, under the same CPU time, the proposed SMI algorithm, on average, reduces the error of the best existing SDE algorithm over 90%, which indicates the superiority of the proposed SMI algorithm.