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

随着大规模定制的市场需求日趋显著,赛如生产系统(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)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.

An Online Algorithm for Parallel Scheduling of Serus With Resource Conflicts

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.