一类多代理流水车间调度问题的合作博弈

Cooperative Games on A Class of Multi-agent Flow-shop Scheduling Problem

对具有多个代理的一类加工时间和工序相关的流水车间调度问题,研究代理之间以合作的方式结成联盟,通过在联盟内重新调度以节省成本。在每个代理的客户服从代理调度的前提下,以最小化客户成本为指标,以代理联盟通过合作获得的最大成本节省为联盟的特征函数,建立多代理流水车间调度问题的合作博弈模型。证明了平均增益分配规则(EGS规则)得到的代理成本分配在合作博弈的核心中。在对客户成本节省进行分配时,由代理通过合作得到的成本节省平均分配给每一个客户,而代理内部客户通过合作得到的成本节省仍然按照EGS规则进行分配,以保证成本分配的公平性及客户合作的稳定性。最后通过算例对所提出的合作博弈模型及成本分配方法进行了验证。

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 use cooperative 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 0 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 0-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.