约束优化求解作业车间调度问题研究

Constrained Optimization Techniques for Job Shop Scheduling

将作业车间调度问题转化为约束优化问题,直接以工序开工时间作为决策节点,构建了包含工艺路线、机床能力、交货期三类约束和提前/拖期成本指标的约束优化调度模型。采用瓶颈机床优先识别和单机排序优化的两阶段调度策略以降低调度问题的复杂性。为了降低回溯搜索中的"Thrashing"现象发生的概率,引入一致性预处理机制对剩余搜索空间实施预修剪,以剔除相关工序变量值域内的潜在冲突值;采用回溯前移机制优先识别瓶颈机床和满足关键工序赋值,以减轻后续搜索进程发生大面积回溯的压力。最后以深度优先搜索为基础,搭建完成约束优化调度算法框架。80组调度测试用例仿真结果表明,约束优化调度方法在降低在制品库存成本、成品库存成本和调度总成本三方面均优于线性E/T排序和指数E/T排序规则。

The job shop scheduling problem（JSSP） was formulated as constrained optimization problems（COP） herein,and a constrained optimization scheduling model was founded,which used a more realistic cost model that directly accounted for the tardiness costs, work-in-process inventory costs, and finished-goods inventory costs introduced by each job. For reducing complication of solving large-scale JSSP, two-phase approach, which included bottleneck resource identification and single machine E/T sequencing, was put forward. In order to improve the search efficiency and reduce the frequency of thrashing phenomenon, consistency enforcing procedure was put forward to prune the search space by eliminating local inconsistencies that cannot participate in a global scheduling solution. By instantiating and satisfying bottleneck-resource and difficult variables first, the system moved to more constrained deadend state.s, this reduces the time the system wastes attempting to complete partial solutions that cannot be completed. The proposed approaches have been tested on a wide range of 80 scheduling problems and satisfactory results have been obtained.