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

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