准时制生产方式下多目标单机调度算法研究.pdf

合肥工业大学 硕士学位论文 准时制生产方式下多目标单机调度算法研究 姓名：陈昊 申请学位级别：硕士 专业：信息管理与信息系统 指导教师：刘心报 20100401 准时制生产方式下多目标单机调度问题算法研究 摘要 基于p a r e t o 解的多目标生产调度问题一直是国内外学者研究的热点 问题目前的解决方案有三大类：确定性算法、启发式算法以及人工智 能算法但是，针对多目标调度问题的研究往往只关注于算法本身，对 于算法的评价方法以及测试数据集没有给予足够的重视，而且在提高算 法性能时，也只关注p a r e t o 解集的某一个指标，因而很难全面地提高解 集的质量 为解决上述问题，本文首先从算法消耗的时间和解集的质量两个角度 提出了“合理时间内取得更优解”的算法评价方法，并且进一步综合单 个解的质量、分布性能和分布范围三个指标提出了最短距离加权和的方 法来评价p a r e t o 解集的质量；然后以J I T 生产方式下的多目标单机调度 问题为例，在恢复束搜索算法的基础上，引入子方向搜索概念提出了改 进的束搜索算法；最后探讨了测试数据集的应满足的几个条件并针对本 文研究的问题提出了五类八十组测试数据，并且在此基础上使用前文提 出的评价方法比较了束搜索算法和改进束搜索算法。

关键字：准时制生产；多且标调度；算法评价；S D R B S 算法 S t u d y0 1 1m u l t i —·o b j e c t i v es i n g l em a c h i n es c h e d u l i n g p r o b l e mn n d e rJ u s t —I n - T i m ep r o d u c t i o nm o d e A b s t r a e t P a r e t o —b a s e dm u l t i 一0 b j e c t i v e s c h e d u l i n gs o l u t i o nh a sb e e nt h e h o t i s s u eo fd o m e s t i Ca n df o r e i g nr e s e a r c h e r s ．C u r r e n tS O l u t i o n sh a v et h r e e m a i n c a t e g o r i e s ：d e t e r m i n i s t i ca l g o r i t h m ，h e u r i s t i ca l g o r i t h m sa n d a r t i f i c i a l i n t e l l i g e n c ea l g o r i t h m s ．H o w e v e r ，r e s e a r c ho nm u l t i ．o b i e c t i v e s c h e d u l i n gp r o b l e mt e n d e dt of o c u so n l yo nt h ea l g o r i t h mi t s e l f ，d on o t g i v ee n o u g ha t t e n t i o nf o rt h ea l g o r i t h me v a l u a t i o na n dt e s td a t as e t s ．A n d t h er e s e a r c h e r so n l yc o n c e r no n e i m p r o v et h e a lg o r i t h mp e r f o r m a n c e o v e r a l lq u a l i t y0 fS O l u t i o ns e t s ． i n d i c a t o r s o fp a r e t os o l u t i o ns e tt o ，m a k i n g i td i f f i c u l tt oi n c r e a s et h e T os o l v et h ep r o b l e m ，t h i st h e s i s p r o p o s ea na l g o r i t h me v a l u a t i o n m e t h o d s ”o b t a i nt h eb e t t e rs o l u t i o nw i t h i nr e a s o n a b l et i m e ”c o n s i d e r i n gt h e t i m ec o n s u m i n go ft h em e t h o da n dt h eq u a l i t yo ft h es o l u t i o ns e t ，a n d i n t e g r a t e ds i n g l es o l u t i o nq u a l i t y ，p e r f o r m a n c eo ft h ed i s t r i b u t i o n ，r a n g eo f d i s t r i b u t i o nt h r e ei n d i c a t o r si n t ot h es h o r t e s td i s t a n c ew e i g h t e dm e t h o dt o e v a l u a t et h eq u a l i t yo fp a r e t oS O l u t i o ns e t ．T h e nt h i st h e s i sf o c u so nt h eo n m u l t i - o b je c t i v es i n g l em a c h i n es c h e d u l i n gp r o b l e mu n d e rJ u s t —I n ．T i m e p r o d u c t i o ns c h e d u l i n gp r o b l e m ，p r o p o s ea ni m p r o v e dR e c o v e r i n gB e a m S e a r c h a l g o r i t h mb a s e do ns u bd i r e c t i o nc o n c e p t ．T h e n ，w ed i S C U S S t h e c o n d i t i o nf o rt h et e s ts e ta n dp r o p o s e8 0g r o u p so ft e s ts e td a t a ．F i n a l l y t h i st h e s i sc o m p a r et h eR e c o v e r i n gB e a mS e a r c ha l g o r i t h mt ot h eS u b d i r e c t i o nR e c o v e r i n gB e a mS e a r c ha l g o r i t h mo nt h eb a s i so ft h ep r o p o s e d m e t h o do fa l g o r i t h me v a l u a t i o n ． K e y w o r d s ：J u s t - I n —T i m ep r o d u c t i o n ；m u l t i —o b j e c t i v e s c h e d u l i n g ； A 1 9 0 r i t h me v a l u a t i o n ；S u b —d i r e c t i o nR e c o v e r i n gB e a mS e a r c h ． 2 图表清单 图2 ．1 基于单个解质量的多目标调度算法的评价方法⋯⋯⋯⋯⋯⋯⋯．11 图2 ．2 基于距离的多目标调度算法的评价方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1 图2 ．3p a r e t o 解集的评价( 分布范围和分布性能) ⋯⋯⋯⋯⋯⋯⋯⋯⋯．1 图3 ．1 轮箍生产工艺流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．1 图3 ．2 马钢车轮公司轮箍生产线轧制工序排产界面⋯⋯⋯⋯⋯⋯⋯⋯2 2 图3 ．3 马钢车轮公司轮箍生产线热处理工序排产界面⋯⋯⋯⋯⋯⋯⋯2 3 图3 ．4 马钢车轮公司轮箍生产线检测工序排产界面⋯⋯⋯⋯⋯⋯⋯⋯2 4 图3 ．5 R B S 算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．2 7 图3 ．6 子方向搜索的原理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1 图3 ．7S D R B S 算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯_ ．．1 表4 ．1 每一类测试数据集的构成⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯35 表4 ．2R B S 算法和S D R B S 算法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．38 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。

据我所知，除了文中特别加以标志和致谫十的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得 佥鲤王些达堂 或其他教 育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签字：予糸羡签字E l 期：z 护Ⅳ年够月z7 日 学位论文版权使用授权书 本学位论文作者完全了解 金目巴互些太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅或借阅本人授权 金月壁工业盔堂可以将学位论文的全部或部分论文内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学 位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 隅聚 签字E t 期：砂C 侈年午月z1 日 学位论文作者毕业后去向：’ 工作单位：—k 呖L 通讯地址： 导师签名： 日 e，f-f 7 丹 f ：．． 0 话编 年 电邮 r D ／ 期日字签 致谢 衷心感谢我的导师刘心报教授在论文完成过程中，刘老师在论文 选题、构思及写作的整个过程给予了我不可或缺的帮助，为我的研究工 作指明了方向。

同时，在两年半的研究生求学生涯中，刘老师为我提供 了许多参与实际项目的机会，让我能够学以致用，将书本知识与实际项 目很好地结合起来，使我获益匪浅另外，我也被刘老师治学严谨、孜 孜不倦的精神深深影响，这将成为我今后人生中一笔不可多得的财富 在此，谨向刘老师表示我诚挚的感谢和崇高的敬意! 其次，非常感谢刘林老师、程浩老师和裴凤老师以及周谧老师，他 们在我论文完成过程中提出了很多有效的建议并给予了有力的指导衷 心感谢管理学院各位老师，他们传授的各门课程为我的研究工作打下了 坚实的基础 再次，感谢高先务师兄、冯瑞、刘吴曼、宋旭、张夏梓、黄明达等 在研究生期间给我的关怀和鼓励同时感谢27 班及决策所的所有同学， 集体的温暖永远能给人安定的力量 最后，感谢我的家人，他们的支持一直是我前进的动力! 作者：陈吴 2 0lO 年3 月17 日 1 ．1 研究背景 第1 章绪论 马钢股份有限公司车轮公司是我国生产火车整体碾钢车轮和轮箍的特 大型企业，是亚洲最大的火车车轮生产基地公司经营销售车轮、轮箍、 环件、轮件、盘件、锻件六大系列产品，品种规格达2 0 0 0 多种其中轮箍 系列产品每周需要生产的批量较小，品种较多，且不同的产品对于生产瓶 颈环节一一轧制工序的要求也不尽相同，此外有些产品( 例如军用环件) 对产品的生产周期又有较严格的要求，因此对于轮箍生产的瓶颈环节一一 轧制工序的生产调度有多。