两个代理商松弛工期指派与位置有关负荷资源约束单机排序问题  

A Two-Agent Slack Due-Date Assignment Single Machine Scheduling Problem with Position-Dependent Workload and Resource Constraint

作　　者：罗成新 LUO Chengxin(College of General Education,Guangdong University of Science and Technology,Dongguan Guangdong 523073,China)

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

出　　处：《重庆师范大学学报（自然科学版）》2022年第6期1-8,共8页Journal of Chongqing Normal University:Natural Science

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

摘　　要：【目的】研究两个代理商松弛工期指派资源约束单机排序问题。【方法】代理商通过竞争在同一台处理机上处理各自任务集合,各有一定数量的资源可以分派给任务。任务有待定的松弛工期,处理时间与位置有关且是所获资源量的凸函数。目标是求出任务的处理顺序、工期和资源分配方案,使得乙代理商任务中最大费用不超过给定值,且甲代理商任务最大费用取最小值。将问题转化为凸规划问题,先求出任务资源数量;再通过求解指派问题确定任务的处理顺序,进而求得工期。【结果】给出了多项式时间的最优算法,提供算例说明算法的有效性。【结论】分析表明算法的计算时间复杂度为O(n~3),其中n为两个代理商任务数中较大的一个。[Purposes]A two-agent slack due-date assignment single machine scheduling problem with position-dependent workload and resource constraint is studied. [Methods]Agents compete on the use of a common processor to process their own set of jobs. Each agent has some resource to allocate to its jobs. Each job has a slack due-date to be decided. The processing time of a job is position-dependent and is convex in resource amount allocated. The goal is to find the joint job sequence and due-dates, resource amount allocated to each job that minimizes the maximal cost among all jobs of the one agent, subject to an upper bound on the maximal cost of the second agent. The problem is converted to a convex programming problem. By solving it the resource allocation policy is obtained. The optimal job sequence is obtained by solving two assignment problems. Then the due-dates are obtained. [Findings]An optimal algorithm is presented in polynomial time. Two examples are provided to show the efficiency of the algorithm. [Conclusions]The analysis shows that the time complexity of our algorithm is O(n~3), where n is the bigger number of jobs between the two agents.

关 键 词：排序 双代理商 松弛工期 位置负荷 资源分配 

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