运筹与管理2024，Vol.33Issue(12)：115-121,7.DOI:10.12005/orms.2024.0394
基于合作博弈的批处理机生产与成批运输协调调度
Coordinated Scheduling of Production and Batch Transportation with Batch-processing Machine Based on Cooperative Games
摘要
Abstract
In the production process of the process industry,there are many complicated processes.The continu-ous production processes require the coordination of production and transportation scheduling.The coordinated scheduling problem of batch production and batch delivery(CSP-BPBD)has a wide range of application scenari-os in process industries such as iron and steel industry. The CSP-BPBD is described as follows:there are n jobs belonging to different customers,each of which needs to be processed on an identical batching machine with production capacity limits and then transported in batches by a transporter with limited capacity to the downstream process(or a customer).Furthermore,there is an initial processing order on the jobs of customers.It takes the same time for the batching machine to produce a batch of jobs and the same time for the transporter to transport a batch of jobs,which are independent of the number of jobs in the batch.Considering that jobs are willing to form a coalition by cooperation and rearrange their processing and transportation orders to gain cost savings,we can allocate the cost savings reasonably,so that all customers in the coalition can benefit.Therefore,it is of certain practical significance to study a coordi-nated scheduling problem of production and transportation by taking a cooperative game theoretical approach. In this paper,we take the cooperative game theory to study CSP-BPBD.The customer's cost is defined as a linear function of the job's completion time.The cooperative game models are proposed for CSP-BPBD with jobs as players and the maximal cost savings of the coalition as the characteristic function.For two different cases of whether the transporter delivers jobs in full batch or not,the properties of corresponding games are analyzed,and some fair and stable allocations of cost savings are presented. Firstly,the conditions of feasible schedule scheme and optimal schedule scheme are given.For each sched-uling order,there can be different feasible schedule schemes corresponding to it,and each feasible schedule scheme corresponds to only one scheduling order.The optimal schedule scheme π∗ must satisfy the following conditions: (1)π∗is a feasible schedule scheme arranged in non-increasing order according to the cost coefficient of the job; (2)The jobs are processed in full batch on the batching machine with no idle time. Secondly,considering whether the transporter delivers jobs in full batch or not,the sets of admissible schedule schemes are defined for a CSP-BPBD sequencing situation,and the corresponding cooperative games(N,vk)(k=1,2)are defined,where N is the set of players(or jobs),vk(k=1,2)is the maximal cost savings of coalition for two different ways of transportation. Some properties of the games are obtained,and the cost of each job can be reduced by reasonable and stable cost saving allocations.It is proved that,when the transporter delivers jobs in full batch,the cooperative game(N,v1)has no externalities(the cost savings of the coalition are not affected by the jobs outside)and is σ0-component additive,and then the characteristic function v1 can be written as the unique linear combination of unanimity games.Since unanimity games are convex,we show these coefficients of the linear combination are nonnegative,and the game(N,v1)is convex.That is to say,the bigger the coalition,the greater the marginal cost savings for(N,v1).Both the β rule and the Shapley value can give a core element of a cooperative game(N,v1).Moreover,the Shapley value can be expressed in a simple and computable form in this case.Numeri-cal examples are given to verify the correctness of the conclusions.However,when there is no need for full batch transportation,it is obtained that the cooperative game(N,v2)has externalities.A counterexample is provided to show the game(N,v2)need not be σ0-component additive or convex.In this case,there is no guarantee that the core is nonempty,and these games need to be further studied. For future research,we will pay attention to the general CSP-BPBD and other coordinated scheduling problems in complex production and transportation environment,analyze the properties of cooperative games in different ways of cooperation,and design reasonable and stable allocations of cost savings.关键词
批处理机/批运输/合作博弈/Shapley值/核心分配Key words
batching machine/batch delivery/cooperative game/Shapley value/core allocation分类
数理科学引用本文复制引用
孙文娟,刘鹏,宫华..基于合作博弈的批处理机生产与成批运输协调调度[J].运筹与管理,2024,33(12):115-121,7.基金项目
辽宁省"兴辽英才计划"项目(XLYC2006017) （XLYC2006017）
辽宁省教育厅科学研究项目(LG202025,LJKQZ2021057) （LG202025,LJKQZ2021057）
