Abstract:

For solving the critical job-scheduling problem in the service-oriented manufacturing plants, a two level-nested Stackelberg game model was put forward, which was made up of two sub-games, that is, dynamic Stackelberg sub-game and static non-cooperative sub-game. The dynamic Stackelberg sub-game was for the decision between the critical job and non-critical jobs while static non-cooperative sub-game was for the decision among non-critical jobs. In the Stackelberg game model, the leader corresponded to the critical job, and followers corresponded to the non-critical jobs; the strategies of each job corresponded to the alternative machines related to operations of this job; the payoff of each job was defined as its corresponding cost including processing cost, inventory cost, transportation cost, and tardiness cost, etc. Therefore, the optimal scheduling results were determined by the Stackelberg equilibrium point of this game. In order to find the equilibrium point efficiently and effectively, a hybrid adaptive genetic algorithm was designed based on hill-climbing method. A numerical case study demonstrates the validity of the presented game model and its related resolving algorithm.

Key words: service-oriented manufacturing, critical job scheduling, Stackelberg game, Stackelberg equilibrium, hybrid adaptive genetic algorithm

摘要：

针对服务型制造车间关键任务调度问题，提出了两层次嵌套的Stackelberg博弈调度模型。该博弈模型由Stackelberg子博弈与非合作静态子博弈构成。其中Stackelberg子博弈模型用于解决关键任务与非关键任务的之间的调度决策问题，非合作静态子博弈模型则用于实现非关键任务之间的调度决策。在该博弈调度模型中，将关键任务映射为领导者，将其余非关键任务映射为追随者，将与各任务包含的工序集所对应的可选加工设备映射为可行方案集，将各任务的综合成本指标映射为收益函数。为实现对模型的Stackelberg均衡点的有效求解，设计了基于爬山搜索的混合自适应遗传算法。算例仿真结果验证了所提出的模型与解算方法的正确性。

关键词: 服务型制造, 关键任务调度, Stackelberg博弈, Stackelberg均衡, 混合自适应遗传算法