具有独立安装时间和恶化效应的单机成组排序问题研究

《具有独立安装时间和恶化效应的单机成组排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、殏檪檪檪檪檪檪檪殏檪文章编号：２０９５－１２４８（２０１７）０４－００８２－０６檪殏基檪础科檪学檪与檪工檪程檪檪殏具有独立安装时间和恶化效应的单机成组排序问题研究王吉波，赵伯来（沈阳航空航天大学理学院，沈阳１１０１３６）摘要：研究具有恶化效应且带有准备时间的单机成组排序问题，其中同一组内工件的加工时间具有简单线性恶化效应和独立的常数准备时间，各组之间的调整时间为独立的常数安装时间。目标是确定同一组内工件的排列顺序和各组之间的排列顺序使所有工件的最大完工时间最小。对此问题给出了一个下界和一个启发式算法，即上界，从而可以用分支定界算法来求此问题的最优解。关键词：排序；单机；恶化效应；准备时间

2、；分支定界算法中图分类号：Ｏ２２３；Ｃ９３４文献标志码：Ａｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．２０９５－１２４８．２０１７．０４．０１１Ｒｅｓｅａｒｃｈｏｎｓｉｎｇｌｅ-ｍａｃｈｉｎｅｇｒｏｕｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｉｎｄｅｐｅｎｄｅｎｔｓｅｔｕｐｔｉｍｅｓａｎｄｄｅｔｅｒｉｏｒａｔｉｏｎｅｆｆｅｃｔＷＡＮＧＪｉ-ｂｏ，ＺＨＡＯＢｏ-ｌａｉ（ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ，ＳｈｅｎｙａｎｇＡｅｒｏｓｐａｃｅＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ１１０１３６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｃｏｎｓｉｄｅｒｓａｓｉｎｇｌｅ-ｍａｃｈｉｎｅｇｒｏｕｐｓｃｈｅｄｕｌｉ

3、ｎｇｐｒｏｂｌｅｍｗｉｔｈｄｅｔｅｒｉｏｒａｔｉｏｎｅｆｆｅｃｔａｎｄｒｅａｄｙｔｉｍｅｓ，ｗｈｅｒｅｔｈｅｐｒｏｃｅｓｓｉｎｇｔｉｍｅｏｆａｊｏｂｗｉｔｈｉｎｅａｃｈｇｒｏｕｐｉｓａｓｉｍｐｌｅｌｉｎｅａｒｄｅｔｅｒｉｏｒａｔｉｏｎｅｆｆｅｃｔ，ｒｅａｄ-ｙｔｉｍｅｏｆａｊｏｂｗｉｔｈｉｎｅａｃｈｇｒｏｕｐｉｓａｎｉｎｄｅｐｅｎｄｅｎｔｃｏｎｓｔａｎｔ，ａｎｄｔｈｅｓｅｔｕｐｔｉｍｅｓｏｆｇｒｏｕｐｓａｒｅｉｎｄｅｐｅｎｄｅｎｔｃｏｎｓｔａｎｔｓ．Ｏｕｒｏｂｊｅｃｔｉｖｅｉｓｔｏｄｅｔｅｒｍｉｎｅｔｈｅｓｃｈｅｄｕｌｅｏｆｊｏｂｓｗｉｔｈｉｎｅａｃｈｇｒｏｕｐａｎｄｔｈｅｓｃｈｅｄｕｌ

4、ｅｏｆｇｒｏｕｐｓｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｋｅ-ｓｐａｎ．Ａｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄａｌｇｏｒｉｔｈｍｉｎｃｏｒｐｏｒａｔｉｎｇｗｉｔｈａｌｏｗｅｒｂｏｕｎｄａｎｄａｈｅｕｒｉｓｔｉｃａｌ-ｇｏｒｉｔｈｍ（ｉ．ｅ．，ａｎｕｐｐｅｒｂｏｕｎｄ）ａｒｅｐｒｏｐｏｓｅｄｔｏｆｉｎｄｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｆｏｒｔｈｅｐｒｏｂｌｅｍ．Ｋｅｙｗｏｒｄｓ：ｓｃｈｅｄｕｌｉｎｇ；ｓｉｎｇｌｅ-ｍａｃｈｉｎｅ；ｄｅｔｅｒｉｏｒａｔｉｏｎｅｆｆｅｃｔ；ｒｅａｄｙｔｉｍｅ；ｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄａｌｇｏｒｉｔｈｍ在经典排序中，假设工件的加工时间为常数，成钢坯。当等待时间增

5、加时（即加工开始时间延但在许多实际问题中，工件的加工时间可能与其后），在连铸机上加工的炉次的温度将会降低，从开工时间有着某种联系。如在钢铁制造企业的连而造成炉次加工时间的恶化（如刘鹏等［１］）。具铸－轧制生产过程中，炼钢的基本单元是炉次，它有恶化工件的这类问题在塑料工业、军事以及医是指同一座转炉一次共同冶炼的钢水。在炼钢的疗等其他方面也有着广泛的应用（如Ｂｒｏｗｎｅ和连铸阶段，高温熔融钢水在连铸机底部连续凝固Ｙｅｃｈｉａｌｉ［２］，Ｍｏｓｈｅｉｏｖ［３－４］，Ｊｉ和Ｃｈｅｎｇ［５］，Ｎｇ收稿日期：２０１７－０５－３１基金项目：国家自然科学基金项目（项目编号：７１４７１１２０），沈阳航空航

6、天大学大学生创新创业训练计划项目（项目编号：Ｘ１６１１４０５）作者简介：王吉波（１９７５－），男，辽宁沈阳人，教授，博士后，主要研究方向：生产计划与排序，Ｅ-ｍａｉｌ：ｗａｎｇｊｉｂｏ７５＠１６３．ｃｏｍ。第４期王吉波，等：具有独立安装时间和恶化效应的单机成组排序问题研究８３等［６］，Ｓｕｎ等［７］，Ｐｅｉ等［８］）。关于工件加工时间具有研究了组内工件加工时间和组间安装时间都为开恶化效应的综述，可参考文献Ｇａｗｉｅｊｎｏｗｉｃｚ［９］。工时间的简单恶化函数的排序问题，对加权完工随着市场竞争的日趋激烈，为适应多品种小时间平方和问题与加权等待时间平方和问题，他批量生产方式的需求，成组技术成为

7、排序问题研们分别给出了多项式时间最优算法。Ｌｅｅ等［１９］究领域中的一类热点问题。在成组排序问题中，研究了组内工件加工时间和组间安装时间都为开工件可以分成“类似”工件的工件组。同组的工工时间的简单恶化函数的排序问题，对加权误工件连续加工时，不需要或需要较少的安装时间；不数问题，他们给出了一些优势性质，一个下界，一同组的工件接连加工时，需要一定的或需要较多个启发式算法和分支定界法。并用数值例子进行的安装时间。柔性制造系统的发展给成组技