基于约束满足的车间调度算法综述-计算机集成制造系统.PDF

第 卷第 期 计算机集成制造系统 １３ １ Ｖｏｌ．１３Ｎｏ．１ 年 月 ２００７ １ Ｃｏｍ ｕｔｅｒＩｎｔｅｒａｔｅｄＭａｎｕｆａｃｔｕｒｉｎ Ｓｓｔｅｍｓ Ｊａｎ．２００７ ｐ ｇ ｇ ｙ 文章编号： （ ） １００６－５９１１２００７０１－０１１７－０９ 基于约束满足的车间调度算法综述 郭冬芬，李铁克 （北京科技大学 管理学院，北京 １０００８３） 　 摘 要：为了说明如何利用启发式信息构造车间调度的约束满足求解算法，首先概述了常规约束满足求解技 　 术，进而介绍了车间调度问题的约束传播算法、树有哪些信誉好的足球投注网站算法和启发式修复算法的构造原理及适用性。在此基础上， 针对目标优化问题，给出两种求解框架。最后，指出近期的研究趋势和进一步的研究工作。 关键词：车间调度；约束满足；约束传播算法；树有哪些信誉好的足球投注网站算法；启发式修复算法；混合求解方法 中图分类号： 文献标识码： ＴＰ１８ Ａ 　　　 犆狅狀狊狋狉犪犻狀狋－犫犪狊犲犱犪犾狅狉犻狋犺犿犳狅狉犑狅犫犛犺狅 狊犮犺犲犱狌犾犻狀 犵 狆 犵 ， 犌犝犗犇狅狀 － 犲狀 犔犐犜犻犲－犽犲 犵 犳 （ ， ， ， ） Ｓｃｈ．ｏｆＭａｎａｅｍａｎｔＵｎｉｖ．ｏｆＳ＆ＴＢｅｉｉｎ Ｂｅｉｉｎ １０００８３ Ｃｈｉｎａ ｇ ｊｇ ｊｇ　 ： 犃犫狊狋狉犪犮狋Ｔｏｅｘｌａｉｎｈｏｗｔｏｕｓｅｔｈｅｈｅｕｒｉｓｔｉｃｓｉｎｆｏｒｍａｔｉｏｎｏｆｔｈｅ ｒｏｂｌｅｍｔｏｃｏｎｓｔｒｕｃｔｃｏｎｓｔｒａｉｎｔ－ｂａｓｅｄｓｏｌｖｉｎ ａｌ ｐ ｐ ｇ ， ， ｏｒｉｔｈｍ ｔｈｅ ｅｎｅｒａｌｃｏｎｓｔｒａｉｎｔｓａｔｉｓｆａｃｔｉｏｎｓｏｌｖｉｎ ｔｅｃｈｎｏｌｏ ｗａｓｂｒｉｅｆｌｉｎｔｒｏｄｕｃｅｄ ｔｈｅｎｔｈｅ ｒｉｎｃｉｌｅｓａｎｄｔｈｅ ｇ ｇ ｇ ｇｙ ｙ ｐ ｐ ， ａ ｌｉｃａｂｉｌｉｔｏｆｃｏｎｓｔｒａｉｎｔｒｏａａｔｉｏｎａｌｏｒｉｔｈｍ ｔｒｅｅｓｅａｒｃｈａｌｏｒｉｔｈｍａｎｄｈｅｕｒｉｓｔｉｃｓｒｅａｉｒａｌｏｒｉｔｈｍｆｏｒＪｏｂＳｈｏ ｐｐ ｙ ｐ ｐｇ ｇ ｇ ｐ ｇ ｐ ， ｓｃｈｅｄｕｌｉｎ ｗｅｒｅｓｕｍｍａｒｉｚｅｄ．Ｆｕｒｔｈｅｒｍｏｒｅ ｔｗｏｓｏｌｕｔｉｏｎｆｒａｍｅｗｏｒｋｓｆｏｒｏｂ