Abstract: With the application of intelligent Internet and personalized consumption, manufacturing and service industries have started paying attention to providing personalized service for customers via network information platform. It drives a new service model where product and service designers interact with multiple customers simultaneously in online fashion. According to the interference of service efficiency between parallel tasks of the same designer, this paper describes the problem as a new scheduling model where parallel machine processing rate is influenced by other machines, and the objective of the model is to minimize the total completion time. First of all, for the case where there are only two designers and each designer can deal with at most two parallel tasks at any time, we put forward a modified SPT rule and prove its optimality by the induction method. Then we relax the task assignment requirement of the modified SPT rule, and show that it still keeps the optimality of solution after the relaxation. Finally, we generalize the conclusion to the case with more than two designers. The study provides a theoretical support for constructing effective scheduling strategies in online personalized service applications.

Key words: order scheduling, SPT rule, mathematical induction, parallel machine scheduling

摘要： 随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。

关键词: 订单排序, SPT规则, 归纳法, 平行机调度