A lever concept integrated with simple rules for flow shop scheduling
分析了流水车间调度问题中最小化最大完工时间的性质，提出一种新的支配规则，并基于杠杆权重因子设计了两种优先调度规则，在Taillard基准问题和手术室历史数据上表现优于现有规则且不增加计算复杂度。
The development of more efficient and better performing priority dispatching rules (PDRs) for production scheduling is relevant to modern flow shop scheduling practice because they are simple, easy to apply and have low computational complexity, especially for large-scale problems. While the current research trend in scheduling is towards finding superior solutions through meta-heuristics, they are computationally expensive and many meta-heuristics also use PDRs to generate starting points. In this paper, we analyse the properties of flow shop scheduling problems to minimise maximum completion time, and generate a new dominance rule that is complementary to Szwarc’s rule. These dominance rules indicate that a weighting factor should be included in sequencing to account for the possibility that a single job’s processing time can generate idle time repeatedly within a flow line. Two new PDRs with a leveraged weighting factor are proposed to minimise makespan and average completion time. Computational results on Taillard’s benchmark problems and on historical operating room data show that the proposed PDRs perform much better than established PDRs without an increase in computational complexity.