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

对多个客户参与的一类流水车间调度问题,研究客户之间以合作的方式建立联盟,通过加工任务重新排序节省生产成本。一般流水车间调度合作博弈是受限制的,提出一类加工时间和工序相关的流水车间调度问题,相应的合作博弈是平衡的,因而具有非空核。从合作博弈理论出发,以优化多客户线性成本为指标,构建了加工时间和工序相关的流水车间调度合作博弈模型。在获得最优调度排列后,提出了一种加权前后边际成本的客户成本分配的方法,证明了该分配方法是加工时间和工序相关的流水车间调度合作博弈的一个核分配。最后通过一个实例对所提出的基于合作博弈的加工时间和工序相关流水车间调度模型及成本分配方法进行了验证。

Cooperation games on a type of flow shop scheduling problem

According to a type of flow shop scheduling problem with multi-customer participating, this paper researches that customers establish coalition by cooperation, and total costs of customers can be saved by rearrangement of processing tasks.Cooperation games of general flow shop scheduling problem is restricted, a type of flow shop scheduling problem on processing time associated with workstage is presented, processing time of all processing tasks on same workstage is equal, corresponding cooperation games are balanced and have a nonempty core.Starting from cooperative game theory, a model of flow shop scheduling on processing time associated with workstage based on cooperative games is build, processing tasks are rearranged according to optimizing linear cost of customers.After getting optimum scheduling sequence, a kind of cost allocation method based on weighted marginal cost of predecessors and followers is put forward, it is also proved that this method gives a core allocation of cooperative game on this type of flow shop scheduling.At last, this type of flow shop scheduling model based on cooperative games and cost allocation method proposed in this paper are tested and verified.