摘要
【目的】研究在全部工件加工时间可变的情况下具有指数学习效应和凸资源分配的单机排序问题,其中工件的实际加工时间具有指数学习效应,并依赖于分配它的不可再生资源数量。目标是确定资源的最优分配和工件最优排序,使得最大完工时间和资源消耗费用的3种组合最优,即最大完工时间和资源消耗费用的加权和最小、资源消耗费用限制下的极小化最大完工时间和最大完工时间限制下的极小化资源消耗费用问题。【方法】对给定排序,用约束优化和无约束优化问题的最优性条件能够求得其最优资源分配。【结果】分析最优解满足的性质,证明最优解能够通过多项式时间得到,并给出了具体求解算法。【结论】算法分析表明求解算法的时间复杂度为O(nlog n),其中n为工件个数。
[Purposes]The single machine convex resource allocation scheduling problems with exponential learning effects is studied under the case of variable processing time of all the jobs, where the actual processing time of a job has exponential learning effects and depends on the amount of a non-renewable resource allocated to all the jobs. Our goal is to determine the optimal resource allocation and optimal schedule such that the three combinational models of makespan(maximum completion time) and total resource consumption are optimal, that is, to minimize the weighted sum of makespan and total resource consumption cost;to minimize the makespan subject to the total resource consumption cost is limited;to minimize the total resource consumption cost subject to the makespan is limited. [Methods]Under a given schedule, the optimal resource allocation can be obtained by using optimal conditions for constrained and unconstrained optimization problems. [Findings]The optimal properties of the three combinational models can be obtained, it is proved that the optimal solution can be obtained in polynomial time, and the solution algorithm is given. [Conclusions]The algorithm is analyzed, and it is proved that the time complexity is O(nlog n), where n is the number of jobs.
作者
杨舒涵
王吉波
YANG Shuhan;WANG Jibo(School of Science,Shenyang Aerospace University,Shenyang 110136,China)
出处
《重庆师范大学学报（自然科学版）》
CAS
北大核心
2022年第5期24-28,共5页
Journal of Chongqing Normal University:Natural Science
基金
国家自然科学基金(No.71471120)
辽宁省“兴辽英才计划”项目(No.XLYC2002017)。
关键词
学习效应
排序
单机
凸资源分配
learning effect
scheduling
single machine
convex resource allocation
