具有公共流、退化效应与维护和资源分配的单机窗口排序问题

《具有公共流、退化效应与维护和资源分配的单机窗口排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：2095-1248（2016）05-0082-06具有公共流、退化效应与维护和资源分配的单机窗口排序问题赵崴羽，罗成新（沈阳师范大学数学与系统科学学院，沈阳110034）摘要：考虑具有公共流、退化效应与维护和资源分配的单机窗口排序问题，所有任务都具有松弛窗口。在实际加工过程中，为提高生产效率，提供给每个任务不同的资源，资源总量有限，并适时对机器进行维护，一旦维护活动结束，机器恢复到最初状态并且任务的退化效应更新。机器维护持续的时间取决于维护活动的开始时间。假定任务的实际加工时间是关于任务排序位置及资源分配的凸函

2、数，目标是确定任务的窗口、资源分配、任务排序使得提前惩罚、延误惩罚、窗口位置、窗口宽度、时间表长、任务完工时间之和惩罚及资源消耗费用之和最小。给出一个最优算法求解该问题。关键词：排序；退化效应；退化维护；资源分配；窗口；公共流中图分类号：Ｏ223文献标志码：Ａdoi：10．3969／ｊ．ｉｓｓｎ．2095-1248．2016．05．015ASingle-machinedue-windowassignmentschedulingbasedoncommonflowallowancewithdeterioratingeffec

3、t，maintenanceactivityandresourceallocationＺＨＡＯＷｅｉ-ｙｕ，ＬＵＯＣｈｅｎｇ-ｘｉｎ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＳｈｅｎｙａｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ110034，Ｃｈｉｎａ）Abstract：Ｔｈｉｓｐａｐｅｒｃｏｎｓｉｄｅｒｅｄａｓｉｎｇｌｅ-ｍａｃｈｉｎｅｄｕｅ-ｗｉｎｄｏｗａｓｓｉｇｎｍｅｎｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｂａｓｅｄｏｎａｃｏｍｍｏｎｆｌｏｗａｌｌｏｗａｎｃｅ.Ｉｎｏｒｄｅ

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

5、ｅｏｆａｊｏｂｗａｓａｃｏｎｖｅｘｆｕｎｃｔｉｏｎｏｆｉｔｓｐｏｓｉｔｉｏｎａｎｄｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ．Ｔｈｅｏｂｊｅｃｔｉｖｅｗａｓｔｏｆｉｎｄｔｈｅｃｏｍｍｏｎｆｌｏｗａｌｌｏｗａｎｃｅ，ｔｈｅｄｕｅ-ｗｉｎｄｏｗｓｉｚｅ，ｔｈｅｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎａｎｄｔｈｅｊｏｂｓｅｑｕｅｎｃｅｗｈｉｃｈｍｉｎｉｍｉｚｅｓｔｈｅｔｏｔａｌｃｏｓｔｏｆｅａｒｌｉｎｅｓｓ，ｔａｒｄｉｎｅｓｓ，ｔｈｅｓｔａｒｔｉｎｇｔｉｍｅｏｆｄｕｅ-ｗｉｎｄｏｗ，ｔｈｅｓｉｚｅｏｆｄｕｅ-ｗｉｎｄｏｗ，ｍａｋｅｓｐａ

6、ｎ，ｔｈｅｔｏｔａｌｏｆｃｏｍｐｌｅｔｉｏｎｔｉｍｅｏｆａｌｌｊｏｂｓ，ａｎｄｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ．Ｗｅｉｎｔｒｏｄｕｃｅａｎｅｆｆｉｃｉｅｎｔａｌｇｏ-ｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍ．Keywords：ｓｃｈｅｄｕｌｉｎｇ；ａｇｉｎｇｅｆｆｅｃｔ；ｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙ；ｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ；ｄｕｅ-ｗｉｎｄｏｗ；ｃｏｍｍｏｎｆｌｏｗａｌｌｏｗａｎｃｅ收稿日期：2016-06-28基金项目：国家自然科学基金（项目编号：11171050）；辽宁省教育厅项目（项

7、目编号：Ｌ2014433）作者简介：赵崴羽（1992-），女，辽宁朝阳人，硕士研究生，主要研究方向：组合最优化与随机运筹学，Ｅ-ｍａｉｌ：ｚｗｙｈｏｕｓｅ@ｑｑ．ｃｏｍ；罗成新（1958-），男，辽宁新宾人，教授，主要研究方向：组合最优化与随机运筹学，Ｅ-ｍａｉｌ：ｌｕｏｃｈｅｎｇｘｉｎ@163.ｃｏｍ。第5期赵崴羽，等：具有公共流、退化效应与维护和资源分配的单机窗口排序问题83经典排序中，任务的加工时间是固定的常数，时刻已全部到达，所有任务加工不可中断，在一台但在实际生产中，任务等待或机器等原因都会引机器上进行加工。考

8、虑凸函数模型：起任务加工时间的增长，即任务的实际加工时间珔ｐｒａｊｋｊｐ=（1）与该任务的开始加工时间有关［1］，因此，适时地ｊｕｊ对机器进行检修能提高机器的生产效率。通常情其中ｐｊ表示任务Ｊｊ的实际加工时间，珔ｐｊ表示况下，给任务分配一定额度资源，任务的加工时间任务Ｊｊ的正常加工时间，ｒ表示任务Ｊｊ在排序π变小