基于无冲突集的约束Job Shop调度优化算法

无等待或阻塞的约束Job Shop调度是NP难问题，广泛存在于冶金、制药、食品加工等应用中。无等待Job Shop中任务加工路线确定但不一致，要求任务一旦开始加工便不能间断；阻塞Job Shop中任务加工路线确定且不一致，任务加工过程中如果某一操作所需机器不可达则造成阻塞。基于无等待和阻塞Job Shop调度问题的结构特点，分析任务间可行开始时间所形成无冲突集的性质；提出无冲突集的多项式计算方法，大大减少基于无冲突集时间表算法的计算时间，提高算法效率；提出分组-重构时间表安排策略，设计任务的移动代价评估机制，确定任务的移动方向（前向或后向）和范围，压缩机器空闲时间，提高算法性能；提出包含初始解、邻域搜索和局部解改善等三阶段的全局优化复合启发式算法，为无等待和阻塞Job Shop调度问题提供快速、有效的求解方法。本项目可推广到地铁调度等实际工程应用中，具有重要的科学意义和应用价值。

针对最小化最大完工时间的无等待Job Shop和阻塞Job Shop调度问题，提出有效的求解方法。将问题分解为时间表问题和排列问题，分析无等待和阻塞Job Shop的结构特点和无冲突集性质，主要目的是从以下几方面提高算法效率：（1）研究任务间距离的特点，基于任务间的可行开始时间形成无冲突集，采用分治法在多项式时间内求解给定排列的最优时间表，大大减少算法的计算时间；（2）建立基于可行时间差集的问题模型，提出基于移动惩罚的时间表方法，对时间表压缩以进一步优化时间表；（3）研究有效的邻域构造方法，提出包含初始解、邻域搜索和局部解提高等三阶段的全局优化复合启发式算法。