关键词: 多代理, 流水车间调度, 合作博弈, EGS规则, 成本分配

Abstract: Flow-shop scheduling problem is one of the most widely studied problems in the field of industrial production. It is a simplified model of many actual assembly line production scheduling problems. It is widely used in discrete manufacturing industry and process industry. Multi-agent production scheduling refers to that multiple agents with different customers compete for equipment resources to process their customers’ jobs. The traditional multi-agent production scheduling generally takes the production enterprise as the main body. According to the production environment, delivery time, processing capacity and other constraints, the agents and their jobs are uniformly scheduled to achieve the optimal overall objectives, such as the maximum completion time (makespan), earliness and tardiness penalties, total weighted completion time,etc. In actual production, jobs of different agents may come from different customers, who have their own needs and optimization goals. In the case of limited resources, agents or customers may form an coalition by cooperation, and optimize scheduling within the coalition,so as to reduce production costs or gain more profits. Therefore, it is of practical significance to usecooperative game theory to study the multi-agent production scheduling problem.
In the field of production scheduling, Curiel et al. first applied cooperative sequencing games to single machine scheduling problem. They consider that there are n agents, each agent has a job to be processed, and the cost of each agent is a linear function of the job’s completion time. It is proved that the core of the cooperative sequencing game on the single machine scheduling problem is nonempty. On this basis, cooperative sequencing games are extended to multi-agent flow-shop scheduling problem in this paper.
In a class of multi-agent flow-shop scheduling problem studied in this paper, there are g agents, and each agent has multiple jobs belonging to different customers to be processed. Each job needs to be processed through m processes and has the same processing path. There is only one machine for each process. The processing time of each job on each machine is known and related to the process, that is, the processing time of each job in the same process is the same.
In this paper, we consider that the customer’s cost function is linearly weighted with job’s completion time, and the agents form an initial processing order σ^A₀ based on their arrival time. Some agents can form an coalition by cooperation, and total costs of agents can be saved by rescheduling within the coalition. Under the premise that customers are subject to the agent’s scheduling, a cooperative game model of multi-agent flow-shop scheduling problem is established with minimizing total customers’ costs as an optimization objective. In the game model, the agents are taken as the players, and the maximum cost savings obtained from the cooperation of agents is taken as the worth of the coalition. It is proved that the cooperative games of multi-agent flow-shop scheduling problem with the equal processing time on the same process for each job are superadditive and σ^A₀-component additive. The cost savings allocation of agents obtained by the Equal Gain Splitting rule (EGS rule) is a core element of the game. When allocating customers’ cost savings, the cost savings obtained from the agents by cooperation are equally distributed to each customer, and the cost savings obtained from the customers by cooperation are also distributed according to the EGS rule to ensure the fairness of cost allocation method and the stability of customers’ cooperation. Finally, the properties of cooperative games and cost allocation method proposed in this paper are verified by an example.
In the future, we will pay more attention to the general flow-shop scheduling problems and other production scheduling problems with more complex shop environment.With the goal of minimizing the nonlinear costs of multiple customers, we will use cooperative game theory to study the scheduling problems, analyze the properties of cooperative games and design reasonable cost allocation methods.

Key words: multi-agent, flow-shop scheduling, cooperative games, EGS rule, cost allocation