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

doi:10.16381/j.cnki.issn1003-207x.2020.1663

摘要/Abstract

摘要： 探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素，运用在线理论与竞争分析方法构建了平行机调度over-list在线模型，其最小化目标是工件总完工时间与机器租赁总成本之和。针对工件均为单位长度的情形，分析了问题离线最优方案，进而证明了竞争比下界为1+6a－312a－3+118a+(6b+3)12a－3+6b2+6b－1，其中，a为固定租赁成本系数，b(0≤b<a)为可变租赁成本系数。当a→+∞，b/a→0+时，该下界趋于4/3；同时，设计给出了在线策略TS，并证明当a=2时该策略竞争比为4/3；当a≥3时，其竞争比为1.89。

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

Abstract: 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－312a－3+118a+(6b+3)12a－3+6b2+6b－1 of competitive ratio is proved, where a and b (0≤b<a) 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.

Key words: shared manufacturing; online scheduling; parallel machine scheduling; competitive analysis; total completion time

中图分类号:

O224

徐寅峰, 智荣腾, 郑斐峰, 刘明. 考虑共享机器租借费用的在线订单加工策略及竞争分析[J]. 中国管理科学, 2023, 31(4): 142-150.

XU Yin-feng, ZHI Rong-teng, ZHENG Fei-feng, LIU Ming. Online Strategy and Competitive Analysis of Production Order Scheduling Problem with Rental Cost of Shared Machines[J]. Chinese Journal of Management Science, 2023, 31(4): 142-150.

参考文献

［1］工业和信息化部. 关于加快培育共享制造新模式新业态促进制造业高质量发展的指导意见［EB/OL］. (2019-10-29). https://www.miit.gov.cn/jgsj/zfs/wjfb/art/2020/art_43afa5054df84d7499fd71ef05176ee7.html.Ministry of Industry and Information Technology. Guiding opinions on accelerating the cultivation of new models and forms of shared manufacturing to promote high quality development of the manufacturing industry［EB/OL］. (2019-10-29). https://www.miit.gov.cn/jgsj/zfs/wjfb/art/2020/art_43afa5054df84d7499fd71ef05 176ee7.html.
［2］国家信息中心. 2018中国制造业产能共享发展年度报告［EB/OL］. (2018-2-27) ［2018-3-8］. http://www.199it.com/archives/697457.html.The State Information Center. Annual report on China’s manufacturing capacity sharing development in 2018［EB/OL］. (2018-2-27) ［2018-3-8］. http://www.199it.com/archives/697457.html.
［3］国家信息中心分享经济研究中心. 中国共享经济发展报告(2020)［EB/OL］. (2020-3-4) ［2020-3-9］.http://www.sic.gov.cn/News/568/10429.htm.The Sharing Economy Research Center under the State Information Center. Report on the development of China’s sharing economy［EB/OL］.(2020-3-4) ［2020-3-9］. http://www.sic.gov.cn/News/568/10429.htm.
［4］ Liu Ning, Li Xiaoping, Shen Weiming. Multi-granularity resource virtualization and sharing strategies in cloud manufacturing［J］. Journal of Network and Computer Applications, 2014,46:72-82.
［5］ Liu Yongkui, Zhang Lin, Tao Fei, et al. Resource service sharing in cloud manufacturing based on the Gale-Shapley algorithm: advantages and challenge［J］. International Journal of Computer Integrated Manufacturing, 2017,30(4-5):420-432.
［6］齐二石，李天博，刘亮，等. 云制造环境下企业制造资源共享的演化博弈分析［J］. 运筹与管理, 2017,26(2):25-34.Qi Ershi, Li Tianbo, Liu Liang, et al. The evolutionary game analysis of the sharing of manufacturing resource in the environment of cloud manufacturing［J］. Operations Research and Management Science, 2017,26(2):25-34.
［7］ Argoneto P, Renna P. Supporting capacity sharing in the cloud manufacturing environment based on game theory and fuzzy logic［J］. Enterprise Information Systems, 2016,10(2):193-210.
［8］赵道致, 杜其光. 供应链中需求信息更新对制造能力共享的影响［J］. 系统管理学报, 2017,26(2):374-380+389.Zhao Daozhi, Du Qiguang. The impact of demand information updating on sharing of manufacturing capacity in the supply chain［J］. Journal of Systems & Management, 2017,26(2):374-380+389.
［9］ Li Kai, Zhou Tao, Liu Bohai, et al. A multi-agent system for sharing distributed manufacturing resources［J］. Expert Systems with Applications, 2018,99:32-43.
［10］ Jiang Yiwei, Hu Jueliang, Liu Longcheng, et al. Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost［J］. Information Sciences, 2014,269:128-141.
［11］ Akaria I, Epstein L. An optimal online algorithm for scheduling with general machine cost functions［J］. Journal of Scheduling, 2020,23:155-162.
［12］ Ma Ran, Yuan Jinjiang. Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines［J］. Journal of the Operations Research Society of China, 2016,4(1):111-119.
［13］ Ma Ran, Yuan Jinjiang. Online scheduling to minimize the total weighted completion time plus the rejection cost［J］. Journal of Combinatorial Optimization, 2017,34:483-503.
［14］ Dai Bingfei, Li Weidong. Vector scheduling with rejection on two machines［J］. International Journal of Computer Mathematics, 2020,97(12):2507-2515.
［15］ Karp R M. Online algorithms versus offline algorithms: how much is it worth to know the future?［C］//Proceedings of IEIP 12th World Computer Congress on Madrid, Spain, September 7-11, 1992.
［16］陈晓丽, 徐维军, 刘幼珠. 考虑复利的三种策略选择在线租赁模型及其竞争分析［J］. 系统工程, 2016,34(7):118-124.Chen Xiaoli, Xu Weijun, Liu Youzhu. Online leasing strategy and competitive analysis for three-slope rental problem based on compound interest［J］. Systems Engineering, 2016,34(7):118-124.
［17］陈晓丽, 徐维军. 复利下二重在线租赁竞争策略及风险补偿模型［J］. 系统工程理论与实践, 2016,36(9):2284-2292.Chen Xiaoli, Xu Weijun. Competitive strategy and risk-reward model with compound rate for online fashion A-B leasing problem［J］. Systems Engineering-Theory & Practice, 2016,36(9):2284-2292.
［18］张卫国, 张永, 徐维军, 等. 随机选择设备获得方式的可折旧设备在线租赁［J］. 管理科学学报, 2013,16(4):1-7.Zhang Weiguo, Zhang Yong, Xu Weijun, et al. Online leasing of depreciable equipment based on randomization of obtaining methods［J］. Journal of Management Sciences in China, 2013,16(4):1-7.
［19］ Feng Xin, Xu Yinfeng, Ni Guanqun, et al. Online leasing problem with price fluctuations under the consumer price index［J］. Journal of Combinatorial Optimization, 2018,36(2):493-507.
［20］徐维军, 董鹏翠, 彭子衿. 基于优惠合同的在线租赁策略设计［J］. 运筹与管理, 2019,28(3):183-190.Xu Weijun, Dong Pengcui, Peng Zijin. The design of online leasing strategy based on the preferential contract［J］. Operations Research and Management Science, 2019,28(3):183-190.
［21］杨兴雨, 张卫国, 徐维军, 等. 基于绩效比和合同约束的多阶段在线租赁［J］. 中国管理科学, 2014,22(2):94-100.Yang Xingyu, Zhang Weiguo, Xu Weijun, et al. Multi-period online leasing problem based on performance ratio and constraint［J］. Chinese Journal of Management Science, 2014,22(2):94-100.
［22］徐维军, 刘幼珠, 陈晓丽, 等. 通胀市场下多设备租赁的在线策略分析［J］. 中国管理科学, 2016,24(2):69-75.Xu Weijun, Liu Youzhu, Chen Xiaoli, et al. Competitive Strategy for on-line multiple devices leasing in an inflation market［J］. Chinese Journal of Management Science, 2016,24(2):69-75.
［23］ Hu Jueliang, Jiang Yiwei, Zhou Ping, et al. Total completion time minimization in online hierarchical scheduling of unit-size jobs［J］. Journal of Combinatorial Optimization, 2017,33:866-881.

[1]	邹清明, 胡李庆, 邹霆钧. 碳限额与碳交易机制下考虑公平关切的供应链定价与协调研究[J]. 中国管理科学, 2022, 30(10): 142-154.
[2]	代业明, 齐尧, 高红伟, 李陆. 基于PMSC管理及奖惩机制的智能电网实时定价研究[J]. 中国管理科学, 2022, 30(7): 88-98.
[3]	陈刚, 付江月. 灾后不确定需求下应急医疗移动医院鲁棒选址问题研究[J]. 中国管理科学, 2021, 29(9): 213-223.
[4]	马浚洋, 黄晓霞, 傅颖诗, 周晓光. 复杂不确定环境下考虑代理人通过努力减少项目持续期限的最优代理合同[J]. 中国管理科学, 2021, 29(5): 138-146.
[5]	郑斐峰, 靳凯媛, 张娥, 刘明. 考虑订单类型的两台平行批处理机在线调度模型研究[J]. 中国管理科学, 2021, 29(5): 173-179.
[6]	郭东威, 丁根宏, 刘伟. 带时间窗装卸货问题的改进多策略分组编码遗传算法[J]. 中国管理科学, 2020, 28(7): 204-211.
[7]	宋鸿芳, 褚宏睿, 张文思. 基于患者两阶段医疗服务过程的病床资源优化[J]. 中国管理科学, 2020, 28(3): 93-102.
[8]	李京, 王国庆, 朱建明, 徐康. 冰雪灾害背景下电网投资优化和韧性提升模型[J]. 中国管理科学, 2020, 28(3): 122-131.
[9]	张伸, 孟庆春, 安国政. 电商平台扣点率影响下的双渠道供应链协调定价研究[J]. 中国管理科学, 2019, 27(10): 44-55.
[10]	苏强, 杨微, 王秋根. 考虑空间随机需求的急救站点选址规划[J]. 中国管理科学, 2019, 27(10): 110-119.
[11]	孙立缘, 罗建强, 杨慧. 面向价值共创的服务衍生供需决策优化研究[J]. 中国管理科学, 2019, 27(9): 160-168.
[12]	陶莉, 高岩, 朱红波, 曹磊. 有可再生能源和电力存储设施并网的智能电网优化用电策略[J]. 中国管理科学, 2019, 27(2): 150-157.
[13]	万骁乐, 郝婷婷, 戎晓霞, 孟庆春. 共创视角下考虑开放式创新的供应链价值创造研究[J]. 中国管理科学, 2017, 25(7): 57-66.
[14]	颜瑞, 朱晓宁, 张群, 戚耀元, 蔺俞铮. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67-77.
[15]	彭春, 李金林, 王珊珊, 冉伦. 多类应急资源配置的鲁棒选址-路径优化[J]. 中国管理科学, 2017, 25(6): 143-150.