具有时间与位置相关的两类平行机排序问题  

Scheduling problem with time-and-position-dependent effect on two parallel machines environments

作　　者：苟燕 戴秦 张新功 GOU Yan;DAI Qin;ZHANG Xingong(Bureau of Civil A airs,Junlian Yibin 645250,Sichuan,Chin;Department of Economy and Management,Shanghai University of Electric Power,Shanghai 200090,China;College of Mathematics Science,Chongqing Normal University,Chongqing 401331,China)

机构地区：[1]四川省宜宾市筠连县民政局,四川宜宾645250 [2]上海电力大学经济管理系,上海200090 [3]重庆师范大学数学科学学院,重庆401331

出　　处：《运筹学学报》2019年第4期86-94,共9页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11971443,715610007);重庆市教委研究生教改重点项目(No.yjg182019);重庆市科委自然科学基金(No.cstc2018jcyjAX063)

摘　　要：研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n^k+2)/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n^k-1)/((k-1)!).This paper studies parallel-machine scheduling problems with time-andposition effect and maintenance restrictions,which parallel-machine environments are only involved with the identical parallel machines and unrelated machines.The actual processing time of the job is the function of position and time,and machines need to be maintained.Objective function is consisted of total machine load,total completion time and total waiting time.Under unrelated machines,the proposed problem can be solved by transferring into assignment problem,which its time complexity is O(n^k+2)/((k-1)!).Under identical parallel machines,the proposed problem can be solved by matching algorithm,which its time complexity is O((2 n+m+n log n)n^k-1)/((k-1)!).

关 键 词：排序 平行机 时间与位置效应 维修活动 

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