具有时间区间惩罚工期指派资源约束最大费用最小化排序问题  

Minmax Due-Date Assignment and Scheduling Problem with Due-Date Window Cost and Resource Restriction

作　　者：罗成新 张庚[1] LUO Cheng-xin;ZHANG Geng(College of General Education,Guangdong University of Science and Technology,Dongguan 523073,China)

机构地区：[1]广东科技学院通识教育学院,广东东莞523073

出　　处：《数学的实践与认识》2021年第18期195-201,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(1117050);广东科技学院创新强校工程项目(GKY-2019CQYJ-16)。

摘　　要：研究工期指派资源约束排序问题,其中每个任务工期的确定有提前或延误工期费用.目的是求出任务的加工顺序,每个任务的工期和分配给每个任务的资源数量,使得所有任务费用中最大费用取最小值.分两步处理:首先将问题转化为非线性凸规划问题,利用凸规划理论求出任务的资源数量;其次通过求解一系列指派问题确定任务的最优加工顺序,进而求得每个任务的工期.获得了时间复杂性为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.

关 键 词：排序 工期费用区间 最大费用 位置负荷 资源分配 

分 类 号：O223[理学—运筹学与控制论]