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

项目名称： 基于无冲突集的约束Job Shop调度优化算法

项目编号： No.60973073

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 李小平

作者单位： 东南大学

项目金额： 30万元

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

中文关键词： 无冲突集；无等待；阻塞；Job Shop；

英文摘要：

英文关键词： no-conflicting set；no-wait；blocking；Job Shop；