具有维护活动及公共工期的加工时间依赖资源的单机排序问题

《具有维护活动及公共工期的加工时间依赖资源的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：2095-1248（2016）06-0090-07具有维护活动及公共工期的加工时间依赖资源的单机排序问题隋楠，罗成新（沈阳师范大学数学与系统科学学院，沈阳110034）摘要：研究在工件的提前惩罚、延误惩罚等总费用受限的前提下，最小化资源费用的单机排序问题。所有工件具有一个公共工期，工件的加工时间是关于位置与资源的具有退化效应的凸函数。在加工过程中，存在一次维护活动。考虑维护活动对依赖于资源的加工时间的影响，确定最优资源分配、最优公共工期、最优维护位置及维护持续时间，并给出一个求得最小资源费用的多项式时间最优算法。关键词：排序；维护活

2、动；工期；资源分配；退化效应中图分类号：Ｏ223文献标志码：Ａdoi：10．3969／ｊ．ｉｓｓｎ．2095-1248．2016．06．015Singlemachineschedulingwithjob-dependentandmaintenanceactivitiesandprocessingtimedependentonresourceswithdue-dateＳＵＩＮａｎ，ＬＵＯＣｈｅｎｇ-ｘｉｎ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＳｈｅｎｙａｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ

3、110034，Ｃｈｉｎａ）Abstract：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｓｔｕｄｙｔｈｅｓｉｎｇｌｅｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｏｆｍｉｎｉｍｉｚｉｎｇｒｅｓｏｕｒｃｅｃｏｓｔｓｕｎｄｅｒｔｈｅｃｏｎｄｉｔｉｏｎｓｔｈａｔｔｈｅｅａｒｌｉｎｅｓｓ，ｔａｒｄｉｎｅｓｓａｎｄｏｔｈｅｒｐｅｎａｌｔｉｅｓａｒｅｌｉｍｉｔｅｄ．Ａｌｌｔｈｅｊｏｂｓｈａｖｅａｃｏｍｍｏｎｄｕｅ-ｄａｔｅ，ａｎｄｔｈｅａｃｔｕａｌｐｒｏｃｅｓｓｉｎｇｔｉｍｅｓａｒｅｄｅｆｉｎｅｄｂｙａｃｏｎｖｅｘｆｕｎｃｔｉｏｎｏｆｔｈｅｉｒｎｏｒｍａｌｐｒｏｃｅｓ

4、ｓｉｎｇｔｉｍｅｓ，ｐｏｓｉ-ｔｉｏｎｓａｎｄｔｈｅｅｆｆｅｃｔｉｎｄｅｘｏｆｄｅｔｅｒｉｏｒａｔｉｎｇａｎｄｒｅｓｏｕｒｃｅｓ．Ｔｈｅｒｅｉｓａｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙｉｎｔｈｅｐｒｏｃｅｓｓｉｎｇ．Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｅｆｆｅｃｔｏｎｔｈｅｐｒｏｃｅｓｓｉｎｇｔｉｍｅｏｆｒｅｓｏｕｒｃｅｆｒｏｍｍａｉｎｔｅｎａｎｃｅ，ｗｅｇｉｖｅｔｈｅｏｐｔｉｍａｌｒｅｓｏｕｒｃｅａｌ-ｌｏｃａｔｉｏｎ，ｔｈｅｏｐｔｉｍａｌｄｕｅ-ｄａｔｅ，ｔｈｅｏｐｔｉｍａｌｐｌａｃｅｆｏｒｍａｉｎｔｅｎａｎｃｅａｎｄｔｈｅｌａｓｔｉｎｇｔｉｍｅ

5、ｏｆｍａｉｎｔｅｎａｎｃｅ．Ａｎｏｐ-ｔｉｍａｌｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｍｉｎｉｍｕｍｒｅｓｏｕｒｃｅｃｏｓｔｉｓｇｉｖｅｎ．Keywords：ｓｃｈｅｄｕｌｉｎｇ；ｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｉｅｓ；ｄｕｅ-ｄａｔｅ；ｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ；ｄｅｔｅｒｉｏｒａｔｉｎｇｅｆｆｅｃｔ排序问题是一类重要的组合最优化问题，多适当地分配给工件一定的资源，使其加工效率提年来人们一直在运筹学、计算机科学、管理科学等高，加工时间缩短。领域进行着该问题的研究。在经典排序模型中，近20年，由于现代运营管理

6、等产业的引进，工件的加工时间是一个独立的且与加工位置和资具有公共工期的排序问题陆续进入人们的视野。源无关的常数，但在实际问题中，工件的加工时间如果一个工件在它的工期之前完成加工，那么它可能会在机器的维护作用下相应缩短，或者通过需要承担一部分的提前惩罚费用，相应的，如果一收稿日期：2016-10-28作者简介：隋楠（1992-），女，辽宁铁岭人，硕士研究生，主要研究方向：组合最优化与随机运筹学，Ｅ-ｍａｉｌ：ｎａｎｎａｎ879@126．ｃｏｍ。第6期隋楠，等：具有维护活动及公共工期的加工时间依赖资源的单机排序问题91个工件在它的工期之后完成加工

7、，那么它需要承工件Ｎ＝｛Ｊ，Ｊ，…，Ｊ｝要在一台机器上加工，在12ｎ担一部分的延误惩罚费用。文献［6］首先研究了同一时刻机器最多只能加工一个工件，工件必须带有公共工期的排序问题，目标是最小化提前惩连续加工不允许中断。每个工件Ｊ（ｊ＝1，2，…，ｎ）ｊ罚、延误惩罚和工期的总费用。自此之后，在不同的基本加工时间为ｐ，退化指数为ａ且ａ＞0。在ｊｊｊ环境下的带有公共工期的排序问题被陆续研究许多资源分配的问题中，线性资源消耗函数不能着。恰当地反应资源减少的规律，为了克服这一问题，文献［4］首先研究了带有退化效应的排序问ｐｒａｊｋＡｊ应用如下的凸资源消耗

8、函数：ｐ（ｕ）＝。ｊｒｊ题。由于实际生产的需要，维护问题越来越受重ｕｊ视。为了更好地提高机器的运行效率，需要对机考虑到机器的退化，我们假设有且只有一个维修器进行