Abstract: For service-oriented manufacturing firms with multiple production lines and multiple installation teams,the order scheduling problem of Product Service System (PSS) with the earliest allowable service times was studied.With the objective of minimizing the total delivery time of all orders,a mixed integer linear programming model for PSS order scheduling problem was developed,and a modified Iterative Greedy (IG) algorithm was proposed to tackle the problem.In the proposed algorithm,an integer coding and decoding method based on order sequence was designed according to the characteristics of the problem;a modified NEH initialization method based on the earliest allowable service time was proposed;a random neighborhood search method was proposed,which combined the insert neighborhood and swap neighborhood.By embedding the neighborhood search optimization for partial solutions,a destruction,optimization and construction process was proposed as perturbation operator.Based on the roulette wheel selection strategy,a new acceptance criterion was designed.In the simulation experiments,the effectiveness of the proposed local search strategy,perturbation operator and acceptance criteria were verified,and the modified IG algorithm was compared with the classical IG algorithm.The impact of key parameters on the performance of the proposed algorithm was discussed.The results showed that the proposed improved strategies were very effective,and the solution efficiency of the classical IG algorithm was significantly improved.Moreover,the proposed algorithm had good robustness in terms of the number of production lines,the number of installation teams and the earliest allowable service time.

Key words: service-oriented manufacturing, product service system, order scheduling, iterated greedy algorithm, acceptance criterion

摘要： 针对拥有多条生产线和多支安装团队的服务型制造企业,研究了产品服务系统订单的调度问题。以最小化所有订单的交付时间总和为目标,考虑了各订单的最早允许服务时间约束,构建了产品服务系统订单调度问题的混合整数线性规划模型,并设计了改进的迭代贪婪算法进行求解。在该算法中,首先根据问题的特点设计了基于订单排序的整数编码与解码方法,其次基于最早允许服务时间排序提出一种改编NEH初始化方法,然后结合插入邻域和交换邻域提出一种随机邻域搜索算法,并通过嵌入针对部分解的邻域搜索优化提出了一种破坏、优化与重建过程作为扰动算子,最后基于轮盘赌的选择策略设计了一种新的接受准则。在仿真实验中,检验了所提局部搜索算法、扰动算子和接受准则的有效性,并将改进迭代贪婪算法与经典迭代贪婪算法进行了对比分析,同时探讨了关键参数对算法性能的影响。结果表明,所提出的改进策略非常有效,显著提升了改进后迭代贪婪算法的求解效率,且该算法对于生产线数量、安装团队数量和最早允许服务时间等因素均表现出了较好的鲁棒性。

关键词: 服务型制造, 产品服务系统, 订单调度, 迭代贪婪算法, 接受准则