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

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

作　　者：宫华 孙文娟[1,2] 刘鹏 许可[1,2] GONG Hua;SUN Wenjuan;LIU Peng;XU Ke(School of Management,Shenyang University of Technology,Shenyang 110870,China;School of Science,Shenyang Ligong University,Shenyang 110159,China)

机构地区：[1]沈阳工业大学管理学院,辽宁沈阳110870 [2]沈阳理工大学理学院,辽宁沈阳110159

出　　处：《运筹与管理》2023年第4期23-28,60,共7页Operations Research and Management Science

基　　金：辽宁省百千万人才工程资助项目(2019);辽宁省教育厅科学研究经费项目(LG202025,WJGD2020001)。

摘　　要：对具有多个代理的一类加工时间和工序相关的流水车间调度问题,研究代理之间以合作的方式结成联盟,通过在联盟内重新调度以节省成本。在每个代理的客户服从代理调度的前提下,以最小化客户成本为指标,以代理联盟通过合作获得的最大成本节省为联盟的特征函数,建立多代理流水车间调度问题的合作博弈模型。证明了平均增益分配规则(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 proces

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

分 类 号：O225[理学—运筹学与控制论] C931.1[理学—数学]