具有双重时间窗约束的作业车间调度算法

为解决实际生产调度中等待时间受限引起的工件加工时间窗约束和设备能力有限引起的机器可加工时间窗约束,以工件完工率最大为优化目标,建立了具有双重时间窗约束的作业车间调度模型,提出了求解该模型的基于启发式规则的禁忌搜索算法。在分析优化目标与约束条件关系的基础上,提出了工件选择和机器分配的启发式规则,并利用启发性规则生成初始调度方案;设计具有块邻域结构的禁忌搜索算法,减小了邻域规模,通过迭代优化最终获得较优的调度方案。选择多种不同规模的算例与传统算法进行对比分析,实验结果表明了所提算法的可行性和有效性。

Dual Time Window Constrained Job-shop Scheduling Algorithm

To deal with processing time window constraints caused by limited waiting time and machinable time window constraints caused by limited equipment capacity, the job-shop scheduling model with dual time window constraints was established, which aims to maximize job complement rate. The tabu search algorithm based on heuristic rule was proposed. Though analyzing the relation of objective and constraints, the strategies of job selection and machine assignment were designed, by which the initial scheme was get. The tabu search algorithm with the block structure, which reduces the size of neighborhood, was used to get preferable scheme though iterative optimization. The examples with different scales were selected to compare results of the proposed and typical algorithm. Experiments results showed that the presented algorithm is feasible and effective.