加工时间依赖与位置有关的负荷和资源的工期指派问题

《加工时间依赖与位置有关的负荷和资源的工期指派问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：2095—1248(2017)01—0091—06加工时间依赖与位置有关的负荷和资源的工期指派问题张浩楠，罗成新(沈阳师范大学数学与系统科学学院，沈阳110034)摘要：讨论了带有公共工期且加工时间依赖与有关的位置负荷和资源的单机排序问题。工件的加工时间是一个和资源分配、工件在排序中的位置以及负荷有关的凸函数，所有任务具有一个公共工期。目标是确定最优工期的位置、分配给每个工件的资源和最优的工件排序，使由提前、误工、工期、资源分配构成的总费用最小化。应用指派问题解法给出了时间复杂度为O(，13)的最优算法。关键词：单机排序；资源分配；可控加工时间；依赖位置的负荷；工期

2、中图分类号：0223文献标志码：A·loi：10．3969／j．issn．2095—1248．2017．01．014Due-dateassignmentproblem、树thposition-dependentworkloadandresourceprocessingtimesZHANGHao—nail，LUOCheng—xin(SchoolofMathematicsandSystemsScience，ShenyangNormalUniversity，Shenyang110034，China)Abstract：Weconsideracommondue—dateassignme

3、ntandsinglemachineschedulingprobleminwhichjobprocessingtimehasposition·dependentworkload．Undertheconditionthattheprocessingtimeofajobisaconvexfunctionoftheamountofaresourceallocatedtoitanditspositionintheprocessingsequenceandworkload，alljobshaveacommondue—date．TheobjectiveistOfindtheoptimal

4、due—date，theoptimalre-sourceallocationschemeandtheoptimaljobsequencetominimizethetotalcost，whichinvolvesearliness，tardiness，due—date，andresourceconsumption．Weproposedanefficient0(n3)algorithmtosolvethisas．signmentproblem．Keywords：singlemachinescheduling；resourceallocation；controllableproces

5、singtimes；position—dependentworkload；due-date近年来，带有资源分配和工期指派的单机排序问题倍受关注。在传统的排序问题中，工件的加工时间是一个常数。然而在实际环境中，工件的加工时间可能是一个和资源分配、工件在排序收稿日期：2016—10—24基金项目：国家自然科学基金(项目编号：11171050)；辽宁省教育厅项目(项目编号：L2014433)作者简介：张浩楠(1993一)，女，辽宁锦州人，硕士研究生，主要研究方向：组合最优化，E．mail：zhnagnes@foxmail．com；罗成新(1958一)，男，辽宁新宾人，教授，主要研究

6、方向：组合最优化，E—mail：luochengxin@163．com。92沈阳航空航天大学学报第34卷中位置有关的函数，由此产生一些新型排序问题。WangD等‘1。考虑了带有资源分配和学习效应的单机排序问题并给出多项式算法。LuY—Y等‘2]研究了带有资源分配的单机排序问题。王吉波等口。考虑了具有恶化工件的不同工期指派问题，证明该问题的算法复杂性是多项式时间可解的，并给出了如何求解该问题的最优算法。WangJ—B等‘4。研究了带有公共工期、资源分配以及学习效应的单机指派问题。郭玲等”o讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题，给出了最优解的一些性质，并且证

7、明了这个问题是多项式时间可解的。MosheiovGMl研究了带有学习效应的排序问题。王洪芳等"1研究单机排序下加工时间可变的工期窗口指派问题，任务的加工时间是关于所获资源分配量的一个凸函数，证明了此问题是多项式时间可解的，并给出了最优算法。HeH等坤1研究了带有资源约束和标准截断学习效应的排序问题。NgCT等归。考虑了带有几种公共工期和资源分配的单机排序问题。王吉波等¨叫研究了具有学习效应的单机可控加工时间排序问题，其中工件的加工时间是其所在位置的函数，且与加工时间的控制变量有关，并证明他们都能转化为指