摘要
研究工期指派资源约束排序问题,其中每个任务工期的确定有提前或延误工期费用.目的是求出任务的加工顺序,每个任务的工期和分配给每个任务的资源数量,使得所有任务费用中最大费用取最小值.分两步处理:首先将问题转化为非线性凸规划问题,利用凸规划理论求出任务的资源数量;其次通过求解一系列指派问题确定任务的最优加工顺序,进而求得每个任务的工期.获得了时间复杂性为O(n4)的算法,证明了该算法是最优算法,并给出一个算例说明算法的有效性(其中n为任务数).
A single machine due-date assignment resource restriction and scheduling problem is studied.Each job has a due-date to be decided.Each due-date has an early or tardy cost.The aim is to find job sequence and due-dates,resource amount allocated to each job that minimizes the maximal cost among all jobs,subject to an upper bound on resource amount.Firstly,the problem is converted to a nonlinear convex programming problem.By solving it the resource amount of each job is obtained.Secondly,by sovling a few assignment problems the job seqence is given.Then the due-dates are obtained.An algorithm is presented.It is shown that it is optimal in time O(n4),where n is the number of jobs.An example is given to show how to realize the algorithm.
作者
罗成新
张庚
LUO Cheng-xin;ZHANG Geng(College of General Education,Guangdong University of Science and Technology,Dongguan 523073,China)
出处
《数学的实践与认识》
2021年第18期195-201,共7页
Mathematics in Practice and Theory
基金
国家自然科学基金(1117050)
广东科技学院创新强校工程项目(GKY-2019CQYJ-16)。
关键词
排序
工期费用区间
最大费用
位置负荷
资源分配
scheduling
due-date cost interval
maximal cost
position-dependent workload
resource allocation
