考虑共享机器租借费用的在线订单加工策略及竞争分析  

Online Strategy and Competitive Analysis of Production Order Scheduling Problem with Rental Cost of Shared Machines

作　　者：徐寅峰 智荣腾 郑斐峰[1] 刘明 XU Yin-feng;ZHI Rong-teng;ZHENG Fei-feng;LIU Ming(Glorious Sun School of Business and Management,Donghua University,Shanghai 200051,China;School of Economics&Management,Tongji University,Shanghai 200092,China)

机构地区：[1]东华大学旭日工商管理学院,上海200051 [2]同济大学经济管理学院,上海200092

出　　处：《中国管理科学》2023年第4期142-150,共9页Chinese Journal of Management Science

基　　金：国家自然科学基金资助项目(71832001,71771048,71531011,71571134);中央高校基本科研业务费专项资金资助项目;东华大学研究生创新基金资助项目(CUSF-DH-D-2020088)。

摘　　要：探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素,运用在线理论与竞争分析方法构建了平行机调度over-list在线模型,其最小化目标是工件总完工时间与机器租赁总成本之和。针对工件均为单位长度的情形,分析了问题离线最优方案,进而证明了竞争比下界为1+6a-3√12a-3+/18a+(6b+3)√12a-3+6b^(2)+6b-1,其中,a为固定租赁成本系数,b(0≤b<a)为可变租赁成本系数。当a→+∞,b/a→0+时,该下界趋于4/3;同时,设计给出了在线策略TS,并证明当a=2时该策略竞争比为4/3;当a≥3时,其竞争比为1.89。In sharing economics era,it arises a new manufacturing mode where one manufacturer may temporarily rent social processing resources or machines,if necessary,to complete its customer orders and pay a reasonable rental fee.This work investigates an online scheduling problem where one manufacturer owning two parallel identical machines may lease a number of external machines to satisfy its jobs via a manufacturing resource sharing platform.The objective is to minimize the sum of the total completion time of jobs and the total leasing cost of sharing machines,where the rental cost consists of fixed cost and variable cost.The online over-list model is focused on such that jobs with unit processing times are released one by one,and each job has to be assigned on its arrival to one of the currently rented machines for processing without the knowledge of any future jobs.Moreover,the decision on leasing one more external machine may be made concurrently by the manufacturer.Several fundamental properties are presented for an offline optimal solution,and a lower bound 1+6a-3√12a-3+/18a+(6b+3)√12a-3+6b^(2)+6b-1 of competitive ratio is proved,where a and b(0≤ba)are the coefficients of fixed and respectively variable costs,and both are assumed to be integers.The lower bound approaches 4/3,provided that a approaches infinity and the ratio of b to a approaches zero.Secondly,an online algorithm named TS is proposed,which assigns arrival jobs almost evenly between the manufacturer's own machines or between the rented external machines.The difference between the upper bounds of the number of jobs assigned to the above two types of machines is equal to either b or b+1.It is proved that TS is of a competitive ratio of 4/3 for a=2 and 1.89 for a≥3,respectively.The results indicate that when the manufacturer has to make decisions on the processing schedule of jobs and the time points for machine leasing in the online mode,the total cost spent is less than twice of the optimal one.

关 键 词：共享制造 在线调度 平行机调度 竞争比 总完工时间 

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