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

中国机械工程 ›› 2010, Vol. 21 ›› Issue (20): 2445-2450,2458.

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

杨宏安;孙启峰;郭杰

西北工业大学,西安,710072

出版日期:2010-10-25 发布日期:2010-10-29
基金资助:
国家自然科学基金资助项目(50705076)；国家高技术研究发展计划(863计划)资助项目(2007AA04Z187，2007AA040701)
National Natural Science Foundation of China（No. 50705076）;
National High-tech R&D Program of China (863 Program) （No. 2007AA04Z187，2007AA040701）

Constrained Optimization Techniques for Job Shop Scheduling

Yang Hong’an;Sun Qifeng;Guo Jie

Northwestern Polytechnical University,Xi’an,710072

Online:2010-10-25 Published:2010-10-29
Supported by:

National Natural Science Foundation of China（No. 50705076）;
National High-tech R&D Program of China (863 Program) （No. 2007AA04Z187，2007AA040701）

摘要/Abstract

摘要：

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

关键词:

作业车间调度, 约束优化, 瓶颈机床, 回溯搜索, &ldquo, Thrashing&rdquo, 现象

Abstract:

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 states, 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.

Key words: job shop scheduling, constrained optimization, bottleneck-machine, backtrack search, thrashing

中图分类号:

TP278

杨宏安, 孙启峰, 郭杰.

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

[J]. 中国机械工程, 2010, 21(20): 2445-2450,2458.

YANG Hong-An, SUN Qi-Feng, GUO Jie.

Constrained Optimization Techniques for Job Shop Scheduling

[J]. China Mechanical Engineering, 2010, 21(20): 2445-2450,2458.

参考文献

[1]上官春霞[1],周泓[1],师瑞峰[2],吴旸[1].作业车间排序重调度问题及其改进修复约束满足算法[J].计算机集成制造系统,2008,14(9):1742-1751.
[2]杨宏安[1],孙树栋[1],司书宾[1],梁辰[2].基于动态一致性增强技术的Job Shop调度算法研究[J].西北工业大学学报,2007,25(4):523-527.
[3]郭冬芬[1],李铁克[1].基于约束满足的车间调度算法综述[J].计算机集成制造系统,2007,13(1):117-125.
[4]陈恩红,薛瀚宏.基于约束满足的Job—Shop调度问题求解方法研究[J].软件学报,1998,9(12):946-948.
[5]段透明,陈进.基于约束分析的Job Shop调度算法的综述[J].重庆大学学报：自然科学版,1998,21(1):133-138.
[6]Smith S F,Peng Si Ow,Jean-Yves Porvin.OPIS:an Opportunistic Factory Scheduling System. Proceedings of the3rd International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems . 1990
[7]Sadeh N,Fox M S.Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem. Artificial Intelligence . 1996
[8]Barták R,Skalicky T.A Local Approach to Auto-mated Correction of Violated Precedence and Re-source Constraints in Manually Altered Schedules. Proceedins of MISTA2009:Fourth Multidis-ciplinary International Scheduling Conference:The-ory and Applications . 2009
[9]Barták R.Constraint Satisfaction Techniques in Planning and Scheduling:An Introduction. Archives of Control Sciences . 2008
[10]Dechter R,,Meiri I.Experimental Evaluation of Preprocessing Techniques in Constraint Satisfac-tion Problems. Proceedings of the Eleventh International Joint Conference on Artificial Intelli-gence . 1989
[11]M Fox.Constraint-directed search: A case study of job shop scheduling. . 1983
[12]Fox MS,Smith SF.ISIS: a knowledge-based system for factory scheduling. Expert Systems . 1984
[13]Peng S O,Morton T E.The single machine early/tardy problem. Management Science . 1989
[14]SADEH N,SYCARA K,XIONG Y.Backtracking tech-niques for the Job Shop scheduling constraint satisfactionproblem. Artificial Intelligence . 1995