带有资源冲突的Seru在线并行调度算法  

An Online Algorithm for Parallel Scheduling of Serus With Resource Conflicts

作　　者：江煜舟 李冬妮[1] 靳洪博 殷勇[2] JIANG Yu-Zhou;LI Dong-Ni;JIN Hong-Bo;YIN Yong(Beijing Laboratory of Intelligent Information Technology,School of Computer Science,Beijing Institute of Technology,Beijing 100081,China;Graduate School of Business,Doshisha University,Kyoto 602-0023,Japan)

机构地区：[1]北京理工大学计算机学院智能信息技术北京市重点实验室,北京100081 [2]同志社大学商学院,日本京都602-0023

出　　处：《自动化学报》2022年第2期444-459,共16页Acta Automatica Sinica

基　　金：内蒙古自治区重大基础研究开放课题(GZ2018KF001);国家自然科学基金(61763046)资助。

摘　　要：随着大规模定制的市场需求日趋显著,赛如生产系统(Seru production system,SPS)应运而生,逐渐成为研究和应用领域的热点.本文针对带有资源冲突的Seru在线并行调度问题进行研究,即需要在有限的空间位置上安排随动态需求而构建的若干Seru,以总加权完工时间最小为目标,决策Seru的构建顺序及时间.先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time,AD-SWPT)算法,针对其竞争比不为常数的局限性,引入调节参数,得到竞争比为常数的无资源冲突的Seru在线并行调度算法.接下来,引入冲突处理机制,得到有资源冲突的Seru在线并行调度算法,αAD-I(α-average delayed shortest weighted processing time-improved)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.With the remarkably increase of mass customization,there comes the seru production system(SPS),which has become a hotspot in both the research and the application fields.This paper discusses the online parallel scheduling problem of serus with resource conflicts,which aims at scheduling serus that are generated with dynamic demands on limited space to minimize the total weighted completion time.First,we consider online parallel scheduling of serus without resource conflicts.Based on the average delayed shortest weighted processing time(AD-SWPT)algorithm,an adjustment parameter is introduced and an optimization algorithm with a constant competitive ratio is proposed.Then for online parallel scheduling of serus with resource conflicts,anα-average delayed shortest weighted processing time-improved(αAD-I)algorithm is proposed,whose competitive ratio is proved to be the same as the one without resource conflicts in special cases via instance reduction.Computational experiments are implemented to test and verify the superiority of our algorithm under both special instances and general instances.

关 键 词：赛如生产系统 在线调度 竞争比 实例归约 总加权完工时间 

分 类 号：TH186[机械工程—机械制造及自动化]