基于拍卖理论的动态多代理同类机调度算法

工程（英文） ›› 2024, Vol. 35 ›› Issue (4) : 31 -46. DOI: 10.1016/j.eng.2023.09.024

研究论文

基于拍卖理论的动态多代理同类机调度算法

刘亚琼 ^a^,^b^,^c ,
孙树栋 ^a^,^b ,
申高攀 ^a^,^b ,
Xi Vincent Wang ^c ,
Magnus Wiktorsson ^c ,
Lihui Wang ^c

作者信息 +

An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival

Yaqiong Liu ^a^,^b^,^c ,
Shudong Sun ^a^,^b ,
Gaopan Shen ^a^,^b ,
Xi Vincent Wang ^c ,
Magnus Wiktorsson ^c ,
Lihui Wang ^c^,^* ,

Author information +

文章历史 +

Received	Accepted	Published
2022-11-01	2023-09-19
Issue Date
2024-06-12

PDF (2513K)

摘要

本文研究了考虑客户代理的工件动态到达的多代理同类并行机调度问题。所有客户代理和资源代理都是自利且理性的，追求个体目标的最大化，进而导致客户代理之间激烈的资源竞争和不愿意披露私人信息的策略性行为。针对此问题，传统集中式决策方法不再适用，分布式决策方法成为求解目标问题的关键手段。本文提出了一种基于分布式调度决策思想的动态迭代拍卖方法，旨在针对不完全信息下的多代理调度问题，生成同时满足代理偏好，且具有高社会福利的稳定协同调度方案。构建了动态拍卖程序，实现动态工件实时参与拍卖；提出了简单直观的无价格属性投标策略，以降低投标决策的复杂性；设计了自适应匈牙利算法，以高效求解定标决策问题。此外，证明了所提方法满足个体理性，并且短视竞价策略是客户代理提交投标的弱占优策略。广泛的仿真实验表明，所提方法能够生成高质量的调度方案，并在解决包含众多客户代理和工件的大规模问题上表现出较强的稳定性。未来工作将进一步研究考虑多个资源代理的多代理调度问题。

Abstract

This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents. All agents are self-interested and rational with the aim of maximizing their own objectives, resulting in intense resource competition among consumer agents and strategic behaviors of unwillingness to disclose private information. Within the context, a centralized scheduling approach is unfeasible, and a decentralized approach is considered to deal with the targeted problem. This study aims to generate a stable and collaborative solution with high social welfare while simultaneously accommodating consumer agents’ preferences under incomplete information. For this purpose, a dynamic iterative auction-based approach based on a decentralized decision-making procedure is developed. In the proposed approach, a dynamic auction procedure is established for dynamic jobs participating in a real-time auction, and a straightforward and easy-to-implement bidding strategy without price is presented to reduce the complexity of bid determination. In addition, an adaptive Hungarian algorithm is applied to solve the winner determination problem efficiently. A theoretical analysis is conducted to prove that the proposed approach is individually rational and that the myopic bidding strategy is a weakly dominant strategy for consumer agents submitting bids. Extensive computational experiments demonstrate that the developed approach achieves high-quality solutions and exhibits considerable stability on large-scale problems with numerous consumer agents and jobs. A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.

Graphical abstract

关键词

多代理调度 / 分布式决策 / 拍卖理论 / 动态工件 / 私有信息

Key words

Multi-agent scheduling / Decentralized scheduling / Auction / Dynamic jobs / Private information

引用本文

引用格式 ▾

刘亚琼,孙树栋,申高攀,Xi Vincent Wang,Magnus Wiktorsson,Lihui Wang. 基于拍卖理论的动态多代理同类机调度算法[J]. 工程（英文）, 2024, 35(4): 31-46 DOI:10.1016/j.eng.2023.09.024

登录浏览全文

4963

注册一个新账户忘记密码

1 引言

生产调度在制造系统中起着重要作用[1‒2]，并随着生产模式的不断演变而变化。在传统的大规模生产模式下，调度研究主要集中于提高制造商的设备利用率或降低其制造成本[3]。然而，随着客户驱动生产模式逐渐成为主流，制造商需要满足多个用户的独特需求。这使得调度的目标发生了转变，不仅要实现机器资源的高效分配，同时还要满足用户的多样化需求，即催生了近年来被广泛研究的多代理调度问题[4]。该问题可概括为如何将来自于不同用户的工件安排在给定的机器上[5]，其中并行机调度环境在实际应用中十分常见且至关重要[6]。近年来，多代理并行机调度问题吸引了众多研究者的广泛关注[7‒9]，且实际生活中也具有非常广泛的应用。例如，在制造领域将工件安排在机器上的直观场景[10]；在云计算系统中为用户分配多个虚拟机资源[11]；多个电动车共享电力系统中的充电站[12]；在多手术室中安排手术[13]；以及在给定的一组跑道上调度飞机着陆[14]等。此外，上述大多数调度环境是不确定和动态的，即工件、电动车或手术并非同时到达或发生，而是随着时间的推移动态到达。在此背景下，本文聚焦于动态工件到达的多代理同类并行机器调度问题（multi-agent uniform parallel machines scheduling problem with dynamic jobs arrival, MUPMSP-D），其中同类并行机器是具有不同处理速度的异质机器。

在多代理调度模型中，机器资源的分配涉及不同的代理，且每个代理都有工件需要加工，并追求个体目标的最大化。由于机器资源有限，代理之间的资源竞争异常激烈。集中式调度方法是解决此类问题的传统手段，主要通过构建多目标优化模型并生成帕累托解集来实现[15]。然而，从帕累托解集中选择一个能被所有消费者接受的调度方案是一个复杂且具有挑战性的任务。此外，由于代理有各自的目标和偏好，决策时需要考虑到代理的策略性和经济理性行为[16]。具体而言，自利且理性的代理可能不愿意披露其私人信息，因为信息的完全披露增加了被分配到不理想资源的可能性[17]。上述私有信息的存在导致集中式调度方法不再适用，因为这类方法依赖于掌握全局信息的中央决策者。相比之下，分布式决策方法不依赖于中央决策者，而是通过利用自主代理的集体协作来解决资源分配问题[18‒19]。因此，在存在信息不对称的多代理调度问题中，分布式调度方法成为关键求解手段之一。代理参与决策过程并保留私人信息，可以产生更多基于共识的高质量调度结果。此外，分布式方法在解决动态调度问题时更具可扩展性和容错性[20]。综上所述，对于目标MUPMSP-D问题，需要提出一种考虑自利代理策略行为和信息有限性的分布式调度决策方法。

由于在多代理问题中需考虑自利代理的个体需求，调度的目标被重新定义。分布式调度方法的目标不再是寻找“最优”解，而是生成一个稳定且被所有代理接受的协同资源分配方案。该调度方案需要反映所有代理的目标，同时实现社会福利的最大化。社会福利指的是多代理系统的整体效益，综合考虑每个代理的需求[21]。为实现上述调度目标，通常将市场机制与分布式决策框架相结合来求解。具体而言，代理在参与决策时，会学习经济学理论中用户在市场上竞争资源的行为，其中拍卖理论的应用尤其广泛。拍卖理论由于其自治性和分布性，能够在多种资源分配问题中生成较优的资源分配方案[22‒24]。在相关研究上，截至目前，仅Liu等[7]使用拍卖理论解决多代理并行机器调度问题，提出了一种迭代组合拍卖方法，生成社会福利较优的调度方案。然而，他们研究了一个相对简单的场景，即所有工件在同一时刻到达并在同型行机器上处理。所提方法无法解决本文所研究的动态工件以及同类并行机问题。因此，亟需开发一种基于拍卖的分布式方法来求解MUPMSP-D问题。此外，在拍卖方法中，投标决策和定标决策是代理参与决策的主要方式，也是影响整体方法性能的两个关键环节。通常而言，价格是代理进行投标决策时表达偏好并与资源所有者进行沟通的主要方式[25‒28]。然而，由于MUPMSP-D中增加的工件数量和机器异质性，采用价格引导使投标决策和定标决策的计算成本呈指数增长。因此，针对拍卖方法，需设计无价格属性的投标策略及相应的高效定标决策算法。

本研究探讨了在动态工件环境下，涉及多个自利的客户代理和拥有同类并行机器资源代理的多代理并行机调度问题，提出了一种动态迭代拍卖方法（dynamic iterative auction-based approach, DIA），以生成具有高社会福利，同时满足客户代理偏好的协同调度方案。主要贡献总结如下：

（1）首次提出动态迭代拍卖的方法求解MUPMSP-D问题，其中工件在到达后即可实时参与拍卖，实现了对动态工件的灵活调度。证明了所提方法满足个体理性，并通过大量的计算实验验证了方法的有效性。

（2）在所提出的DIA方法中，设计了一种无价格属性的便于操作的投标策略。客户代理在投标时无需提交投标价格，仅提交目标机器即可充分表达偏好，极大降低了拍卖过程中工件增多带来的不断增加的计算成本。理论证明了短视策略是客户代理提交投标时的弱优势策略。

（3）针对定标决策问题（winner determination problem, WDP），提出了一种结合自适应匈牙利算法和混合终止条件的定标决策算法。该算法能够确保在投标数量和WDP规模不断增加的情况下，依然实现客户代理之间的充分竞争，从而生成高质量的调度方案。

本文的其余部分结构如下：第2节介绍了相关研究；第3节描述了目标MUPMSP-D问题和构建了相应的集中式问题模型；第4节详细介绍了所提出的动态迭代拍卖的方法；第5节展示了计算实验和结果；第6节总结了研究内容及未来研究方向。

2 相关研究

自Kutanoglu和Wu [29]首次将拍卖理论引入分布式决策结构求解作业车间调度问题以来，利用拍卖理论解决调度问题的研究蓬勃发展。例如，Hall和Liu [25]提出了一种有效的升价拍卖方法，将单机资源分割成灵活的时间块并设计了自适应要价策略，促进了拍卖方法在机器调度中的应用。随后，Tang等[23]和Zeng等[30]分别在不同的约束条件下研究了基于拍卖的柔性作业车间调度问题。Zhu和Wang [24]设计了一种拍卖机制用于分配两台并行机的生产能力。然而，这些研究所解决的问题大多为机器环境较为简单的调度问题。此外，每个竞标者仅对一个工件进行投标，限制了方法的可扩展性。在上述研究的基础上，Zeng等[31]研究了一个更加实际和复杂的具有并行批处理的作业车间调度问题，将改进的分离图模型应用于拍卖方法，把灵活的工件视为拍卖者或者竞标者，并在大规模的问题上具有较优的性能。然而，这种方法通用性不强，不能扩展到并行机器调度中。此外，Kong等[32]为云计算中的虚拟并行机器资源调度设计了拍卖机制，但虚拟资源在灵活可分性并不适用于本文研究的问题。Liu等[7]研究了一种基于迭代拍卖的多代理并行机器调度方法，提出了一种多阶段拍卖框架，确保竞标者可以对多个工件进行投标，扩展了可解决问题的规模。然而，这些研究者主要关注相同的并行机，并假设所有工件静态到达。目前，学术界尚未有关于动态多代理同类并行机器调度的相关研究。基于此，本文探讨了MUPMSP-D问题，并提出了一种基于拍卖的方法，以生成高质量的调度方案。该方法同时可以扩展至不相关的并行机器环境。

在动态调度中，拍卖理论同样得到了广泛应用。Dewan和Joshi [33‒34]首先在动态作业车间调度研究了拍卖方法的应用。他们奠定了拍卖在动态调度中的应用基础，但仅考虑了属于一个代理的三个工件，且这些工件同时参与拍卖。文献[35]研究了更为复杂的动态调度问题，构建了相应的拍卖方法，但拍卖仅在机器可用时开始，延迟了决策过程。在其他相关调度领域，拍卖理论也得到了一定的发展。例如，Araúzo等[36]和Tosselli等[37]分别在项目组合调度和多项目调度中采用了拍卖方法。项目调度中的任务通常可以拆分为子任务，但在MUPMSP-D场景中，工件不可拆分。在其他相关领域，Kong等[32]研究了基于拍卖的虚拟机资源调度；Vishalatchi等[38]针对云计算调度，提出了一种结合禁忌搜索的拍卖结合。Mukherjee等[39]通过采用市场清算拍卖和动态报价，解决了电力市场中的调度问题。然而，这些研究重点关注于动态资源，而不是用户需求的动态变化。综上所述，上述研究方法尚无法应用于存在多个用户且每个用户拥有多个且不可分割的工件的动态调度问题。为此，本文开发了一种动态拍卖程序，确保工件一旦到达便能参与拍卖，从而减少了工件等待调度的时间。

在信息不对称的调度环境中，能够反映竞标者个体偏好同时又能保护私人信息的投标策略对于提升拍卖方法的性能至关重要。通常而言，价格是在投标时较为常见的表达个体偏好的方式。Wellman等[40]最早将保留价格引入调度领域，竞标者通过提高价格来表达其偏好。这些研究者还探讨了一般性调度问题中均衡价格的存在。受此原理启发，Hall和Liu [25]设计了一种灵活的自适应定价策略和灵活的时间块，使竞标者能够对其目标时间资源进行灵活投标。此后，该研究在文献[7,24,41]中得到了进一步扩展。基于拉格朗日乘子的定价也是一种被广泛采用的投标定价方法[42‒44]。这些投标方法可以直观地表示竞标者的偏好，并且密封投标较好地保护了用户隐私。然而，竞标者必须为每个工件或任务计算其在所有潜在目标资源上的价格。在目标MUPMSP-D问题中，由于存在三个强约束：多竞标者、多异构机器和不断增加的工件数量，使用传统的价格引导策略将导致投标决策的计算成本呈指数增长。基于此，一些研究提出了无价格的投标机制。例如，Wang等[45]提出了一种无价格投标策略，竞标者提交其偏好的时间间隔。Liu等[46]在手术调度中提出了另一种无价格投标机制，通过为每个时间包分配价值来进行投标。Merz等[47]在人机协作调度中提出了选择处理时间最长的机器的方法。需要注意的是，这些问题中所考虑的资源是单属性资源，即时间或处理速度，在多属性机器环境中无法使用。因此，本文为MUPMSP-D问题设计了一种适用的无价格属性投标策略，竞标者可根据其目标提交一个或多个目标机器。这种方法在保护代理隐私的同时，大大降低了计算成本。

3 问题描述

本节对所研究的MUPMSP-D问题进行了详细描述，并构建了对应的集中式问题模型。其中集中式问题模型将作为第5节对比实验的基准模型。

3.1 MUPMSP-D问题模型

MUPMSP-D问题描述如下：存在N个自利的客户代理

C A = {C A 1, C A 2, …, C A i, …, C A N}

，每个客户代理

C A i

有

n i

个动态到达的工件

{J 1 i, J 2 i, … J k i, J n i i}

。这些工件需要在属于资源代理RA的

m

台同类并行机

{M 1, M 2, …, M j, …, M m}

上加工。所有待加工工件总数为

J = ∑ i = 1 N n i

。工件

J k i

表示

C A i

的第k个工件，其特征包含四个元素

J k i =

p k i, d k i, ω k i, r k i

，分别代表加工需求、截止日期、单位延期带来的收益损失以及工件被加工完成给客户代理

C A i

带来的收益。

此外，本文基于文献[48]考虑了更符合实际的三种机器状态：设置状态、加工状态和空闲状态，具体如图1所示。在开始加工工件之前，机器需要调整机器状态，即进入设置状态，这里考虑机器相关的设置时间（machine-dependent setup time）[49]。在设置完成之后，机器进入加工状态，开始加工工件。由于工件的动态到达，当现有工件业已加工完成但没有新作业到达时，机器会进入空闲状态。空闲时间则指的是机器等待新工件的时间间隔。此时，尽管机器处于空闲状态，但其仍然消耗能量并产生成本[50]。上述三种状态分别对应三种成本。综上，每个机器

M j

包含6个参数：①加工速度

s p j

，决定工件的实际加工时间；②设置时间

s t j

，与工件加工顺序为无关但与机器相关[51]；③单位加工成本

o c j

，即机器处于加工状态时产生的单位运行成本；④单位设置成本

s c j

，指机器处于设置状态时产生的成本；⑤单位空闲成本

i c j

，对应于机器空闲状态时产生的成本；⑥单位加工收益

p r o j

，即机器加工工件时获得的单位收益。

所有客户代理和资源代理均为自利的。客户代理CA _i 的目标为最大化个体效益：

f C A i = ∑ k = 1 n i (r k i - ω k i · m a x

(c k i - d k i, 0))

，其中，

c k i

表示工件

J k i

的完工时间，

ω k i · m a x (c k i - d k i, 0)

表示工件

J k i

延期带来的总收益损失。资源代理通过分配机器资源获得最大的效益，即最大化加工工件产生的总利润减去总成本。这里的总成本由三个部分组成：机器加工成本、设置成本和空闲成本。

一个调度方案可以表示为一个映射

F = s 11, m 11, …,

s k i, m k i

，表示工件

J k i

被分配的机器

m k i

及其在机器上的开始时间

s k i

。本文中调度方案的生成需要满足以下约束和假设：

（1）所有机器在初始时刻可用且无故障；

（2）工件可以在任意机器上加工，但在任意时刻只能在一台机器上加工；

（3）工件只能在其到达后开始加工，且加工开始后不可中断；

（4）工件

J k i

的延期损失不能超过其带给客户代理

C A i

的收益

r k i

；

（5）机器加工速度

s p j

和设置时间

s t j

为公开信息，即所有代理所知，但三种成本仅为资源代理所知；

（6）工件

J k i

的加工需求

p k i

为半公开信息，为客户代理

C A i

和资源代理所知，而其余参数为客户代理

C A i

的私有信息。

由于本文通过设计分布式调度算法求解MUPMSP-D，通常而言，需要进入社会福利来评估调度方案F的系统的整体效益[52]。这里的社会福利指N个客户代理与资源代理的效益之和：

S W = ∑ i = 1 N f C A i + f (R A)

。

3.2 集中式问题模型

本节构建了所有信息均为公开信息下的集中式问题模型。该模型将作为基准，以评估所提出的分布式拍卖方法的性能。所构建的混合整数规划模型如下所示：

M a x i m i z e ∑ k = 1 n i ∑ i = 1 N X k i j t · r k i - ω k i · T k i + ∑ k = 1 n i ∑ i = 1 N ∑ j = 1 m ∑ t = 1 J X k i j t · p k i s p j p r o j - o c j - s t j · s c j - I T j t · i c j

(1)

s.t.

∑ k = 1 n i ∑ i = 1 N X k i j t ≤ 1, j = 1,2, …, m, t = 1,2, …, J

(2)

∑ j = 1 m ∑ t = 1 J X k i j t = 1, k = 1,2, …, n i, i = 1,2, …, N

(3)

S j t + 1 - S j t = ∑ k = 1 n i ∑ i = 1 N X k i j t · p k i s p j + s t j, j = 1,2, …, m, t = 1,2, …, J - 1

(4)

S j l ≥ X k i j t · a k i, k = 1,2, …, n i, i = 1,2, …, N, j = 1,2, …, m, t = 1,2, …, J

(5)

C j t = S j t + X k i j t · s t j + X k i j t · p k i s p j, k = 1,2, …, n i, i = 1,2, …, N, j = 1,2, …, m, t = 1,2, …, J

(6)

T k i = C j t - 1 - X k i j t M - d k i, k = 1,2, …, n i, i = 1,2, …, N, j = 1,2, …, m, t = 1,2, …, J

(7)

T k i ≥ 0, k = 1,2, …, n i, i = 1,2, …, N

(8)

T k i ω k i ≤ r k i, k = 1,2, …, n i, i = 1,2, …, N

(9)

I T j t = ∑ t = 2 J ∑ k = 1 n i ∑ i = 1 N X k i j t S j t - C j t - 1, j = 1,2, …, m

(10)

X k i j t = 0,1, k = 1,2, …, n i, i = 1,2, …, N, j = 1,2, …, m, t = 1,2, …, J

(11)

该模型基于文献[48,53]构建。式（1）表示目标函数，包含客户代理的总效益和资源代理的效益两个部分。式（2）约束条件确保每台机器上的每个位置一次最多只能加工一个工件。式（3）保证工件

J k i

一次只能被一台机器加工。约束条件（4）和（5）用于计算工件

J k i

在机器位置上的开始加工时间，其中约束条件（5）规定了工件只有在到达之后才能开始加工。约束条件（6）量化了工件

J k i

在机器位置上的完工时间。约束条件（7）和（8）定义工件

J k i

的延期时间，其中M表示一个足够大的正数。约束条件（9）确保工件的延期损失不能超过其给客户代理带来的收益。约束条件（10）计算机器

M j

在第t个位置上的空闲时间。

4 研究方法

针对MUPMSP-D问题，本节提出了一种拍卖框架。该方法核心思想是将资源代理和客户代理分别视为拍卖者和竞标者。拍卖者将机器资源视为拍卖商品，而投标方为其目标机器资源进行竞标。由于多个自利客户代理之间对有限机器资源的激烈竞争以及工件的动态到达，该框架被设计为一个动态迭代拍卖过程，主要包括四个主要组成部分：动态迭代拍卖过程、投标方者投标决策模型、拍卖者的定标决策模型以及竞标者的投标更新策略。

4.1 动态迭代拍卖过程

为使客户代理和资源代理能够生成一致的调度计划，设计了动态迭代拍卖过程。其主要流程如图2所示。除定义的公开信息和半公开信息外，任何私人信息都禁止在拍卖过程中披露。

当有任何竞标者产生加工需求时，该竞标者将其加工需求提交给拍卖者，然后拍卖正式开始。拍卖者首先确认可用的机器资源，并将相关信息发布给竞标者。竞标者在收到拍卖信息后，对已到达的工件进行投标决策，并将投标提交给拍卖者。这些投标被整合成一个投标池，作为拍卖者解决定标决策问题的输入。如果满足终止条件（详见第4.3节），则拍卖者生成到达工件的调度方案。否则，拍卖者将基于定标决策模型的临时解决方案更新可用的机器资源。进一步，随着拍卖项目的更新，竞标者更新已提交工件的投标并对新到达的工件进行投标决策。当没有新工件到达时，竞标者将退出拍卖。这种动态拍卖的设计确保了工件一旦到达便能参与拍卖，实现了对动态工件的灵活调度。值得注意的是，每轮拍卖中工件数量的增加也对WDP的求解增加了新的挑战。动态迭代拍卖过程促进了客户代理和资源代理之间的动态有效互动，使参与者能够协商达成一致的调度解决方案。此外，该过程减少了买卖双方信息披露，并具有适应拍卖过程中动态变化的能力。

4.2 投标决策模型

本节构建了客户代理投标决策模型，用于生成投标。一般来说，在拍卖中，拍卖者和竞标者通常通过价格来表达个人偏好[54]。然而，在MUPMSP-D问题中，拍卖者同时出售多个同类并行机器资源，以及每个竞标者将在一轮拍卖中为多个工件进行投标。如果采用投标价格来表达竞标者对不同机器的偏好会带来两方面的难题。首先，拍卖者必须为每台机器的每个时间槽设置要价。其次，每个竞标者必须计算出指数级的投标价格。这些复杂的计算不仅不能产生更好的解决方案，反而降低整个拍卖系统的效率。此外，在实际的制造环境中，消费者和制造商都偏好简单的决策方法。因此，本文开发了一种简单直观的无价格投标策略，并据此构建了投标决策模型。

在拍卖开始时，拍卖者向竞标者发布每台机器的最早可用时间。相应地，竞标者通过提交基于需求的投标表达个体偏好。这种投标可以表示为一个二元组

b k i = J k i, M j

，其中

J k i

表示投标工件，

M j

表示目标机器。对于竞标者而言，无需提交投标价格仅提交目标机器的方式减少了计算成本，并且能够直接且有效表示个体需求。此外，这种方法不要求理性且自利的客户代理披露任何关于其收益的信息，从而保护了隐私。此外，引入

E k i

表示竞标者

C A i

对工件

J k i

的投标次数，主要用于对竞标者在单次拍卖中同时为多个工件投标时排序。

E k i

值越大，工件

J k i

的计算优先级越高。虽然计算顺序不会影响调度方案，但一个合理的规则有助于方法的顺利实施。最后，这种不依赖机器特性的投标生成方法具有较强的通用性，同样适用于异构并行机器环境中。

此外，由于每个竞标者都不了解其他竞标者的投标信息，并且受到自利动机的驱使，采用短视投标策略成为一种自然选择[25]。在4.5节中，证明了短视策略对于客户代理而言是一种弱占优策略。基于此策略，针对投标工件

J k i

，每个竞标者在每轮拍卖中都会选择能带来最高收益的机器为其目标机器。需要注意的是，只有收益为正的机器才可能被选择。如果一个工件在多台机器上获得相同的非负收益，则所有这些机器都会被视为目标机器。这提高了竞标者的获胜概率，并给与拍卖者更大的分配机器资源空间。如果一个工件在任何机器上加工都无法给竞标者带来正收益，它将退出拍卖。

基于上述原则，投标

b k i = J k i, M j

被设计为一个原子投标。如果一个竞标者为一个工件选择多个目标机器，其投标表示为

b k i = J k i, (M 1, M 2, …, M j)

。该投标可分解由逻辑连接符XOR [55]连接的多个原子投标

b k i = J k i, M 1

、

b k i = J k i, M 2

和

b k i = J k i, M j

。例如，投标

b k i = J k i, (M 1, M 2)

表示竞标者期望在机器

M 1

或者

M 2

上加工工件

J k i

。根据从拍卖者接收到的机器最早可用开始时间

A S j

，投标根据算法 1生成具体投标。

定义U为(

n i

)，表示不同客户代理拥有的最大工件数量。算法1的时间复杂度可表示为O(NUm)，其中，N是客户代理的数量，m是所有机器的数量。

4.3 定标决策模型

在收到竞标者的投标后，拍卖者开始求解定标决策问题（WDP）。求解WDP的目的是以最大化拍卖的效益为目标，从给定的投标中确定如何分配机器资源，进而生成协商一致的生产计划或调度方案。在动态迭代拍卖过程中，拍卖者需要在每轮拍卖中求解WDP并生成临时计划，直至满足拍卖终止条件。通常，在每轮拍卖结束时，暂时赢得投标的竞标者被归类为临时中标者；相反，没有赢得投标的竞标者被称为临时失标者[56]。然而，在MUPMSP-D问题中，竞标者在一轮拍卖中同时为多个工件投标。根据工件是否赢得投标来对竞标者进行分类是不准确的。因此，根据工件的唯一性，将工件直接定义为临时中标工件（provisional winning jobs），并组成一个集合PWJ，而临时失标工件（provisional losing jobs）则组成集合PLJ。当满足终止条件时，临时中标工件成为最终中标工件（final winning jobs）获得目标机器资源，并形成集合FWJ。

迭代组合拍卖通常在两种情况下终止：当不存在竞标者之间的资源分配冲突，即需求得到满足时，拍卖自然终止；当拍卖达到预设的轮数时，拍卖强行终止[57]。工件的动态到达导致参与工件的数量逐渐变化，不断增多。如果设定固定的拍卖轮数，部分后到的工件可能无法充分竞争。因此，在求解WDP时，本文采用满足所有工件需求的自然终止条件。工件在拍卖中持续表达其需求直至其需求得到满足。这种方式虽然可能会增加拍卖的持续时间，但可以消除拍卖对后到工件的负面影响。此外，引入了连续三次成为临时中标工件的工件被视为最终中标工件的补充条件，类似于拍卖实践中的三次击锤原则。这样的设计可以减少重复投标，使迭代拍卖更加高效。

在所提出的DIA方法中，WDP模型构建如下。基于工件的动态到达和投标更新带来的动态变化投标集合，拍卖者以最大化自身效益为目标生成临时调度方案。由于二元组

b k i = J k i, M j

或者

b k i = J k i, (M 1, M 2, …, M j)

都不包含任何价格信息，WDP可以转化为指派问题，即在满足第3.1节约束的条件下，将工件分配到机器上。针对指派问题，匈牙利算法是一种应用较为广泛的优化算法，其时间复杂度为

O (n 3)

[58]。基于该算法和动态投标，本文提出了一种自适应匈牙利算法求解动态WDP，其伪代码如算法2所示。

定义

N b

为第r轮拍卖中拍卖者收到的投标总数，

N p

集合临时中标工件集合PWJ中的投标数量，其中

N p ≤ N b

。算法2主要由三部分组成：①生成收益矩阵，时间复杂度为

O (N b)

；②适用自适应匈牙利算法获得最优解，时间复杂度为

O (J 3)

，其中，J是所有工件的数量；③根据

N p

更新所有机器的最早可用时间，其时间复杂度为

O (N p)

。综上，算法2的整体时间复杂度为

O N b + J 3 + N p = O (J 3)

。

4.4 投标更新策略

在迭代拍卖过程中，每个竞标者在最终赢得投标获得所需目标机器资源，或者退出拍卖之前，会不断更新投标。拍卖者在第

r (r ≥ 1)

轮定标决策之后，向竞标者告知工件的定标结果，即属于临时中标工件、临时失标工件还是最终中标工件。在第r+1轮拍卖中，为了提高各自的中标概率，理性的竞标者将根据定标结果对不同的工件采取不同的投标策略。

对临时中标工件，竞标者理所当然期望该工件能够保持获胜状态，并成为最终中标工件。由于短视策略是弱占优策略，且拍卖的机器资源保持不变，在第r轮提交的投标仍能使竞标者的收益最大化，此时在第r+1轮提交相同的投标是最优选择。对临时失败工件，竞标者更渴望其能在下一轮中获胜。因此竞标者会选择提交更多竞标，为拍卖者提供了更多匹配选择，从而提高获胜概率。具体来说，竞标者在第r+1轮中，将在第r轮中提交的收益最大的机器的基础上，增加提交收益第二大的目标机器。此外，如果工件在r+1轮中持续失败，那么竞标者在第r+2轮中将会在第r+1轮投标的基础上继续增加收益第三大的机器。这种增加会一直持续，直到工件获胜或所有的有效投标都被加入。对于最终中标工件，这些工件已获得所需的机器资源，将退出拍卖。算法3总结了该投标更新策略。

4.5 方法性质证明

对于拍卖方法而言，证明其相关属性能够从理论上说明方法的合理性。本节描述并证明了提出的DIA方法的两个关键属性[46]。

性质1：所提出的DIA方法是个体理性的。

证明：在一个个体理性的拍卖机制中，对任意参与者，无论任何其他参与者的行为如何，该参与者参与拍卖获得的效用至少不低于其不参与拍卖的产生效用。即当所有竞标者参与拍卖的期望效用非负时，个体理性得以成立。

在DIA中，每个竞标者

C A i

对任意工件

J k i

都只生成收益非负的投标。当工件在所有机器上的效用为负时，自动退出拍卖。显然，所有最终获胜的工件都会为竞标者带来非负效益，即满足

V k i j ≥ 0

，进而

C A i

参与拍卖的最终收益满足

f C A i = ∑ k = 1 n i V k i j ≥ 0

。由于拍卖方法确保所有参与者均获得非负效用，因此其满足个体理性。

性质2：在所提DIA方法中，短视策略是竞标者提交投标的弱占优策略（weakly dominant strategy）。

证明：由于自利且理性的竞标者不知道任何其他竞标者的相关投标信息，因此在拍卖开始时，所有的竞标者都会采取短视策略，即为参与拍卖的工件提交收益最大的投标。在第r轮的定标决策结束后，工件被归类为临时中标工件、临时失标工件和最终中标工件。最终中标工件将退出拍卖，以下分别证明对于临时中标工件和临时失标工件而言，短视策略仍然是其在第r+1轮更新投标的弱占优策略。

情形1：对于临时中标工件，竞标者的最优自然选择是继续遵循短视策略，在第r+1轮中仍然提交与第r轮相同的收益最大的投标。因为当前投标已经给竞标者带来最大收益，若提交其他投标不仅会减少收益，还可能泄露更多的私人信息。

情形2：对于临时失标工件，竞标者若采用短视策略则会在第r+1轮中增加收益仅次于最大收益的新投标

b^k i

。为证明短视策略为弱占优策略，构建另外一种策略作为对比，即竞标者额外提交收益小于

b ˜ k i

和

b^k i

的新投标

b ˜ k i

。以下分两种情形进行证明。

情形2-1：假设临时失标工件在第r+1轮中通过提交投标

b^k i

获胜。此时，若采用对比策略会产生两种结果：工件通过提交

b ˜ k i

在第r+1轮中失标，那么毫无疑问提交

b^k i

是最优策略；工件提交

b ˜ k i

在第r+1轮中获胜，但是明显的，

b^k i

会给竞标者带来更多收益。因此，在情形2-1下，短视策略是占优策略。

情形2-2：假设临时失标工件在第r+1轮中提交投标

b^k i

，但是未中标。考虑采用对比策略产生的两种结果：工件提交

b ˜ k i

在第r+1轮中未中标，则提交

b^k i

和

b ˜ k i

给竞标者带来的收益是相同的；工件提交

b ˜ k i

在第r+1轮中标，此时尽管

b^k i

在第r+1轮未获胜，但根据短视策略竞标者会在第r+2轮中增加投标

b ˜ k i

，即该工件仍然会在第r+2轮中获胜。因此，在情形2-2下，竞标者采用短视策略和其他策略的收益相同。

总之，所提出的迭代拍卖方法是个体理性的，并且对于临时中标工件和临时失标工件，短视投标策略都是竞标者生成和提交投标的弱占优策略。

5 仿真实验

首先，通过与集中式调度方法和分布式调度方法的比较，验证了所提出的DIA方法的性能。然后，分析了方法在不同问题上的所需拍卖轮次的变化。最后，测试了所提出方法的可扩展性。所有方法均使用 MATLAB 2016b（The MathWorks Inc., Boston）和Python 3.9实现，并在一台3.6 GHz Intel i7 CPU和8 GB RAM的PC上进行实验。

5.1 实验设置

不同规模的问题实例和合理的评价指标对于评估方法的性能至关重要。因此，本节将描述问题实例的生成方式以及性能评估指标。

5.1.1 算例构造

对于m台同类并行机，每个机器都包含6个参数

s p j, s t j, o c j, s c j, i c j, p r o j

。参数取值分别为：机器数量满足

m = {3,5, 10,15}

；加工速度

s p j

和设置时间

s t j

服从均匀分布：U[10,20]和U[1,5] [59]；单位加工成本

o c j

、单位设置成本

s c j

、单位空闲成本

i c j

分别满足U[11,15]、U[6,10]、U[1,5]。与实际生产中实际情况保持一致，三种成本呈递减趋势。完成工件获得的单位收益

p r o j

是通过公式

p r o j = 1.3 (o c j + s c j + i c j)

取整后获得。

基于机器数量，客户代理数量取值为

N = {3,5,

7,9,

11,13,15}

。不同的取值是为了构造不同竞争程度的问题算例。具体地，当机器数不变，客户代理数量越多，说明客户代理之间的资源竞争冲突越激烈。客户代理的待加工工件数

n i

与方法性能无关。为便于理解和算例构造，假设所有客户代理的待加工工件数相等，取值满足

n i = {5,7, 10,15}

。工件相关

J k i

5.1.2 评价指标

为了评估所提出的DIA方法的有效性，分别将其与集中式方法和分布式方法进行比较。首先，与动态调度中最典型的四种集中式调度方法进行对比：①五种基本的调度规则[61,33]（dispatching rules, DR），包括先到先加工（first-come-first-served, FCFS）、最早截止日期有限（the earliest due date, EDD）、最短加工时间优先（the shortest processing time, SPT）、最长加工时间优先（the longest processing time, LPT）和最小松弛时间优先（the minimum slack, MS）；②复杂调度规则组合[62]（complex dispatching rules, CDR）；③深度强化学习[63]（deep reinforcement learning, DRL）；④改进的遗传算法[64]（modified genetic algorithm, MGA）。其次，在分布式对比方法方面，将调度规则DR嵌入分布式环境（DR implemented in decentralized environment, DR_D），形成DR_D算法；将复杂调度规则组合CDR应用于分布式决策环境（CDR implemented in decentralized environment, CDR_D），形成CDR_D算法。这是因为所提出的DIA方法是在动态工件、多代理并行机、信息不完全的约束下开发的，在现有文献难以找到在同样约束下求解的分布式方法。因此为了确保公平性和可比性，根据参考文献[33]的算法对比思想，将调度规则应用于分布式环境。

采用社会福利比值指标来评估所提算法性能，其计算公式如下：

R S W x = S W D I A S W x × 100 %

(12)

式中，

S W D I A

表示算法DIA获得的社会福利，

S W x

表示不同集中式方法生成的社会福利，x表示具体用于对比的集中式算法。需要注意的是，当与DR和DR_D比较时，五种调度规则的最大社会福利为

S W D R

，DR_D的最大社会福利为

S W D R_D

。该评价指标越大，说明所提出方法的性能越优。

5.2 实验结果分析

5.2.1 实验1：与集中式方法对比

在该实验中，所提出的DIA方法分别与四种集中式方法进行了比较。附录表S1~S4展示了DIA在所有问题上与集中式方法对比的RSW结果，其中，PI_N_

n i

表示包含有N个客户代理和每个客户代理有

n i

个待加工工件的算例。表1总结了在不同机器参数上，DIA分别与方法DR、CDR、DRL和MGA对比的平均RSW以及整体平均值。需要注意的是，提出DRL的文献[63]在进行灵活性实验时验证的最大机器数为4台，且没有在更多机器的问题上进行训练，也未提供相关参数。在本实验中，采用现有参数在10机器和15机器的问题上进行测试时，发现DRL的效率和性能都明显较差。为了保持公平性，剔除了DRL在10机器和15机器上的实验结果。

从表1可以看出，DIA的平均社会福利分别达到了简单规则DR的103.5%，复杂调度规则CDR的92.1%，达到强化学习DRL的84.1%，以及达到改进遗传算法MGA的78.4%。说明在不完全信息和动态工件的强约束下，所提出的DIA方法和集中式方法差距较小，能产生相对较高的社会福利。特别是，在和DR相比时，大于100%的RSW说明所设计的分布式方法的性能甚至优于集中式简单规则。此外，从不同的机器参数来看，在任意对比方法下，DIA的平均RSW都随机器数量的增加而提高。例如，在15机器时，DIA的平均RSW分别达到CDR方法的93.8%和MGA方法的88.2%。这表明DIA在机器数量较多的问题上具有更好的求解性能。

由于MGA在这四种集中调度方法中表现最佳，直接比较由MGA和DIA获得的特定RSW（定义见5.1.2节）足以说明DIA方法的性能。以下将以DIA和MGA对比的RSW为例，说明DIA在不同参数测试算例上的性能变化。首先，以

α = 1.4

为例，说明DIA在不同客户代理数量N和工件数量n_i 问题上的性能变化，如图3所示。通过横向观察四个子图，随着客户代理数量和工件数量的不断增加，DIA的RSW表现稳定，没有表现出显著的下降规律。这一现象说明所提方法具有较强的稳定性，方法性能没有在规模扩大的问题上出现明显恶化。另一个可能的原因是，算法DIA和MGA都较为稳定，当前算例参数

n i

和N的取值不足以使它们的性能出现较大波动，因此无法观测到明显的变化趋势。在随后第5.2.4节，将通过进一步的实验探讨方法在更大参数问题上的性能变化。

DIA在不同参数

α

问题上的RSW变化，如图4所示。图中每个柱子表示在给定机器数量和参数

α

下，DIA在所有客户代理上的平均RSW。可以看出，从四个柱状图可以看出，在给定机器数量下，随着参数

α

的增加，DIA的RSW表现出轻微的上升趋势。例如，当m = 10时，DIA在α = 1.2、1.4、1和1.8的问题上，对应的RSW值分别为81.2%、83.8%、84.9%和85.3%。不同的是，在m = 3和

α = 1.4

的问题上，RSW有所下降。这可能是由于MGA在这些问题上性能较好，社会福利更高，因此导致DIA与MGA的比值RSW的相对减小。此外，观察同一颜色的柱子可知，在同一参数

α

下，RSW在机器数量增加的问题上的RSW值越大，与表1中的趋势保持一致。尤其是，当m = 15和

α = 1.8

时，DIA的RSW达到89.2%。这些结果表明，所设计的方法在截止日期更宽松的和更多机器的问题上表现出了更优越性能。原因在于，客户代理之间的资源竞争程度降低，以及分布式决策中竞标者的投标选择更加多样。

5.2.2 实验2：与分布式方法对比

第二个实验通过与分布式调度方法的比较，进一步验证方法的有效性。附录A中的表S5和表S6汇总了DIA与分布式方法DR_D和CDR_D在所有问题上的详细对比结果。表2总结了DIA与DR_D和CDR_D在不同机器数下的平均RSW变化，以及总体平均RSW。可以看出，与两种方法相比，DIA在所有问题上生成方案的社会福利平均提升至155.9%和134.9%。这表明DIA能够生成高质量的调度方法，并且性能优于分布式环境下的调度规则。此外，DIA在更大规模的机器问题上表现出更优越的性能。具体来说，当机器数量增加到15时，DIA的性能分别提高了85.1%和54.0%。鉴于复杂调度规则CDR_D优于基本规则DR_D，直接将DIA与CDR_D对比，既便于描述，也能更清晰地呈现对比结果。因此，在后续的实验和分析中，仅用与CDR_D对比的RGR来说明DIA和分布式方法对比的结果。

图5以DIA和CDR_D对比的RSW为基础，展示了DIA在不同参数规模问题上的性能表现。首先，从四条折线可看出，在任意

α

值下，RSW的整体平均值随着机器数量的增多呈现出不断变大的趋势，与表2保持一致。这进一步说明了所提出的DIA方法在解决更多机器的问题时，能够获得更高质量的解决方案。随后，从每个子图的柱状图来看，即保持参数

α

不变的情况下，在任何机器数量上，随着每个代理代加工工件数量的不断增多，RSW逐渐增大。同样地，在保持工件数量

n i

和机器数量m不变的情况下，在

n i = 5

之外的所有算例上，随着

α

值的增加，DIA的优越性更加突出。结合二者，在

α = 1.8

、

n i = 15

和m=15的问题上，RSW的平均值达到最高。在部分算例上，CDR_R能够产生较高的社会福利，导致相应的RSW较小。然而，DIA表现较为稳定，在其他问题上生成了更高的社会福利提升了RSW，从而弥补了这一差距，使得平均RSW表现出很强的规律性。

5.2.3 实验3：所需拍卖轮次分析

该实验主要总结和分析算法DIA在不同规模问题上达成最终分配方案所需要的拍卖轮次数。为便于统计和分析，针对每个算例，保持机器数量m,、客户代理数量N、每个客户代理待加工工件数量

n i

不变。取DIA在同一个算例在不同参数

α

下的拍卖轮次平均值作为分析依据。图6展示了DIA在不同规模问题上所需的平均拍卖轮次。

如图6的四个子图所示，在保持机器数量保持不变的情况下，随着客户代理待加工工件数量的增多，DIA需要更多的拍卖轮次才能达成一致。同时，对任意子图，在工件数量

n i

不变，客户代理增加的问题上，DIA也需要更多的轮次才能生成高质量的解决方案。观察子图中同样颜色的折线，可以发现随着机器数量的增加，客户代理需要更多的拍卖轮次才能达成共识。此外，当

n i

越大时，所需的迭代轮次增长得更快。如四条橙色线所示，当

n i = 15

时，拍卖轮次的增加幅度最大。这三种参数的叠加，使得DIA在

n i = 15

、N=15和m=15的问题上的拍卖轮次达到峰值。这是由于增加可用的机器资源在一定程度上可以缓解客户代理之间的竞争，然而，由于机器的处理能力不同，竞标者的投标决策和竞拍者的定标决策都会变得更加复杂，因此需要更多的拍卖轮次才能消解竞争冲突。此外，参与拍卖的工件数量的不断增加也使得解决这些问题的难度加大，这也是图中橙色线条的变化如此剧烈的原因。

5.2.4 实验4：方法可扩展性分析

在第四个实验中，分析了DIA在客户代理数量和每个客户代理工件数量上的可扩展性。按照上文实验分析中指标选择的标准，在该实验中，MGA和CDR_D分别作为DIA与集中式和分布式方法对比的基准。

图7显示了在不同客户代理数量问题上，DIA分别与MGA和CDR_D对比的RSW变化。在该实验中，保持每个代理的待加工工件数

n i = 15

不变，将客户代理的数量从18个增加至42个，则对应的所有待加工工件总数从270个增加到630个。从总体上看，无论是与MGA还与CDR_D对比，DIA都表现出相似的性能变化趋势。在机器数量较少的问题上（m=3，图中蓝色折线），DIA的RSW表现出下降趋势。这说明，表明随着客户代理数量的增加，所提出方法的性能有所恶化。然而，在机器数量较多的问题上，RSW则呈现出明显的增加趋势。特别是与CDR_D对比时，增加尤为明显。这是因为客户代理和机器数量同时增加使得问题求解难度急剧增加，而CDR_D的性能恶化远超DIA，因此RSW呈上升趋势。这一现象从侧面证明了DIA在处理复杂问题时仍具有较强的稳定性。

图8展示了DIA在每个客户代理待加工工件数量问题上的可扩展性分析。在该实验中，保持客户代理数量N = 15不变，将每个客户代理的待加工工件数量从20个增加至60个，则对应的总工件数从300增加到900。在

n i

增加至30之前，无论是与MGA还是与CDR_D对比，DIA的RSW值均呈下降趋势。然而，随着

n i

的持续增加，RSW则出现了上升趋势。综合两个子图，可以得出，随着客户代理数量和每个客户代理的待加工工件数量（即总工件数量）的增加，DIA的社会福利有所下降。然而，增长的RSW也表明所提方法具有更好的稳定性。尤其是在对于超过500个工件的问题上，DIA的性能下降远小于对比方法。此外，与客户代理数量增加相比，DIA在工件增加的问题上性能降低的幅度更低。

6 结论与未来工作

本文研究了多代理同类并行机器调度问题，考虑了代理的个体偏好和私有信息及工件的动态到达，提出了一种分布式动态迭代拍卖方法，以生成具有高社会福利的、稳定的、协同调度方案。方法主要包括动态拍卖程序、投标决策、定标决策和投标更新策略四个部分。在方法的每个阶段，代理的私有信息都得到了保护。其中，动态拍卖程序确保工件在到达之后即可参与拍卖；投标决策和更新中的无价格属性投标策略，克服了在拍卖中对不断增加的工件进行投标的挑战，显著降低了计算成本；在定标决策阶段，提出了一种自适应匈牙利算法高效对WDP进行高效求解。通过理论分析，证明了该法的两个特性：个体理性以及短视策略是竞标者投标的弱占优策略。最后，在2240个算例上，进行了四种实验。结果表明，所提方法能够生成高质量的解决方案，特别是在大规模问题上表现出良好的稳定性。对于具有更多客户代理和工件的问题，方法需要更多的迭代拍卖轮次来生成具有高社会福利的解决方案。

尽管提出的DIA方法具有上述优势，但该方法也存在一些不足。求解定标决策问题的算法2的时间复杂度为

O (J 3)

。当工件总数J足够大时，方法会产生一定的计算成本。此外，本文尚未对所提方法的在实际企业中的应用进行验证。

未来，我们将进一步以拍卖方法为基础理论，研究多代理调度方法的实际应用。比如，在实际中，往往存在多个客户代理和多个资源代理。针对此问题，计划提出一种基于双边拍卖理论的多对多谈判过程。同时考虑与多个资源代理相关的距离和物流成本。问题难度的增加使得投标决策和定标决策的复杂性大大增加。因此，需要进一步优化相关决策算法，同时降低算法时间复杂度。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	Wang B, Tao F, Fang X, Liu C, Liu Y, Freiheit T. Smart manufacturing and intelligent manufacturing: a comparative review. Engineering 2021;7(6):738‒57. . 10.1016/j.eng.2020.07.017

[2]	Yang T, Yi X, Lu S, Johansson KH, Chai T. Intelligent manufacturing for the process industry driven by industrial artificial intelligence. Engineering 2021;7(9):1224‒30. . 10.1016/j.eng.2021.04.023

[3]	Edis EB, Oguz C, Ozkarahan I. Parallel machine scheduling with additional resources: notation, classification, models and solution methods. Eur J Oper Res 2013;230(3):449‒63. . 10.1016/j.ejor.2013.02.042

[4]	Wang D, Yu Y, Yin Y, Cheng TCE. Multi-agent scheduling problems under multitasking. Int J Prod Res 2021;59(12):3633‒63. . 10.1080/00207543.2020.1748908

[5]	Agnetis A, Pacciarelli D, Pacifici A. Combinatorial models for multi-agent scheduling problems. In: Levner E, editor. Multiprocessor scheduling: theory and applications. London: IntechOpen; 2007. p. 21‒46. . 10.5772/5213

[6]	Pinedo ML. Scheduling: theory, algorithms and systems. 4th ed. New York: Springer; 2012. . 10.1007/978-1-4614-2361-4

[7]	Liu Y, Sun S, Wang XV, Wang L. An iterative combinatorial auction mechanism for multi-agent parallel machine scheduling. Int J Prod Res 2022;60(1):361‒80. . 10.1080/00207543.2021.1950938

[8]	Pei J, Wei J, Liao B, Liu X, Pardalos PM. Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent. Ann Oper Res 2020;294:191‒223. . 10.1007/s10479-019-03160-y

[9]	Yu F, Wen P, Yi S. A multi-agent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan. Adv Mech Eng 2018;10(2):1‒14. . 10.1177/1687814018756103

[10]	Mönch L, Shen L. Parallel machine scheduling with the total weighted delivery time performance measure in distributed manufacturing. Comput Oper Res 2021;127:105126. . 10.1016/j.cor.2020.105126

[11]

Abdel-Jabbar MAH, Kacem I, Martin S. Unrelated parallel machines with precedence constraints: application to cloud computing. In: Proceedings of 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet); 2014 Oct 8‒10; Luxembourg, Luxembourg. Piscataway: IEEE; 2014. p. 438‒42. . 10.1109/cloudnet.2014.6969034

[12]	Zhou Y, Kumar R, Tang S. Incentive-based distributed scheduling of electric vehicle charging under uncertainty. IEEE Trans Power Syst 2019;34(1):3‒11. . 10.1109/tpwrs.2018.2868501

[13]	Alimin NN, Rahmin NAA, Ibragimov G, Nazihah MA. Multi-start local search for online scheduling in parallel operating theatre. Adv Math Sci J 2020;9(12):10915‒27. . 10.37418/amsj.9.12.75

[14]	Lieder A, Stolletz R. Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways. Transp Res Part E 2016;88:167‒88. . 10.1016/j.tre.2016.01.015

[15]	Yuan J, Ng CT, Cheng T. Scheduling with release dates and preemption to minimize multiple max-form objective functions. Eur J Oper Res 2020;280(3):860‒75. . 10.1016/j.ejor.2019.07.072

[16]	Kugler T, Kausel EE, Kocher MG. Are groups more rational than individuals? A review of interactive decision making in groups. WIREs Cogn Sci 2012;3(4):471‒82. . 10.1002/wcs.1184

[17]	Klein M, Faratin P, Sayama H, Bar-Yam Y. Negotiating complex contracts. Group Decis Negot 2003;12(2):111‒25.

[18]	Schneeweiss C. Distributed decision making. Berlin: Springer; 2003. . 10.1007/978-3-540-24724-1

[19]	Lu Y, Yang L, Yang K, Gao Z, Zhou H, Meng F, et al. A distributionally robust optimization method for passenger flow control strategy and train scheduling on an urban rail transit line. Engineering 2022;12:202‒20. . 10.1016/j.eng.2021.09.016

[20]	Renna P. Multi-agent based scheduling in manufacturing cells in a dynamic environment. Int J Prod Res 2011;49(5):1285‒301. . 10.1080/00207543.2010.518736

[21]	Arrow KJ, Sen A, Suzumura K. Handbook of social choice and welfare. Volume 2. London: Elsevier; 2011. . 10.1016/s0169-7218(10)00013-4

[22]	Deconinck G, De Craemer K, Claessens B. Combining market-based control with distribution grid constraints when coordinating electric vehicle charging. Engineering 2015;1(4):453‒65. . 10.15302/j-eng-2015095

[23]	Tang J, Zeng C, Pan Z. Auction-based cooperation mechanism to parts scheduling for flexible job shop with inter-cells. Appl Soft Comput 2016;49:590‒602. . 10.1016/j.asoc.2016.08.046

[24]	Zhu Q, Wang X. Auction-based capacity allocation in two parallel machines with inclusive processing set restrictions. Math Probl Eng 2022;2022:1‒11. . 10.1155/2022/2045630

[25]	Hall NG, Liu Z. Market good flexibility in capacity auctions. Prod Oper Manag 2013;22(2):459‒72. . 10.1111/j.1937-5956.2012.01355.x

[26]	Song W, Kang D, Zhang J, Xi H. A multi-unit combinatorial auction based approach for decentralized multi-project scheduling. Auton Agent Multi-Agent Syst 2017;31(6):1548‒77. . 10.1007/s10458-017-9370-z

[27]	Daoud A, Balbo F, Gianessi P, Picard G. ORNInA: a decentralized, auction-based multi-agent coordination in ODT systems. AI Commun 2021;34(1):37‒53. . 10.3233/aic-201579

[28]	Zade M, Lumpp SD, Tzscheutschler P, Wagner U. Satisfying user preferences in community-based local energy markets—auction-based clearing approaches. Appl Energy 2022;306:118004. . 10.1016/j.apenergy.2021.118004

[29]	Kutanoglu E, Wu SD. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Trans 1999;31(9):813‒26. . 10.1080/07408179908969883

[30]	Zeng C, Tang J, Fan Z, Yan C. Auction-based approach for a flexible job-shop scheduling problem with multiple process plans. Eng Optim 2019;51(11):1902‒19. . 10.1080/0305215x.2018.1561884

[31]	Zeng C, Qi G, Liu Z, Tang J, Fan ZP, Yan C. Auction-based approach with improved disjunctive graph model for job shop scheduling problem with parallel batch processing. Eng Appl Artif Intell 2022;110:104735. . 10.1016/j.engappai.2022.104735

[32]	Kong W, Lei Y, Ma J. Virtual machine resource scheduling algorithm for cloud computing based on auction mechanism. Optik 2016;127(12):5099‒104. . 10.1016/j.ijleo.2016.02.061

[33]	Dewan P, Joshi S. Auction-based distributed scheduling in a dynamic job shop environment. Int J Prod Res 2002;40(5):1173‒91. . 10.1080/00207540110098445

[34]	Dewan P, Joshi S. Implementation of an auction-based distributed scheduling model for a dynamic job shop environment. Int J Comput Integr Manuf 2001;14(5):446‒56. . 10.1080/09511920010022486

[35]	Masin M, Pasaogullari MO, Joshi S. Dynamic scheduling of production-assembly networks in a distributed environment. IIE Trans 2007;39(4):395‒409. . 10.1080/07408170601089505

[36]	Araúzo JA, Pajares J, Lopez-Paredes A. Simulating the dynamic scheduling of project portfolios. Simul Model Pract Theory 2010;18(10):1428‒41. . 10.1016/j.simpat.2010.04.008

[37]	Tosselli L, Bogado V, Martínez E. A repeated-negotiation game approach to distributed (re)scheduling of multiple projects using decoupled learning. Simul Model Pract Theory 2020;98:101980. . 10.1016/j.simpat.2019.101980

[38]

Vishalatchi M, Krishnamoorthy N, Sangeetha S. Optimised scheduling in cloud computing. In: Proceedings of 2017 International Conference on Algorithms, Methodology, Models and Applications in Emerging Technologies (ICAMMAET); 2017 Feb 16‒18; Chennai, India. Piscataway: IEEE; 2017. p. 1‒6. . 10.1109/icammaet.2017.8186712

[39]

Mukherjee P, Goswami S, Paul B, Chanda CK. Scheduling of generation and loads through market clearing auction in a dynamic power market. In: Proceedings of 2022 4th International Conference on Energy, Power and Environment (ICEPE); 2022 Apr 29‒May 1; Shillong, India. Piscataway: IEEE; 2022. p. 1‒6. . 10.1109/icepe55035.2022.9798194

[40]	Wellman MP, Walsh WE, Wurman PR, MacKie-Mason JK. Auction protocols for decentralized scheduling. Games Econ Behav 2001;35(1‒2):271‒303.

[41]	Pan H, Gao H, Ma W, Liu J. Dynamic bidding strategy for electricity retailers considering multi-type demand response. In: Proceedings of 2020 IEEE Sustainable Power and Energy Conference (iSPEC); 2020 Nov 23‒25; Chengdu, China; Piscataway: IEEE; 2020. p. 1127‒32. . 10.1109/ispec50848.2020.9350983

[42]	Hsieh FS. Combinatorial reverse auction based on revelation of Lagrangian multipliers. Decis Support Syst 2010;48(2):323‒30. . 10.1016/j.dss.2009.08.009

[43]	Mansouri B, Hassini E. A Lagrangian approach to the winner determination problem in iterative combinatorial reverse auctions. Eur J Oper Res 2015;244(2):565‒75. . 10.1016/j.ejor.2015.01.053

[44]	Pennanen T. Efficient allocations in double auction markets. Math Oper Res 2022;47(2):1648‒63. . 10.1287/moor.2021.1182

[45]	Wang C, Dargahi F, Bhuiyan MFH. On the tradeoff between privacy and efficiency: a bidding mechanism for scheduling non-commercial services. Comput Ind 2012;63(6):610‒8. . 10.1016/j.compind.2012.01.012

[46]	Liu L, Wang C, Wang J. A combinatorial auction mechanism for surgical scheduling considering surgeon’s private availability information. J Comb Optim 2019;37(1):405‒17. . 10.1007/s10878-017-0247-5

[47]

Merz F, Schwindt C, Westphal S, Zimmermann J. An auction-based mechanism for the formation and scheduling of heterogeneous human-machine teams. In: Proceedings of 2021 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM); 2021 Dec 13‒16; Singapore, Singapore. Piscataway: IEEE; 2021. p. 863‒8. . 10.1109/ieem50564.2021.9672780

[48]	Ebrahimi A, Jeon HW, Lee S, Wang C. Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system: a comparison of four metaheuristic algorithms. Comput Ind Eng 2020;141:106295. . 10.1016/j.cie.2020.106295

[49]	Hung YF, Bao JS, Cheng YE. Minimizing earliness and tardiness costs in scheduling jobs with time windows. Comput Ind Eng 2017;113:871‒90. . 10.1016/j.cie.2016.12.023

[50]	He Y, Li Y, Wu T, Sutherland JW. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops. J Clean Prod 2015;87:245‒54. . 10.1016/j.jclepro.2014.10.006

[51]	Pinedo ML. Deterministic models: preliminaries. In: Pinedo ML, editor. Scheduling. Cham: Springer; 2016. p. 13‒32. . 10.1007/978-3-319-26580-3_2

[52]	Nguyen NT, Nguyen TT, Roos M, Rothe J. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Auton Agent Multi-Agent Syst 2014;28(2):256‒89. . 10.1007/s10458-013-9224-2

[53]	Fang KT, Lin BMT. Parallel-machine scheduling to minimize tardiness penalty and power cost. Comput Ind Eng 2013;64(1):224‒34. . 10.1016/j.cie.2012.10.002

[54]	Menezes FM, Monteiro PK. An introduction to auction theory. Oxford: Oxford University Press; 2004. . 10.1093/019927598x.001.0001

[55]	Nisan N. Bidding languages for combinatorial auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge: MIT Press Scholarship Online; 2005. p. 215‒32. . 10.7551/mitpress/9780262033428.003.0010

[56]	Ausubel LM, Milgrom P. Ascending proxy auctions. In: Cramton P, Shoham Y, Steinberg R, editors. Combinatorial auctions. Cambridge: MIT Press Scholarship Online; 2005. p. 79‒98. . 10.7551/mitpress/9780262033428.003.0004

[57]	Pikovsky A. Pricing and bidding strategies in iterative combinatorial auctions. Munich: Technische Universität München; 2008.

[58]	Wang Z, Feng Z, Zhang P. An iterative Hungarian algorithm based coordinated spectrum sensing strategy. IEEE Commun Lett 2011;15(1):49‒51. . 10.1109/lcomm.2010.111910.101806

[59]	Rabadi G, Moraga RJ, Al-Salem A. Heuristics for the unrelated parallel machine scheduling problem with setup times. J Intell Manuf 2006;17(1):85‒97. . 10.1007/s10845-005-5514-0

[60]	Liu Y, Wang L, Wang Y, Wang XV, Zhang L. Multi-agent-based scheduling in cloud manufacturing with dynamic task arrivals. Procedia CIRP 2018;72:953‒60. . 10.1016/j.procir.2018.03.138

[61]	Ðurasević M, Jakobović D. A survey of dispatching rules for the dynamic unrelated machines environment. Expert Syst Appl 2018;113:555‒69. . 10.1016/j.eswa.2018.06.053

[62]	Lee JH, Kim Y, Kim YB, Kim BH, Jung GH, Kim HJ. A sequential search method of dispatching rules for scheduling of LCD manufacturing systems. IEEE Trans Semicond Manuf 2020;33(4):496‒503. . 10.1109/tsm.2020.3029124

[63]	Liu R, Piplani R, Toro C. Deep reinforcement learning for dynamic scheduling of a flexible job shop. Int J Prod Res 2022;60(13):4049‒69. . 10.1080/00207543.2022.2058432

[64]	Cheng CY, Huang LW. Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. J Manuf Syst 2017;42:1‒10. . 10.1016/j.jmsy.2016.10.005