考虑交货期和等待时间受限的HFS调度问题的混合算法

Hybrid Algorithms for Hybrid Flowshop Scheduling Considering Due Dates and Limited Wating Times

针对工件具有交货期要求以及等待时间受限的混合流水车间调度问题,提出了一种回溯、启发式修复与邻域搜索相结合的混合算法。工件按启发式规则形成加工序列,以排列排序方式经过各加工阶段,采用递归回溯消除工件在相邻阶段的等待时间受限冲突,形成所有机器上的操作加工序列;通过对最后阶段机器上的操作加工序列进行移动修复以最小化其提前/拖期成本;对工件排序进行邻域搜索以改进目标函数值。数据实验表明该混合算法具有可行性和有效性。

A hybrid algorithm, which includes backtracking, heuristic repairing and neighborhood search, is proposed to solve the hybrid flowshop scheduling （HFS） problem with due dates and limited waiting times. Jobs are processed through all stages with the same routing priority that is formed by problem-dependent heuristics rules. The backtracking is used to solve constraints of limited waiting times. All operation processing orders are constructed. The heuristic repairing is applied to the orders of the last stage to minimized the cost of earliness and tardiness. And the neighborhood search is performed to improve objectives. Experiments show that the hybrid algorithm is feasible and effective.