An iterative combinatorial auction mechanism for multi-agent parallel machine scheduling

Abstract

This paper focuses on the multi-agent parallel machines scheduling problem with consumer agents and resource agents. Within the context, all the agents are self-interested aiming at maximising their profits, and have private information, precluding the use of the centralised scheduling approaches that require complete information of all the consumer agents. Therefore, an iterative combinatorial auction mechanism based on a decentralised decision procedure is proposed to generate a collaborative scheduling scheme without violating information privacy. The developed approach adopts flexible bidding strategies to reduce the conflict in resource allocation, and a hybrid auction termination condition is developed to ensure the convergence of the approach while guaranteeing sufficient competition among agents. Experimental results show the developed approach generates high-quality solutions with a small price of anarchy compared with centralised approaches and outperforms the state-of-the-art decentralised scheduling approach in improving social welfare, especially for problems with a large number of consumer agents.

Keywords:

• multi-agent scheduling
• iterative combinatorial auctions
• decentralised decision-making
• resource allocation
• social welfare

1. Introduction

Multi-agent parallel machines scheduling problem (MPMSP) is characterised as a scheduling problem that the job to be processed might come from different agents competing for limited parallel machine resources (Agnetis et al. 2004; Lee et al. 2009; Agnetis et al. 2014). Many real-world scheduling problems in manufacturing and service operations can be considered as the proposed MPMSP, e.g. some consumers intend to process parts in a factory owning parallel machines, and several users share computing resources from a cloud computing centre that has parallel computers. Traditional centralised scheduling approaches are often used to solve a scheduling problem in two ways: (1) establish a weighted integrated objective function model and obtain an optimal solution (T. E. Cheng et al. 2014; Sadi, Soukhal, and Billaut 2014), but the weights of consumers are generated by a central decision-maker, making the various requirements of consumers cannot be satisfied; (2) a multi-objective optimisation model is constructed, and a Pareto solution set is generated (Yazdani, Khalili, and Jolai 2016; Y. Liu et al. 2018; Fu et al. 2019), while it is challenging to select a solution agreed by all consumers from the Pareto solution set. In addition, since the complexity of the problem increases significantly with the consumer increases, the problems that can be solved in these two ways are greatly limited, with most current researches focussing on only two or three agents (Perez-Gonzalez and Framinan 2014). Moreover, the centralised approach is applied under the assumption that the complete information is known by a central decision-maker. However, in many practical situations, agents are self-interested and may not be willing to disclose their private information (Klein et al. 2003; Lang, Fink, and Brandt 2016), which makes the centralised approach inapplicable. Compared with the centralised approach, the decentralised decision-making approach deals with resource allocation problems through multiple decision-makers competing fully and making compromise resulting in some kind of equilibrium in case of asymmetric information (Schneeweiss 2003). Therefore, a decentralised decision-making procedure can be an effective way to generate high-quality solutions when solving the multi-agent scheduling problem with incomplete information and more consumer agents.

Table

Abbreviations
Name	Description
MPMSP	Multi-agent parallel machines scheduling problem
ICA	Iterative combinatorial auction
ICAs	Iterative combinatorial auctions
NMSA	Negotiation mechanism inspired by simulated annealing
WDP	Winner determination problem
SA	Simulated annealing
GA	Genetic algorithm
PSO	Particle swarm optimisation
RCG	Relative growth rate
RSW	Ratio of different social welfares

The core of the decentralised decision-making approach is that the original fully-informed authority is replaced by local decision-makers with partial information, and a consensus will be reached through their competition and compromise. This idea that is comparable with market competition can be combined with some market mechanism theories in economics (Kutanoglu and Wu 1999), where the auction theory used to allocate goods and services is applied to work on the decentralised scheduling problem (Rosen and Madlener 2013). In particular, Kutanoglu and David Wu (1999) and Wellman et al. (2001) are the first two to introduce auction theory to solve the distributed scheduling problems. They developed a basic structure of the auction-based decentralised scheduling approach. Within the structure, the resources are regarded as market goods for auction, and bidders bid for the goods while the auctioneer determines whether the buyers win or lose the bids. Inspired by this idea, many researchers exploited auction in various fields, such as dynamic machine scheduling (Dewan and Joshi 2000, 2002), flexible job shop scheduling (Zeng et al. 2019), project scheduling (Song et al. 2016, 2017). However, few studies applied auction theory to the MPMSP. The designed auction-based approaches are well-directed and cannot be extended to MPMSP directly (Section 2). In addition, the problem scale solved by auction-based methods is limited due to the severe resource allocation conflicts. Thus, it is appropriate and necessary to develop a decentralised auction-based scheduling approach for MPMSP. Reducing the resource allocation conflicts among self-interested agents towards an agreement and allowing the resource scheduling aligning with social welfare are challenges (Krajewska and Kopfer 2006; Hall and Liu 2013).

This study focuses on the multi-agent parallel machine scheduling problem. Consumers who intend to process multiple jobs and a resource owner are considered as consumer agents and a resource agent. Both agents are self-interested to maximise individual profits and possess private information. The aim of this study is to develop an auction-based approach for generating a collaborative scheduling scheme from the perspective of operations and management. Hence, a multi-stage iterative combinatorial auction (ICA) mechanism is proposed to achieve the goal, which also extends the scale of MPMSP solved efficiently. In the proposed approach, flexible bidding strategies are adopted to reduce resource allocation conflicts, and a hybrid auction termination condition is set to guarantee the sufficient competition of consumer agents and the convergence of the mechanism simultaneously. The effectiveness of this approach is validated through extensive computational experiments.

The remainder of the paper is organised as follows: Section 2 introduces related work. In Section 3, the targeted MPMSP with incomplete information is described, and a centralised scheduling model with perfect information is built. Section 4 presents the proposed ICA mechanism. Section 5 shows computational experiments and results. Conclusions and future work are highlighted in Section 6.

2. Related work

Research efforts on the combinatorial auction for decentralised scheduling problems have been numerous. Kutanoglu and David Wu (1999) introduced a combinatorial auction-based scheduling framework for a job shop scheduling problem. They first regarded bid as a bundle of consecutive time slots and presented payment functions corresponding to the Lagrangian decomposition of the centralised problem. Afterwards, their works were extended by Dewan and Joshi (2002), Attanasio et al. (2006) and Sasaki and Nishi (2015). However, feasible solutions generated by a central decision-maker are needed in these approaches, which are inapplicable for the MPMSP with incomplete information. Considering the self-interested agent, Hall and Liu (2013) made a significant contribution by proposing the flexible block and adaptive asking pricing strategy in a single machine environment. Tang, Zeng, and Pan (2016) applied a reference matrix for bidders to modify bids, and Zeng et al. (2019) and Zeng, Tang, and Fan (2019) expanded this method to a flexible job shop scheduling problem and cell part scheduling, respectively. However, all the above auction-based approaches are not universal and cannot be applied to the MPMSP. Meanwhile, these approaches regard a job as a bidder agent, i.e. one agent per job, and thus the size of the problems that can be solved is limited. In other research fields, Song et al. (2016, 2017) and C.-B. Cheng and Lo (2017) developed combinatorial auction mechanisms for the multi-project problems, in which each agent is in charge of many activities. Bidders submit feasible solutions involving all activities as their bids. Tafsiri and Yousefi (2018) reported a similar method when generating bids in the cloud computing market. Nevertheless, the jobs processed on the parallel machines are independent and cannot be bid as a whole in machine scheduling problems. To the best of our knowledge, we address the MPMSP firstly, in which each agent has multiple jobs and all job information except processing time are private. It is necessary to develop an auction-based approach to solve it efficiently and expand the scale of the problem.

Iterative combinatorial auctions (ICAs) are typical cases of the combinatorial auction, which are designed to address the situation that bidders have little information about the auction (Parkes 2006). It has been implemented in some resource allocation problems in recent years. Karabatı and Yalçın (2014) developed an iterative auction mechanism with a single-minded bidding policy to solve the capacity problem in the supply chain. Abrache et al. (2013, 2014) studied the ICAs for multilateral procurement with a simple bidding language. Bidders in these approaches submit one bid or bundle of time slots per round, which cannot reduce the resource allocation conflicts and solve the large-scale problem effectively. Wang et al. (2011) proposed an iterative bidding framework for due-date management with submitting more than one bid. Amir, Sharon, and Stern (2015) handled the situation where many bundles are submitted by each agent in the multi-agent pathfinding problem. Hou, Wang, and Yan (2019) allowed users to bid for different preferred time windows at one time in electric vehicle charging scheduling problem. The similar ideas are also discussed in other decentralised decision-making problems (L. Liu, Wang, and Wang 2019; Bansal, Uzsoy, and Kempf 2020; Sen, Bagchi, and Chakraborty 2020; Ahn, Kim, and Kim 2021). Although these methods provide more allocation options for the auctioneer, the bids updating strategies are fixed, preventing bidders from making full use of the feedback information and weakening the performance of approaches. Besides, the unitary termination condition in the above approaches makes them converge slowly and inefficient when solving large-scale problems. Our research develops a flexible and adaptive bidding strategy with bidders submitting multiple bids and updating bids with flexible options, and a hybrid auction termination condition that combines the traditional setting of a fixed iteration round and the rule that no conflicts among bids. These two methods reduce the time slot allocation conflicts and make the proposed approach more efficient.

Apart from the auction-based approaches, several other decentralised approaches have been proposed to solve multi-agent scheduling problems, the most common of which is the negotiation mechanism based on the heuristic algorithm. Homberger (2012) first introduced a coordination mechanism based on an evolutionary search for an agent-based multi-project problem. Lang and Fink (2015) summarised the requirements for negotiation protocol established on general heuristic optimisation algorithms. Fink and Homberger (2013) developed a decentralised approach using ant colony optimisation, and then negotiation mechanisms inspired by simulated annealing and random search evolutionary are proposed by Lang, Fink, and Brandt (2016) and Homberger and Fink (2017), respectively. These negotiation mechanisms are easy to be implemented and can generate solutions that agents agree on by exploiting the evolutionary properties of heuristic algorithms, while using iterative voting methods to protect the agents' preference information. However, local and stochastic optimisation leads to unstable negotiation results, and even the negotiation tends to stall when there are many agents. Since the auction is followed by a series of steady and effective rules, the scheduling scheme obtained by the ICA mechanism keeps stable even with numerous agents. Note that the negotiation scheduling approach will be used as a benchmark to compare with the proposed ICA approach.

3. Problem statement

In this research, a set of competing consumer agents $CA=\left\{C{A}_1,C{A}_2,\dots ,C{A}_i,\dots ,C{A}_n\right\}$ and one resource agent $RA$ are considered. Each $C{A}_i$ has several jobs $J^i=\left\{J_1^i,J_2^i,\dots ,J_k^i,\dots ,J_{n_i}^i\right\}$, which have to be scheduled on identical parallel machines $M=\{M_1,M_2,\dots ,M_j,\dots ,M_m\}$ from $RA$. $J_k^i$ is the job k of $C{A}_i$. Each $J_k^i$ is characterised by a processing time $p_k^i$ and a due date $d_k^i$. A job $J_k^i$ generates revenue ${\pi }_k^i$ when processed before its due date and has a revenue loss of unit-time tardiness ${\omega }_k^i$. The machine resources belonging to $RA$ are divided into a set of consecutive time slots $T=\left\{1,2,\dots ,t,\dots ,T_{max}\right\}$, and each time slot t defines a time interval $\left[t-1,t\right]$ corresponding to a unit processing time. A standardised unit operating cost δ per time slot is considered. Based on the primary setting, some assumptions in this study are summarised as follows:

1. All jobs are completed on the machines.

2. All machines are available at the beginning of the planning horizon.

3. Each job can be processed on any machine, but it can only be processed on one machine simultaneously.

4. All jobs cannot be interrupted once being processed.

5. The processing time $p_k^i$ of job $J_k^i$ includes the setup time before it is processed.

6. $p_k^i$ is semi-public information known to $RA$ and $C{A}_i$, while $d_k^i$, ${\pi }_k^i$, and ${\omega }_k^i$ hold private information only known to $C{A}_i$, and δ is only known to $RA$.

In the ICAs model, consumer agents bid for machine resources they need, and we assume that they can bid resources for each job individually. The bidding price submitted by $C{A}_i$ for $J_k^i$ is $b_k^i$, which also defines the revenue that $RA$ can obtain by completing $J_k^i$. The total revenue of $C{A}_i$ is determined by the revenues of jobs, the prices for purchasing resources and revenue losses caused by tardiness. The tardiness $T_k^i$ of $J_k^i$ depends on its completion time $c_k^i$ and due date $d_k^i$. The revenue loss caused by the tardiness of job $J_k^i$ is given by $L_k^i={\omega }_k^i\ast max(c_k^i-d_k^i,0)$. Therefore, the total revenue of $C{A}_i$ is defined by $f\left(C{A}_i\right)=\sum _{k=1}^{n_i}({\pi }_k^i-b_k^i-L_k^i)$. The total profit of $RA$ is defined as $f\left(RA\right)=\sum _{k=1}^{n_i}\sum _{i=1}^n(b_k^i-\delta p_k^i)$.

Since the problem is solved in a decentralised decision-making manner, social welfare is needed to measure the system revenue (Nguyen et al. 2014). The social welfare of a schedule refers to the total profit of CA and $RA$: $SW=\sum _{i=1}^{n}f\left(C{A}_i\right)+f\left(RA\right)$.

The purpose of the ICA approach is to make all self-interested agents reach an agreement and negotiate a collaborative schedule plan that achieves social welfare maximisation. It is noted that the revenue of some jobs may be negative in the final negotiated schedule plan. Because all the jobs should be completed, when many agents or jobs compete for limited machine resources, some consumer agents concede, leading to some jobs' revenue damaged and even be negative. However, if they withdraw from the auction and give up processing these jobs, they may suffer more losses. This refers to the research of order acceptance. The focus of this research is to generate a negotiated schedule plan for orders that have been accepted.

A centralised decision model is also developed where all information is public (Appendix 1). The solution obtained for such a centralised model will constitute the benchmark profit levels in evaluating the ICA approach's performance.

4. Iterative combinatorial auction mechanism

In this section, a multi-stage iterative combinatorial auction mechanism is proposed to solve the MPMSP. The resource agent and consumer agents are regarded as an auctioneer and bidders, respectively. The auctioneer divides machine time resources into consecutive time slots for auction. Bidders obtain their required time slots through bidding. Since the conflict of resource allocation between self-interested agents is fierce, the ICA approach is developed to enable both parties to express individual requirements in each iteration, prompting them to coordinate and reach an agreement. Through ICAs, all jobs are processed in their required time slots, and then a consensus scheduling scheme is generated.

Since all agents have private information, some relevant assumptions should be made first. We assume that before the auction starts, the auctioneer has no knowledge of the bidders' bids, such as required time slots and offered bidding prices. Bidders know nothing about the auction items, such as time resources and asking prices. During the auction, bidders have no idea about other bidders' bids, and the auctioneer will not disclose any bidder's bidding information.

4.1. Multi-stage auction framework

In this section, a multi-stage auction framework is proposed. Each consumer agent has multiple jobs to be processed. If they bid for all the jobs simultaneously, they need to select bids from an exponential number of possible combinations. The resource agent needs to solve the winner determination problem with an extremely complex solution space. These are highly challenging for them. Therefore, a multi-stage auction framework is constructed, which is shown in Figure 1.

Figure 1. The multi-stage auction framework.

Specifically, in the first-stage auction, each bidder selects and bids for one job. When the first-stage auction ends, it enters the second stage, where each bidder chooses and bids for another job from the unprocessed jobs. This process will repeat until all the jobs are scheduled. At each auction stage, the number of bidders $n_g\le n$. The total auction stage is $max\left(n_i\right)$, where $n_i$ denotes the number of jobs of $C{A}_i$. When $n_i(i=1,2,\dots ,n)$ are different, those bidders withdraw from the auction after their relative fewer jobs are scheduled, and other bidders keep attending the auction. When $n_i(i=1,2,\dots ,n)$ are identical, $n_g=n$ and $max\left(n_i\right)=n_i$.

4.2. Iterative combinatorial auction approach

Under the multi-stage auction framework, the ICA approach is proposed to solve the scheduling problem at each stage. It is a round-based auction with the preset iteration round R, which is entirely different from the total number of auction stages $max\left(n_i\right)$. Besides, it is a non-decreasing procedure, where the prices in successive rounds are non-decreasing. The ICA approach consists of (1) call for auction, (2) bid determination, (3) winner determination, (4) auction items updating, (5) bid modification. The main structure is shown in Figure 2.

Figure 2. The main structure of the ICA approach.

4.2.1. Call for auction

Before the auction starts, each bidder selects one job that will be processed in the current auction stage and sends its information to the auctioneer. Then the auctioneer can release the auction items. The call for auction part contains two steps: (1) bidders select and send job information; (2) the auctioneer determines and informs auction items.

In the first step, each bidder selects a job considering maximising revenue equivalent to minimising the tardiness costs. In this sense, the job with the highest tardy probability and the largest tardiness cost from unprocessed jobs has the priority to be selected. The rule is defined as $max\left(\frac{{\omega }_k^i}{d_k^i-p_k^i}\right)$, $d_k^i\ne p_k^i$. If $d_k^i=p_k^i$ for a job, it will be chosen with the highest priority. If more than one job satisfies $d_k^i=p_k^i$, the bidder prioritises the job with a longer processing time. In the end, the bidders send these jobs and their processing times to the auctioneer.

In the second step, the auctioneer determines the auction items, including the set of time slots and the initial asking prices. The set of time slots for auction in the stage g is defined as follows: (1) $\begin{array}{r}{H}_g=\left\{S_g,S_g+1,\dots ,t,\dots ,S_g+\sum _{i=1}^{n_g}{p}_k^i\right\}\end{array}$(1) where $S_g$ denotes the earliest start time of the m parallel machines in the stage g auction, $g=1,2,\dots ,max\left(n_i\right)$; $S_1=0$ indicates all machines are available when the first-stage auction starts; $\sum _{i=1}^{n_g}{p}_k^i$ is the sum of the processing times of jobs submitted by the bidders in stage g.

The initial asking price is equivalent to the reserve price, which means the minimum price that the auctioneer will be accepted as the winning bid. The initial asking price per time slot is set as the unit operating cost δ. Since the ICA approach is a non-decreasing procedure, this setting ensures the resource agent not to process jobs at a price lower than his/her operating cost. A linear and anonymous policy for the asking price is considered. It is defined as $P\left(S\right)=\sum _{t\in S}{a}_t$, which means the asking price of a bundle of time slots is the sum of the prices of the time slots in S. The anonymous policy implies that the asking prices for any bidder are the same (Parkes 2006). The auctioneer informs the set of time slots and the initial asking prices to all bidders.

4.2.2. Bid determination

After being informed of the auction items, each bidder solves the bid determination problem. The bidder generates a 4-tuple bid $B_k^i=⟨J_k^i,(p_k^i,{\hat{c}}_k^i),{\hat{b}}_k^i⟩$, where $J_k^i$ and $p_k^i$ are the job submitted by the bidder and its processing time; ${\hat{c}}_k^i$ and ${\hat{b}}_k^i$ represent the required completion time and bidding price; $(p_k^i,{\hat{c}}_k^i)$ is decoded into a time block $[{\hat{c}}_k^i-p_k^i+1,{\hat{c}}_k^i]$ indicating a bundle of $p_k^i$ consecutive time slots from ${\hat{c}}_k^i-p_k^i+1$ to ${\hat{c}}_k^i$.

A myopic bidding strategy is adopted, where each bidder seeks to obtain the time blocks that maximise his/her revenue in the current iteration without considering the possibilities of future iterations. This bidding strategy is easy to be applied, and it is a natural choice for self-interested consumer agents who have no knowledge about other agents (Wellman et al. 2001; Hall and Liu 2013; Karabatı and Yalçın 2014). An adaptive bid pricing strategy is designed, where the bidding prices of bidders vary with their revenues. In general, bidders are willing to pay more for the time blocks with higher profits. The myopic bidding strategy and adaptive bid pricing policy make the bidders' bids revolve toward maximising their revenue, which will be incarnated in the final scheduling scheme.

Since the proposed approach follows a multi-stage auction procedure, the bid pricing strategy's adaptability also means the consumer agent will update his/her bid pricing policy in the later auction stage according to the previous results. The update is mainly reflected in the change of parameter ${\lambda }_g$, which is a bidding price adjustment factor in the stage g auction. It is updated over the auction stage $1\le g\le max\left(n_i\right)$ by the rule (2) $\begin{array}{r}{\lambda }_g=\left\{\begin{array}{l}{\lambda }_1\ast \left[1+\left(\frac{\sum {\eta }_i^{\mathrm{\prime }}}{\sum {\eta }_i}+\frac{1}{d_k^i-S_g-p_k^i}\right)\right],\\ d_k^i-S_g-p_k^i\ne 0\\ {\lambda }_1\ast \left[1+\left(\frac{\sum {\eta }_i^{\mathrm{\prime }}}{\sum {\eta }_i}+1\right)\right],\\ d_k^i-S_g-p_k^i=0\end{array}\right.\end{array}$(2) where ${\lambda }_1$ is the initial price adjustment factor and a given constant; $\sum {\eta }_i$ denotes the total number of scheduled jobs of $C{A}_i$; $\sum {\eta }_i^{\mathrm{\prime }}$ means the number of tardy jobs in $\sum {\eta }_i$. $\frac{1}{d_k^i-S_g-p_k^i}$ represents the minimum probability that the bid job $J_k^i$ has tardiness in stage g auction, and it can be interpreted as the possibility of $C{A}_i$ increasing the bidding price.

The rule implies two levels of meaning. First, $\frac{\sum {\eta }_i^{\mathrm{\prime }}}{\sum {\eta }_i}$ indicates that the bidder takes into account the tardiness of their scheduled jobs. The more jobs that are postponed before, the more eager the bidder will increase the bidding price to obtain the optimal time block. Then, $\frac{1}{d_k^i-S_g-p_k^i}$ implies ${\lambda }_g$ is updated further based on the characteristics of the job $J_k^i$. It has three conditions: (1) when $d_k^i-S_g-p_k^i>0$, there are time blocks during which $J_k^i$ can be processed without revenue loss, so $C{A}_i$ is willing to pay more to win the target time blocks. (2) when $d_k^i-S_g-p_k^i<0$, the processing of $J_k^i$ in any period of $H_g$ causes revenue loss. Therefore, the value of $H_g$ is discounted for $C{A}_i$ and the willingness to increase bid is reduced. (3) When $d_k^i-S_g-p_k^i=0$, the time block $\left[S_g,S_g+p_k^i-1\right]$ is the only one that $J_k^i$ can be processed without any loss. $C{A}_i$ has a strong desire to get the optimal time block, and the probability for $C{A}_i$ to increase the bidding price is defined as 1.

The bid determination problem can be solved by Algorithm 1. Each bidder submits the time block $[{\hat{c}}_k^i-p_k^i+1,{\hat{c}}_k^i]$ with the largest revenue ${\hat{O}}_k^i$, which is coded as $(p_k^i,{\hat{c}}_k^i)$ in bid $B_k^i$. Since the bidder may have the same maximum profit for different time blocks, and two scenarios are considered: (1) If only time block A has the largest revenue, it is defined as a fixed time block. The bidder submits a bid $B_k^i=⟨J_k^i,(p_k^i,{\hat{c}}_k^i),{\hat{b}}_k^i⟩$, where $(p_k^i,{\hat{c}}_k^i)$ represents A (lines 13–15). (2) If multiple time blocks have the same largest revenue, the bidder submits them simultaneously but wins one of them at most. To reduce the bid's complexity, only the largest required completion time of these time blocks is submitted with a bid $B_k^i=⟨J_k^i,(p_k^i,max({\hat{c}}_k^i\left)\right),{\hat{b}}_k^i⟩$, where $(p_k^i,max({\hat{c}}_k^i\left)\right)$ is defined as flexible time blocks and represents all $\left[c_k^i-p_k^i+1,c_k^i\right]$ bundles of $p_k^i$ consecutive time slots in $\left\{S_g,S_g+1,\dots ,max\left({\hat{c}}_k^i\right)\right\}$ (lines 16–18). For example, if a bidder submits $(p_k^i,max({\hat{c}}_k^i\left)\right)=(3,8)$ and $S_g=2$, then the time blocks he/she bids for include $[2,4],[3,5],[4,6],[5,7]$, and $[6,8]$. It is rational for the bidder, since he/she would have a greater chance of winning by providing the auctioneer with more resource allocation options.

4.2.3. Winner determination

When the auctioneer receives the submitted seal bids, he/she executes the winner determination to decide the provisional winners and the final winners. Winners who temporarily win and keep bidding in the next round are called provisional winners. In contrast, those who win the bids obtaining the target time blocks and stop bidding are described as final winners. This is introduced with two parts: termination condition and winner determination algorithm.

4.2.3.1 Termination condition

Generally, the ICAs will close when no resource allocation conflict among bidders. Alternatively, it may close when the auction reaches a fixed preset round. The resource allocation conflicts are inevitable and intense when multiple self-interested agents compete for limited resources. If the former is regarded as the termination condition, the auction may run in an infinite loop and cannot converge. While if we consider the latter only, the auction may run ineffectively when the round is large, but the bidders cannot compete adequately when it is small. Therefore, a hybrid termination condition that merges the two is developed, under which the auctions can have a rolling closure, and the sufficient competition of bidders and the convergence of the ICAs are guaranteed. It is summarised as follows:

1. Condition A: when no resource allocation conflict among bids, all winning bidders are the final winners, and the auctions end.

2. Condition B: when the auction reaches the fixed preset round, the provisional winners in the last round become final winners (Abrache et al. 2007), and the auction stops temporarily. The losing bidders keep bidding in a new auction until condition A is satisfied.

4.2.3.2 Winner determination algorithm

The auctioneer solves the winner determination problem (WDP) aiming at maximising profit. In the combinatorial auctions, the WDP is always NP-complete (Sandholm et al. 2002), and metaheuristic approaches can solve it effectively (Boughaci 2013). In this research, the WDP model of allocating time blocks to bidders can be seen as a variation of the knapsack model. A winner determination algorithm motivated by Simulated Annealing (SA) algorithm (Leung et al. 2012) is designed to solve it. Algorithm 2 shows the pseudo-code for the proposed winner determination algorithm.

Winner determination takes place in each round of auctions until the termination condition A is satisfied. Moreover, the bidders who submit one bid with flexible time blocks or multiple bids win one target time block at most.

4.2.4. Auction items updating

In the proposed ICA approach, the auctioneer uses asking prices as queries to access the bidder's preferences, and the bidders need information feedback to improve their bids. Therefore, the auctioneer updates the auction items containing time slots and asking prices after solving the WDP.

The set of time slots is updated when the termination condition B is satisfied, for the allocated time slots need to be eliminated. The updated set of time slots is ${H_g}^{\mathrm{\prime }}=H_g-\sum t_a$, where $\sum t_a$ denotes the sum of time slots that have been allocated.

At the end of each round auction, the auctioneer updates the asking prices. The auctioneer updates the asking prices based on the degree of competition of time slots to improve its profit. On the other hand, the bidders modify bids to increase the probability of winning. The rule of updating the asking prices is: (1) if the time slot t is competed by bidders, the maximum bidding price for it in round r will be used as the asking price in the round $r+1$; (2) if no bidder bids for t, its asking price remains unchanged, which is summarised as follows: (3) $\begin{array}{rl}{a}_t^{r+1}& =\left\{\begin{array}{ll}max\left(\frac{{\hat{b}}_k^i}{p_k^i}\times {\eta }_{it}\right),& \mathrm{\exists }{\eta }_{it}\ne 0\\ a_t^r,& {\eta }_{it}=0\end{array}\right.\end{array}$(3) (4) $\begin{array}{rl}{\eta }_{it}& =\left\{\begin{array}{ll}1,& \mathrm{i}\mathrm{f}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{t}t\mathrm{i}\mathrm{s}\mathrm{b}\mathrm{i}\mathrm{d}\mathrm{b}\mathrm{y}C{A}_i\\ 0,& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.\end{array}$(4)

4.2.5. Bid modification

After being informed of the bidding results at round $r(r\ge 1)$, the rational bidders may use different bidding strategies to increase the probability of winning at the round r + 1, flexible bidding strategies, therefore, are designed for different bidders.

For the provisional winners, the bidding strategy stays unchanged. They submit the same bids in the round r + 1 as in the round r. For the losing bidders, two alternative strategies are designed for different scenarios. Firstly, if a bidder loses three times in a row in the round $r(r\ge 3)$, he/she submits additional time blocks with the second-largest revenue, which means that the bidder submits two bids in the round r + 1. If the same situation occurs again, this bidder will create another new bid with the third-largest revenue, and the process repeats. The design of losing bid three times here is analogous to the lot knocking down after three calls in many real-world auctions. Secondly, if a bidder loses less than three times in the round $r(r\ge 1)$, he/she generates a new bid but still bids for the time blocks with the largest revenue. All the new bids are generated using Algorithm 1 based on the updated set of time slots and asking prices.

4.3. Multi-stage iterative combinatorial auction approach

Based on the description above, a multi-stage iterative combinatorial auction approach with five parts is presented to solve the targeted MPMSP. A flow chart of the approach is shown in Figure 3. The detailed steps are summarised in Algorithm 3.

Figure 3. Overall flowchart of the proposed multi-stage ICA approach.

5. Computational experiments

In this section, three sets of computational experiments are performed to evaluate the performance of the proposed ICA mechanism. All the experiments are performed in Python and run on a 3.6 GHz PC with an Intel Core i7 CPU and 8 GB of RAM.

5.1. Generation of problem instances

Since no benchmark instances are available for the focussed problem, the test problem instances are generated based on relevant literature. The problem involves machines $m\in \left\{3,5,10,15,20\right\}$, and the ratio of the number of consumer agents n to the machines is $R_{n/m}\in \left\{2,3,4,5,6\right\}$, which reflects the severity of the resource allocation conflict among consumer agents. The larger the $R_{n/m}$, the more intense the conflict. Since the different $n_i$ has no effects on the performance of the ICA approach, we assume the same $n_i$ for the ease of understanding, i.e. $n_c=n_i,(i=1,2,\dots ,n)$. The parameter has the values $n_c\in \left\{5,7,10,15\right\}$. The processing time $p_k^i$, revenue ${\pi }_k^i$ and the revenue loss of unit-time tardiness ${\omega }_k^i$ are generated by employing rules presented by Hall and Liu (2013), while the due date $d_k^i$ is based on the method introduced by Biskup, Herrmann, and Gupta (2008). They are all uniformly distributed integers. Precisely, $p_k^{\left(i\right)}\sim U[1,10]$; ${\omega }_k^i\sim U[1,10]$; $d_k^i\sim U[p_k^i,max(p_k^i,\alpha \ast P/m\left)\right]$, where $P=\sum _{k=1}^{n_c}\sum _{i=1}^n{p}_k^i$ and $\alpha \in \left\{0.6,0.8,1\right\}$; ${\pi }_k^i\sim U[\text{β}\ast \delta \ast p_k^i,\gamma \ast \delta \ast P/m]$, where $\text{β}=2$ and $\gamma \in \left\{0.4,0.6,0.8\right\}$. We define the initial price adjustment factor ${\lambda }_1$ and the operating cost δ per time slot as constants, ${\lambda }_1=0.1$ and $\delta =4$ (Kutanoglu and David Wu 1999; Hall and Liu 2013). For each of the $5\times 5\times 4\times 3\times 3=900$ possible parameter combinations, three problem instances are generated randomly, with a total of 2700. We run each instance five times and take the average value as the final solution.

5.2. Experimentation and results analysis

This section presents a computational study for evaluating the performances of the proposed ICA approach. Regarding the social welfare, we compare the ICA approach with a state-of-the-art decentralised negotiation mechanism inspired by simulated annealing (NMSA) proposed by Lang, Fink, and Brandt (2016) and two centralised approaches: genetic algorithm (GA) (Chaudhry and Elbadawi 2017) and particle swarm optimisation (PSO) (Fang and Lin 2013). Compared with NMSA, the relative growth rate (RGR) is applied to measure the promotion of social welfare. In parallel, we compute the ratio of the social welfare (RSW) of ICA to that of the centralised approaches. This is synonymous with the price of anarchy that measures to what extent the self-interest of the agents deteriorates the solutions compared to the results determined by a central authority with complete information (Roughgarden and Tardos 2007). The performance of the ICA is positively correlated with RCG and RSW. They are calculated by the formulas (5(5) $\begin{array}{rl}RGR& =\frac{S{W}_{ica}-S{W}_{nmsa}}{S{W}_{nmsa}}\times 100\mathrm{\%}\end{array}$(5) ) and (6(6) $\begin{array}{rl}RSW& =\frac{S{W}_{ica}-S{W_c}^{\ast }}{S{W_c}^{\ast }}\times 100\mathrm{\%}\end{array}$(6) ): (5) $\begin{array}{rl}RGR& =\frac{S{W}_{ica}-S{W}_{nmsa}}{S{W}_{nmsa}}\times 100\mathrm{\%}\end{array}$(5) (6) $\begin{array}{rl}RSW& =\frac{S{W}_{ica}-S{W_c}^{\ast }}{S{W_c}^{\ast }}\times 100\mathrm{\%}\end{array}$(6) where $S{W}_{ica}$ and $S{W}_{nmsa}$ represent the social welfare obtained by the proposed ICA approach and NMSA, respectively. $S{W_c}^{\ast }$ is a better solution generated by GA and PSO for the same problem instance based on the centralised model in Appendix 1, because the optimal solution should be used as the benchmark.

5.2.1. Experiment 1

The first experiment verifies the effectiveness of the ICA approach. The experiment was conducted with the parameter set in Section 5.1 and 2000 iteration rounds. The results are shown in Tables 1–2, where $MPm\mathrm{\_}n$ involves $n_c\in \left\{5,7,10,15\right\}$. For detailed results of each $MPm\mathrm{\_}n\mathrm{\_}{n}_c$, see Appendix 2. Note that both RGR and RSW are used when m = 3, 5 (except $MP5\mathrm{\_}30$), but only apply RSW when m>5. Since the NMSA has been tested to be more suitable for solving the problem within 19 agents, its performance is poor for more agents. We do not show them in the cases of $MP5\mathrm{\_}30$ and m>5 with more than 25 agents since they are less meaningful.

Table 1. Results obtained by different approaches for instances with m = 3 and 5.

$\alpha \times \gamma$	$0.6\times 0.4$		$0.6\times 0.6$		$0.6\times 0.8$		$0.8\times 0.4$		$0.8\times 0.6$		$0.8\times 0.8$		$1.0\times 0.4$		$1.0\times 0.6$		$1.0\times 0.8$		Average
$MPm\mathrm{\_}n$	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW
$MP3\mathrm{\_}6$	−1.92%	92.95%	0.20%	95.20%	0.33%	96.26%	0.68%	95.71%	0.14%	96.31%	0.37%	96.84%	−0.22%	96.40%	0.68%	96.64%	1.28%	96.91%	0.17%	95.91%
$MP3\mathrm{\_}9$	1.34%	93.46%	1.31%	95.09%	1.82%	95.10%	1.49%	95.14%	1.73%	95.54%	1.68%	96.04%	1.65%	95.11%	2.03%	95.84%	2.48%	96.54%	1.73%	95.32%
$MP3\mathrm{\_}12$	2.24%	92.62%	3.29%	95.40%	4.01%	95.02%	3.14%	94.80%	3.49%	95.28%	3.96%	95.52%	3.84%	94.45%	4.20%	95.49%	4.38%	95.25%	3.62%	94.87%
$MP3\mathrm{\_}15$	3.07%	92.30%	4.39%	94.47%	5.06%	95.24%	5.15%	94.55%	5.37%	94.77%	5.13%	94.81%	5.48%	94.06%	5.66%	94.73%	5.44%	95.27%	4.97%	94.46%
$MP3\mathrm{\_}18$	5.48%	91.48%	6.69%	93.99%	6.66%	94.50%	7.06%	94.11%	7.46%	93.99%	8.31%	94.41%	6.96%	93.32%	7.60%	94.09%	8.65%	95.10%	7.21%	93.89%
Average	2.04%	92.56%	3.18%	94.83%	3.57%	95.22%	3.50%	94.86%	3.64%	95.18%	3.89%	95.52%	3.54%	94.67%	4.03%	95.36%	4.45%	95.81%	2.04%	94.89%
$MP5\mathrm{\_}10$	1.57%	93.00%	2.51%	95.28%	2.84%	95.83%	2.64%	95.44%	2.98%	95.58%	3.09%	95.21%	3.92%	95.27%	4.33%	95.64%	4.39%	95.72%	3.14%	95.22%
$MP5\mathrm{\_}15$	3.25%	92.41%	4.43%	94.48%	4.88%	95.85%	4.51%	94.42%	5.24%	95.07%	5.59%	95.54%	5.75%	94.78%	6.23%	94.58%	6.99%	95.39%	5.21%	94.72%
$MP5\mathrm{\_}20$	9.68%	92.00%	13.22%	94.56%	13.62%	95.67%	14.34%	94.79%	14.55%	95.60%	15.06%	95.65%	14.08%	94.48%	14.38%	95.70%	14.36%	94.58%	13.70%	94.78%
$MP5\mathrm{\_}25$	18.52%	91.17%	21.73%	93.97%	22.37%	94.84%	22.54%	94.83%	22.51%	94.57%	23.36%	94.39%	23.27%	94.42%	23.20%	93.73%	23.04%	93.39%	22.28%	93.92%
$MP5\mathrm{\_}30$		90.47%		93.47%		93.59%		94.74%		94.26%		93.29%		93.42%		92.65%		93.13%		93.22%
Average	8.25%	91.81%	10.47%	94.35%	10.93%	95.16%	11.01%	94.84%	11.32%	95.02%	11.77%	94.81%	11.75%	94.47%	12.03%	94.46%	12.19%	94.44%	8.25%	94.37%

Table 2. Results of different approaches for instances with m = 10, 15, and 20.

$\alpha \times \gamma$	$0.6\times 0.4$	$0.6\times 0.6$	$0.6\times 0.8$	$0.8\times 0.4$	$0.8\times 0.6$	$0.8\times 0.8$	$1.0\times 0.4$	$1.0\times 0.6$	$1.0\times 0.8$	Average
$MPm\mathrm{\_}n$	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW
$MP10\mathrm{\_}25$	90.85%	97.32%	97.06%	96.12%	96.46%	96.11%	95.36%	95.55%	95.53%	95.59%
$MP10\mathrm{\_}30$	90.49%	94.80%	94.92%	94.96%	95.15%	94.92%	95.38%	95.08%	94.66%	94.48%
$MP10\mathrm{\_}40$	89.95%	91.84%	95.09%	93.54%	94.03%	93.90%	94.35%	94.66%	94.35%	93.52%
$MP10\mathrm{\_}50$	89.29%	92.90%	93.39%	92.76%	92.96%	92.88%	93.39%	93.41%	93.17%	92.68%
$MP10\mathrm{\_}60$	88.45%	90.89%	92.90%	93.31%	93.43%	91.73%	92.21%	91.65%	92.67%	91.91%
Average	89.81%	93.55%	94.67%	94.14%	94.41%	93.91%	94.14%	94.07%	94.08%	93.64%
$MP15\mathrm{\_}30$	89.82%	94.58%	96.00%	95.80%	95.73%	95.86%	94.85%	95.32%	95.66%	94.85%
$MP15\mathrm{\_}45$	88.55%	92.15%	95.38%	93.52%	94.59%	95.40%	94.71%	94.01%	94.59%	93.65%
$MP15\mathrm{\_}60$	88.81%	89.80%	93.71%	92.27%	94.01%	92.97%	93.02%	94.19%	94.02%	92.53%
$MP15\mathrm{\_}75$	87.91%	89.32%	92.25%	91.65%	92.33%	92.35%	92.20%	92.35%	92.01%	91.37%
$MP15\mathrm{\_}90$	84.63%	86.45%	91.59%	91.23%	90.31%	91.23%	91.10%	90.65%	91.53%	89.86%
Average	87.94%	90.46%	93.78%	92.89%	93.39%	93.56%	93.18%	93.30%	93.56%	92.45%
$MP20\mathrm{\_}40$	88.99%	90.66%	91.97%	91.79%	91.34%	92.90%	92.46%	91.85%	90.69%	91.40%
$MP20\mathrm{\_}60$	86.60%	88.58%	90.98%	89.73%	89.95%	89.38%	90.89%	90.49%	89.88%	89.61%
$MP20\mathrm{\_}80$	82.91%	84.44%	88.74%	88.24%	86.76%	86.92%	87.52%	88.67%	89.98%	87.13%
$MP20\mathrm{\_}100$	78.68%	80.71%	83.10%	82.03%	83.00%	82.84%	81.94%	82.99%	86.14%	82.38%
$MP20\mathrm{\_}120$	70.89%	77.25%	77.86%	77.01%	77.32%	77.68%	77.99%	77.77%	78.08%	76.87%
Average	81.61%	84.33%	86.53%	85.76%	85.67%	85.95%	86.16%	86.35%	86.95%	85.48%

The proposed ICA approach yields better solutions than NMSA in 94.84% of cases within 20 consumer agents in terms of RCG (Tables A1–A2 in Appendix 2). As shown in Tables 1–2, it improves social welfare by 4.97% on average. Moreover, the more the consumer agents are, the more significant the improvement of RCG is, and the better the ICA performs. This is mainly because the ICA approach adopts a hybrid termination condition that allows the bidder to withdraw from the auction when he/she wins the target time block, which reduces the complexity of the problem with large-scale consumer agents.

For the RSW, the ICA approach generates greater than 90% RSW in 91.22% of 2700 problem instances (Tables A1–A5 in Appendix 2). As shown in Tables 1–2, the four average RSW are 94.89%, 94.42%, 93.64% and 92.45% for 3, 5, 10, and 15 machines. These signify that the ICA approach can solve the MPMSP under incomplete information efficiently with a low price of anarchy, even though there is a slight deterioration as consumer agents grow (machines increase). However, Table 2 shows that the average RSW is only 85.48% for 20 machines, and RSW is less than 90% in 75.15% of the instances (Table A5 in Appendix 2). It even reduces to less than 80% for 120 consumer agents. It is challenging to obtain high-quality solutions by the proposed approach for the problems with large-scale consumer agents. Since the performance is relatively poor, we leave this case out in the remaining experiments.

We compare the results in Tables 1–2 with different parameters, where α and γ determine the due date and revenue of a job. Given the parameter α, the average RSWs are 91.11%, 92.62%, 92.73% for $\alpha =0.6,$ $\alpha =0.8,$ $\alpha =1.0$, repesctively. The ICA approach might be affected by the due date, and it performs slightly better in the cases with the more relaxed due date. For the parameter γ, no evidence shows that it could affect the approach. However, there is a special case that the combination $\alpha \times \gamma =0.6\times 0.4$ has smaller RCG and RSW than those of the other two combinations $0.6\times 0.8$ and $0.6\times 1.0$. The possible reason is that the approach is worsened by too small revenue under the tightened due date constraint. The ICA approach is designed as a multi-stage auction mechanism, where part of all jobs are scheduled at each stage. It ensures the consumer agent prioritises the most urgent one but may cause high tardiness costs for other jobs with tighter due dates, thus reducing the overall social welfare. This deficiency becomes more significant when the due date constraints are tighter, and the limited revenue makes it compounded further.

5.2.2. Experiment 2

The second experiment is conducted to test the influence of iteration round changes on the ICA approach, where $m\in \left\{3,5,10,15\right\}$ and $n_c=5$. The results are shown in Figure 4.

Figure 4. Performance varies with iteration rounds: (a) m = 3; (b) m = 5; (c) m = 10; (d) m = 15.

It can be seen that the iteration rounds have a significant positive impact on the performance of the approach, and the impact varies with the change of the parameter $R_{n/m}$, indicating the intensity of resource allocation and the number of consumer agents. In general, its performance is improved with the increase of iteration rounds and gradually stabilises. When $R_{n/m}$ is small, the influence is relatively slight, and high-quality solutions can be obtained in fewer rounds. However, the larger the $R_{n/m}$ is, the more severe the impact is, and the more rounds are needed to generate stable and excellent solutions. In addition, under the same $R_{n/m}$, the growth of consumer agents (increase of machines in Figure 4) makes the effect more considerable. For example, when $R_{n/m}=3$, the ICA approach deteriorates with the raise of machines under the same rounds, and more rounds are needed to achieve stability, as seen from the four blue lines in Figure 4.

To summarise, the proposed ICA approach's performance can be improved by increasing the iteration rounds, especially for problems involving a large number of consumer agents. However, the unlimited increase makes no sense in improving the performance further and imposes computational costs.

5.2.3. Experiment 3

In the third experiment, we study the scalability of the problems solved by the proposed ICA approach efficiently regarding two parameters $R_{n/m}$ and $n_c$, which imply the numbers of consumer agents and jobs.

Figure 5 shows the change of ICA' performance under different numbers of consumer agents n, where $n=R_{n/m}\ast m$. One variable $R_{n/m}$ is kept, and $n_c=5$. Almost all social welfares decrease as consumer agents increase for the same machines, and the magnitude of reduction becomes greater with the increase of machines. This results from the fact that more consumer agents make the conflict in resource allocation more intense, making it harder to reach an agreement. Although its performance is deteriorating, the range of solvable problems is still extended, especially for three machines; it still generates a high-quality solution with 90.06% RSW involving 48 consumer agents ($R_{n/m}=16$).

Figure 5. Effect of the number of consumer agent changes on the ICA approach.

Figure 6 depicts the effects of the increase of jobs $n_c$ on ICA approach, which also illustrates the effectiveness of the designed multi-stage auction mechanism as $n_c$ equals to the auction stage. One variable $n_c$ is kept, and $R_{n/m}=5$. Overall, the performance of the ICA decreases slightly as the number of jobs increases. This may result from a bullwhip-like effect by not considering the subsequent auction stages when solving the WDP at the current stage. Note that when jobs increase sharply (machines increases, $\mathrm{j}\mathrm{o}\mathrm{b}\mathrm{s}=R_{n/m}\times m\times n_c$), the range of the decline in social welfare becomes smaller in contrast. It does not mean that the ICA approach performs better for enormous jobs, especially for 20 machines with 4500–6750 jobs. The benchmark solutions obtained by the centralised approach become worse when the jobs increase dramatically, as if the ICA still maintains good social welfare. However, the decreasing range of the decline proves the stability and effectiveness of the multi-stage auction framework, which improves the deterioration in large-scale problems.

Figure 6. Effect of the number of jobs changes on the ICA approach.

6. Conclusions and future work

In this research, an iterative combinatorial auction (ICA) mechanism is proposed for MPMSP, in which the agents are self-interested and have private information. The ICA approach focuses on generating a collaborative schedule plan that can achieve social welfare maximisation. It contains five parts: call for auction, bid determination, winner determination, auction items updating and bid modification. Flexible bidding strategies and a hybrid auction termination condition are designed to reduce the resource allocation conflict and enable the approach to converge while ensuring sufficient competition among bidders. To verify the performance of the approach, three sets of computational experiments are performed on 2700 problem instances. The experiments demonstrate that the proposed ICA can generate high-quality solutions than the state-of-the-art decentralised approach NMSA, especially for problems with a large number of agents, and can generate high social welfare scheduling schemes with a small price of anarchy compared with the centralised approach.

Although the problem model considered in this paper is generic and the proposed approach can solve it efficiently, some real-world problems could be more complex, and the approach needs to be optimised. For future work, we will consider the setup time separately instead of assuming it being within the processing time, which makes it closer to real-world production. As for the ICA approach, the auctioneer predicts the potential situation in the next stage according to bidders' previous bidding behaviours when solving the WDP at the current stage, thus reducing the deterioration caused by the bullwhip-like effect.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by the National Natural Science Foundation of China under Grant [51975482] and the China Scholarship Council.

Notes on contributors

Yaqiong Liu

Yaqiong Liu is a Ph.D. student in Mechanical Engineering, Northwestern Polytechnical University, China and currently a guest Ph.D. student at KTH, Stockholm, Sweden. She received the M.S. in industrial engineering from the South China University of Technology in 2016. Her research interests are focus on multi-agent scheduling optimisation and industrial engineering.

Shudong Sun

Shudong Sun received the Ph.D. degree in mechanical engineering from Nanjing University of Aeronautics and Astronautics, China, in 1989. He has been a Professor with the School of Mechanical Engineering, Northwestern Polytechnical University (NWPU), China, since 1993. He is the Director of the Key Laboratory of Industrial Engineering and Intelligent Manufacturing. His research interests include decentralised multi-agent scheduling, multi-robot system modelling and optimisation.

Xi Vincent Wang

Xi (Vincent) Wang is an Associate Professor in the IIP Department of Production Engineering, KTH Sweden. He is working with the division of Sustainable Manufacturing Systems (SPS). Vincent received his Ph.D. and Bachelor in Mechanical Engineering from the University of Auckland (New Zealand) and Tianjin University (China), respectively in 2013 and 2008. Vincent's main research focus is on Cloud-based manufacturing, sustainable manufacturing, robotics, computer-aided design, process planning, and manufacturing. He is the managing editor of International Journal of Manufacturing Research (IJMR), Editorial board member of SME Journal of Manufacturing Systems (JMS), Array – OpenAccess Journal by Elsevier, International Journal of Advance Robotics & Expert Systems (JARES), and Remote Sensing.

Lihui Wang

Lihui Wang is currently a Chair Professor with the KTH Royal Institute of Technology, Stockholm, Sweden. He is actively engaged in various professional activities. His research interests are focussed on cyber-physical systems, cloud manufacturing, predictive maintenance, real-time monitoring and control, human-robot collaboration, and sustainable manufacturing systems. He is a fellow of Canadian Academy of Engineering, CIRP, SME, and ASME, a registered Professional Engineer in Canada, and a Board Director of the North American Manufacturing Research Institution of SME. He is also the Editor-in-Chief of International Journal of Manufacturing Research, Journal of Manufacturing Systems, as well as Robotics and Computer-Integrated Manufacturing.

Appendices

Appendix 1. Centralised model under complete information

Let N be the total number of jobs, l be the index $1\le l\le N$ of positions on the machines, $S_{jl}$ represents the start time of the job at the position l on machine $M_i$, $T_k^i$ defines the tardiness of $J_k^i$. $X_{kijl}=\left\{\begin{array}{ll}1& \mathrm{i}\mathrm{f}\mathrm{j}\mathrm{o}\mathrm{b}{J}_k^i\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{d}\mathrm{o}\mathrm{n}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}l\mathrm{o}\mathrm{f}\mathrm{m}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{e}j\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right\}.$The model under complete information is to maximise the system revenue. Under the assumption in Section 3.1, the centralised decision model is formulated as follows: (A1) $\begin{array}{rl}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}& \sum _{k=1}^{n_i}\sum _{i=1}^n\sum _{j=1}^m\sum _{l=1}^N(X_{kijl}{\pi }_k^i-\delta p_k^i-{\omega }_k^i{T}_k^i)\end{array}$(A1) (A2) $\begin{array}{rl}& \sum _{k=1}^{n_i}\sum _{i=1}^n{X}_{kijl}\le 1,j=1,2,\dots ,m,\\ & l=1,2,\dots ,N;\end{array}$(A2) (A3) $\begin{array}{rl}& \sum _{j=1}^m\sum _{l=1}^N{X}_{kijl}=1,k=1,2,\dots ,n_i,\\ & i=1,2,\dots ,n;\end{array}$(A3) (A4) $\begin{array}{rl}& S_{jl+1}-S_{jl}=\sum _{k=1}^{n_i}\sum _{i=1}^n{X}_{kijl}\ast p_k^i,\\ & j=1,2,\dots ,m,l=1,2,\dots ,N-1;\end{array}$(A4) (A5) $\begin{array}{rl}& S_{jl}\ge 0,j=1,2,\dots ,m,l=1,2,\dots ,N;\end{array}$(A5) (A6) $\begin{array}{rl}& \begin{array}{rl}{T}_k^i& \ge S_{jl}+X_{kijl}\ast p_k^i-(1-X_{kijl})M-d_k^i,\\ & k=1,2,\dots ,n_i,i=1,2,\dots ,n,\\ & j=1,2,\dots ,m,l=1,2,\dots ,N;\end{array}\end{array}$(A6) (A7) $\begin{array}{rl}& T_k^i\ge 0,k=1,2,\dots ,n_i,i=1,2,\dots ,n;\end{array}$(A7) (A8) $\begin{array}{rl}& X_{kijl}=\left\{0,1\right\},k=1,2,\dots ,n_i,i=1,2,\dots ,n,\\ & j=1,2,\dots ,m,l=1,2,\dots ,N.\end{array}$(A8) The proposed model is based on Fang and Lin (2013). The objective function is to maximise the total revenue of consumer agents and the resource agent presented in Equation (A1(A1) $\begin{array}{rl}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}& \sum _{k=1}^{n_i}\sum _{i=1}^n\sum _{j=1}^m\sum _{l=1}^N(X_{kijl}{\pi }_k^i-\delta p_k^i-{\omega }_k^i{T}_k^i)\end{array}$(A1) ). Constraint (A2(A2) $\begin{array}{rl}& \sum _{k=1}^{n_i}\sum _{i=1}^n{X}_{kijl}\le 1,j=1,2,\dots ,m,\\ & l=1,2,\dots ,N;\end{array}$(A2) ) ensures that each position of a machine cannot simultaneously process two or more jobs. Constraint (A3(A3) $\begin{array}{rl}& \sum _{j=1}^m\sum _{l=1}^N{X}_{kijl}=1,k=1,2,\dots ,n_i,\\ & i=1,2,\dots ,n;\end{array}$(A3) ) guarantees that each job $J_k^i$ is assigned to one of the positions on the machines. Constrains (A4(A4) $\begin{array}{rl}& S_{jl+1}-S_{jl}=\sum _{k=1}^{n_i}\sum _{i=1}^n{X}_{kijl}\ast p_k^i,\\ & j=1,2,\dots ,m,l=1,2,\dots ,N-1;\end{array}$(A4) ) and (A5(A5) $\begin{array}{rl}& S_{jl}\ge 0,j=1,2,\dots ,m,l=1,2,\dots ,N;\end{array}$(A5) ) define the start time of the job at each position on the machines. Constrains (A6(A6) $\begin{array}{rl}& \begin{array}{rl}{T}_k^i& \ge S_{jl}+X_{kijl}\ast p_k^i-(1-X_{kijl})M-d_k^i,\\ & k=1,2,\dots ,n_i,i=1,2,\dots ,n,\\ & j=1,2,\dots ,m,l=1,2,\dots ,N;\end{array}\end{array}$(A6) ) and (A7(A7) $\begin{array}{rl}& T_k^i\ge 0,k=1,2,\dots ,n_i,i=1,2,\dots ,n;\end{array}$(A7) ) specify the tardiness of $J_k^i$, where M is a large enough positive number.

Table A1. Detailed results obtained by different approaches for instances with m = 3.

$\alpha \times \gamma$	$0.6\times 0.4$		$0.6\times 0.6$		$0.6\times 0.8$		$0.8\times 0.4$		$0.8\times 0.6$		$0.8\times 0.8$		$1.0\times 0.4$		$1.0\times 0.6$		$1.0\times 0.8$		Average
$m\mathrm{\_}n\mathrm{\_}{n}_c$	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW
$MP3\mathrm{\_}6\mathrm{\_}5$	−1.35%	93.02%	0.92%	94.66%	0.32%	96.80%	1.24%	96.21%	1.23%	97.44%	1.65%	98.29%	−0.25%	96.88%	−1.32%	95.71%	1.62%	97.78%	0.45%	96.31%
$MP3\mathrm{\_}6\mathrm{\_}7$	−1.89%	93.64%	0.25%	94.80%	0.78%	96.34%	0.57%	95.66%	0.98%	97.20%	1.03%	96.71%	1.87%	97.74%	1.25%	97.01%	1.39%	97.00%	0.69%	96.23%
$MP3\mathrm{\_}6\mathrm{\_}10$	−2.32%	93.93%	1.53%	97.01%	0.65%	96.69%	0.65%	96.60%	−1.01%	94.35%	0.68%	96.27%	−1.15%	95.43%	1.46%	97.09%	0.97%	96.06%	0.16%	95.94%
$MP3\mathrm{\_}6\mathrm{\_}15$	−2.13%	91.19%	−1.90%	94.32%	−0.43%	95.22%	0.24%	94.36%	−0.64%	96.23%	−1.87%	96.10%	−1.34%	95.54%	1.33%	96.75%	1.12%	96.78%	−0.62%	95.17%
$MP3\mathrm{\_}9\mathrm{\_}5$	1.68%	94.39%	1.85%	95.69%	2.86%	96.33%	2.35%	96.48%	2.23%	96.88%	1.96%	96.28%	2.14%	95.42%	2.33%	96.21%	2.64%	96.40%	2.23%	96.01%
$MP3\mathrm{\_}9\mathrm{\_}7$	1.54%	93.79%	0.87%	95.16%	1.43%	94.43%	1.13%	94.04%	1.87%	95.74%	2.03%	95.55%	1.66%	95.76%	2.25%	96.05%	3.25%	97.99%	1.78%	95.39%
$MP3\mathrm{\_}9\mathrm{\_}10$	1.15%	93.22%	1.64%	95.14%	1.98%	94.61%	1.21%	95.57%	1.17%	94.58%	1.58%	95.85%	1.41%	95.22%	1.74%	96.19%	2.17%	96.30%	1.56%	95.19%
$MP3\mathrm{\_}9\mathrm{\_}15$	0.97%	92.44%	0.89%	94.38%	1.01%	95.02%	1.25%	94.47%	1.65%	94.95%	1.16%	96.48%	1.38%	94.05%	1.81%	94.89%	1.86%	95.46%	1.33%	94.68%
$MP3\mathrm{\_}12\mathrm{\_}5$	2.76%	93.31%	3.38%	96.08%	5.08%	96.96%	3.34%	94.47%	4.41%	96.37%	4.55%	96.23%	3.84%	94.20%	5.25%	96.34%	4.90%	96.24%	4.17%	95.58%
$MP3\mathrm{\_}12\mathrm{\_}7$	2.24%	92.69%	3.87%	94.02%	4.88%	94.19%	3.13%	95.08%	3.34%	94.44%	4.18%	95.73%	4.73%	95.47%	4.61%	96.83%	4.57%	95.80%	3.95%	94.92%
$MP3\mathrm{\_}12\mathrm{\_}10$	2.64%	92.83%	3.26%	94.82%	3.05%	94.81%	3.32%	94.90%	3.21%	95.06%	3.60%	95.03%	3.33%	93.92%	3.40%	94.70%	4.18%	94.09%	3.33%	94.46%
$MP3\mathrm{\_}12\mathrm{\_}15$	1.32%	91.63%	2.65%	96.67%	3.02%	94.13%	2.77%	94.76%	2.98%	95.25%	3.52%	95.10%	3.47%	94.20%	3.52%	94.09%	3.86%	94.86%	3.01%	94.52%
$MP3\mathrm{\_}15\mathrm{\_}5$	3.31%	93.06%	5.52%	95.28%	5.76%	95.89%	5.72%	94.28%	5.87%	94.53%	5.83%	94.53%	6.34%	94.55%	5.77%	94.79%	6.86%	96.65%	5.66%	94.84%
$MP3\mathrm{\_}15\mathrm{\_}7$	3.58%	93.74%	4.33%	94.94%	5.69%	96.16%	5.42%	93.91%	5.91%	95.26%	6.01%	95.94%	5.74%	94.73%	6.07%	95.45%	5.96%	95.86%	5.41%	95.11%
$MP3\mathrm{\_}15\mathrm{\_}10$	2.13%	90.56%	4.65%	94.44%	4.73%	94.92%	4.76%	94.67%	4.75%	94.65%	4.43%	94.79%	5.30%	93.37%	6.18%	95.32%	4.16%	93.92%	4.57%	94.07%
$MP3\mathrm{\_}15\mathrm{\_}15$	3.27%	91.82%	3.07%	93.22%	4.04%	93.98%	4.71%	95.34%	4.95%	94.62%	4.26%	93.96%	4.52%	93.59%	4.60%	93.36%	4.79%	94.65%	4.25%	93.84%
$MP3\mathrm{\_}18\mathrm{\_}5$	6.47%	92.17%	7.19%	93.96%	7.62%	94.83%	8.29%	94.83%	8.22%	94.46%	9.24%	95.58%	7.86%	93.61%	8.13%	94.36%	9.29%	95.33%	8.03%	94.35%
$MP3\mathrm{\_}18\mathrm{\_}7$	5.98%	92.08%	6.02%	94.80%	7.47%	94.82%	7.10%	93.14%	7.60%	94.82%	8.46%	95.37%	7.15%	94.40%	7.45%	93.58%	9.31%	95.16%	7.39%	94.24%
$MP3\mathrm{\_}18\mathrm{\_}10$	5.04%	91.44%	7.35%	94.96%	6.18%	95.14%	7.14%	94.48%	7.86%	93.25%	8.14%	93.12%	6.66%	93.06%	7.42%	94.56%	7.28%	94.09%	7.01%	93.79%
$MP3\mathrm{\_}18\mathrm{\_}15$	4.43%	90.24%	6.20%	92.24%	5.37%	93.21%	5.71%	93.98%	6.14%	93.42%	7.40%	93.58%	6.15%	92.20%	7.38%	93.85%	8.73%	95.83%	6.39%	93.17%

Table A2. Detailed results obtained by different approaches for instances with m = 5.

$\alpha \times \gamma$	$0.6\times 0.4$		$0.6\times 0.6$		$0.6\times 0.8$		$0.8\times 0.4$		$0.8\times 0.6$		$0.8\times 0.8$		$1.0\times 0.4$		$1.0\times 0.6$		$1.0\times 0.8$		Average
$m\mathrm{\_}n\mathrm{\_}{n}_c$	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW	RCG	RSW
$MP5\mathrm{\_}10\mathrm{\_}5$	1.98%	93.86%	2.21%	94.80%	2.87%	95.71%	2.18%	94.78%	3.97%	95.08%	4.44%	96.34%	4.43%	96.57%	5.20%	97.22%	4.45%	96.34%	3.53%	95.63%
$MP5\mathrm{\_}10\mathrm{\_}7$	1.79%	92.92%	2.03%	93.42%	3.23%	95.51%	2.45%	94.96%	2.81%	96.24%	2.13%	94.00%	4.60%	95.40%	4.51%	95.70%	4.88%	95.47%	3.16%	94.85%
$MP5\mathrm{\_}10\mathrm{\_}10$	1.13%	92.49%	3.16%	96.24%	3.06%	96.33%	3.76%	96.40%	2.71%	95.42%	3.00%	95.24%	3.54%	94.17%	4.27%	95.35%	4.24%	95.61%	3.21%	95.25%
$MP5\mathrm{\_}10\mathrm{\_}15$	1.38%	92.73%	2.65%	96.65%	2.19%	95.78%	2.15%	95.60%	2.42%	95.59%	2.77%	95.25%	3.10%	94.93%	3.32%	94.29%	3.97%	95.46%	2.66%	95.14%
$MP5\mathrm{\_}15\mathrm{\_}5$	3.08%	92.07%	4.98%	96.01%	5.72%	96.65%	4.59%	94.42%	5.34%	96.18%	6.17%	95.87%	7.11%	95.67%	7.23%	95.71%	8.36%	96.39%	5.84%	95.44%
$MP5\mathrm{\_}15\mathrm{\_}7$	3.29%	92.48%	4.46%	94.40%	5.18%	95.91%	5.21%	95.28%	5.17%	95.24%	6.12%	95.52%	6.42%	94.29%	6.55%	94.40%	6.16%	94.90%	5.40%	94.71%
$MP5\mathrm{\_}15\mathrm{\_}10$	3.51%	92.61%	4.07%	93.49%	4.36%	95.91%	4.39%	94.10%	5.94%	94.34%	5.30%	94.76%	4.87%	94.40%	5.03%	93.81%	7.62%	96.03%	5.01%	94.38%
$MP5\mathrm{\_}15\mathrm{\_}15$	3.10%	92.49%	4.19%	94.00%	4.27%	94.94%	3.85%	93.86%	4.52%	94.51%	4.75%	95.99%	4.60%	94.74%	6.11%	94.40%	5.83%	94.22%	4.58%	94.35%
$MP5\mathrm{\_}20\mathrm{\_}5$	10.02%	92.26%	13.13%	94.01%	14.51%	95.84%	14.91%	96.69%	15.33%	94.72%	14.45%	94.90%	12.92%	92.82%	15.40%	96.43%	15.21%	95.33%	13.99%	94.78%
$MP5\mathrm{\_}20\mathrm{\_}7$	9.72%	92.52%	13.35%	93.79%	13.06%	95.30%	14.15%	94.19%	14.72%	96.42%	16.50%	96.65%	15.71%	96.96%	15.18%	96.57%	14.77%	94.94%	14.13%	95.26%
$MP5\mathrm{\_}20\mathrm{\_}10$	9.37%	91.47%	13.93%	95.73%	14.74%	96.85%	15.03%	94.08%	14.39%	96.11%	15.07%	95.73%	14.44%	93.41%	14.06%	95.96%	14.33%	94.78%	13.93%	94.90%
$MP5\mathrm{\_}20\mathrm{\_}15$	9.61%	91.75%	12.47%	94.69%	12.16%	94.69%	13.27%	94.19%	13.75%	95.13%	14.20%	95.31%	13.23%	94.71%	12.86%	93.83%	13.13%	93.25%	12.74%	94.17%
$MP5\mathrm{\_}25\mathrm{\_}5$	18.34%	91.80%	22.48%	94.87%	22.91%	94.62%	23.18%	96.34%	22.74%	95.11%	23.33%	94.92%	22.08%	93.39%	23.81%	93.99%	24.43%	94.09%	22.59%	94.35%
$MP5\mathrm{\_}25\mathrm{\_}7$	17.91%	90.23%	21.07%	93.14%	23.32%	96.27%	22.83%	94.79%	21.94%	93.81%	23.08%	93.61%	25.22%	95.93%	24.30%	94.54%	22.95%	93.05%	22.51%	93.93%
$MP5\mathrm{\_}25\mathrm{\_}10$	19.29%	91.88%	21.64%	93.90%	21.84%	95.08%	21.47%	93.42%	23.10%	95.74%	24.16%	95.09%	23.64%	94.78%	23.38%	93.47%	22.14%	93.11%	22.30%	94.05%
$MP5\mathrm{\_}25\mathrm{\_}15$	18.52%	90.75%	21.71%	93.99%	21.39%	93.39%	22.66%	94.77%	22.25%	93.63%	22.86%	93.94%	22.15%	93.56%	21.29%	92.92%	22.64%	93.30%	21.72%	93.36%
$MP5\mathrm{\_}30\mathrm{\_}5$		90.54%		93.61%		94.13%		94.40%		94.20%		94.95%		93.36%		92.58%		93.66%		93.49%
$MP5\mathrm{\_}30\mathrm{\_}7$		90.08%		94.38%		93.81%		93.30%		94.45%		93.58%		93.73%		93.46%		93.93%		93.41%
$MP5\mathrm{\_}30\mathrm{\_}10$		90.21%		93.19%		93.60%		94.89%		94.60%		92.40%		92.58%		93.03%		92.09%		92.95%
$MP5\mathrm{\_}30\mathrm{\_}15$		91.04%		92.70%		92.81%		96.37%		93.80%		92.23%		94.01%		91.51%		92.84%		93.03%

Table A3. Detailed results obtained by different approaches for instances with m = 10.

$\alpha \times \gamma$	$0.6\times 0.4$	$0.6\times 0.6$	$0.6\times 0.8$	$0.8\times 0.4$	$0.8\times 0.6$	$0.8\times 0.8$	$1.0\times 0.4$	$1.0\times 0.6$	$1.0\times 0.8$	Average
$m\mathrm{\_}n\mathrm{\_}{n}_c$	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW
$MP10\mathrm{\_}20\mathrm{\_}5$	91.01%	98.03%	96.12%	96.02%	96.35%	97.37%	96.85%	95.62%	96.34%	95.97%
$MP10\mathrm{\_}20\mathrm{\_}7$	90.95%	97.20%	98.10%	97.04%	97.89%	96.16%	95.73%	94.58%	95.47%	95.90%
$MP10\mathrm{\_}20\mathrm{\_}10$	91.09%	96.66%	96.86%	95.41%	95.09%	94.35%	94.40%	96.82%	95.61%	95.14%
$MP10\mathrm{\_}20\mathrm{\_}15$	90.35%	97.38%	97.16%	96.00%	96.50%	96.57%	94.47%	95.16%	94.71%	95.37%
$MP10\mathrm{\_}30\mathrm{\_}5$	90.06%	94.31%	95.64%	95.83%	94.68%	95.98%	96.06%	94.12%	96.39%	94.79%
$MP10\mathrm{\_}30\mathrm{\_}7$	90.86%	97.33%	95.74%	94.44%	96.39%	94.16%	96.19%	95.13%	93.90%	94.90%
$MP10\mathrm{\_}30\mathrm{\_}10$	91.43%	92.85%	93.33%	94.11%	94.36%	95.45%	95.46%	96.51%	94.13%	94.18%
$MP10\mathrm{\_}30\mathrm{\_}15$	89.61%	94.72%	94.95%	95.46%	95.18%	94.07%	93.80%	94.56%	94.22%	94.06%
$MP10\mathrm{\_}40\mathrm{\_}5$	90.53%	91.47%	95.96%	93.21%	95.34%	93.56%	95.38%	94.59%	95.33%	93.93%
$MP10\mathrm{\_}40\mathrm{\_}7$	90.38%	92.11%	94.83%	94.65%	94.94%	94.46%	93.45%	95.74%	94.94%	93.94%
$MP10\mathrm{\_}40\mathrm{\_}10$	89.82%	92.03%	95.56%	92.16%	93.00%	93.79%	95.04%	95.01%	93.88%	93.37%
$MP10\mathrm{\_}40\mathrm{\_}15$	89.08%	91.76%	94.00%	94.12%	92.84%	93.80%	93.54%	93.29%	93.25%	92.85%
$MP10\mathrm{\_}50\mathrm{\_}5$	89.55%	93.32%	94.96%	92.50%	93.29%	92.18%	93.68%	93.52%	94.09%	93.01%
$MP10\mathrm{\_}50\mathrm{\_}7$	90.36%	92.22%	93.07%	94.81%	92.72%	93.01%	93.50%	93.92%	93.05%	92.96%
$MP10\mathrm{\_}50\mathrm{\_}10$	88.33%	92.48%	93.48%	92.59%	92.63%	93.63%	93.64%	92.98%	92.24%	92.44%
$MP10\mathrm{\_}50\mathrm{\_}15$	88.91%	93.57%	92.05%	91.13%	93.19%	92.70%	92.73%	93.20%	93.30%	92.31%
$MP10\mathrm{\_}60\mathrm{\_}5$	89.38%	93.70%	94.37%	94.73%	93.77%	92.44%	93.15%	92.06%	93.66%	93.03%
$MP10\mathrm{\_}60\mathrm{\_}7$	88.53%	91.27%	93.89%	92.63%	94.95%	92.09%	92.63%	92.34%	91.93%	92.25%
$MP10\mathrm{\_}60\mathrm{\_}10$	88.61%	89.88%	92.16%	93.21%	92.10%	91.87%	91.12%	90.25%	92.26%	91.27%
$MP10\mathrm{\_}60\mathrm{\_}15$	87.26%	88.72%	91.18%	92.65%	92.90%	90.51%	91.95%	91.93%	92.84%	91.10%

Table A4. Detailed results obtained by different approaches for instances with m = 15.

$\alpha \times \gamma$	$0.6\times 0.4$	$0.6\times 0.6$	$0.6\times 0.8$	$0.8\times 0.4$	$0.8\times 0.6$	$0.8\times 0.8$	$1.0\times 0.4$	$1.0\times 0.6$	$1.0\times 0.8$	Average
$m\mathrm{\_}n\mathrm{\_}{n}_c$	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW
$MP15\mathrm{\_}30\mathrm{\_}5$	90.42%	96.48%	95.80%	96.98%	96.17%	96.44%	96.09%	96.87%	96.67%	95.77%
$MP15\mathrm{\_}30\mathrm{\_}7$	90.60%	94.76%	96.69%	94.60%	95.11%	96.33%	93.26%	95.72%	95.64%	94.75%
$MP15\mathrm{\_}30\mathrm{\_}10$	89.79%	93.32%	96.36%	96.10%	96.42%	95.18%	95.51%	94.31%	95.47%	94.72%
$MP15\mathrm{\_}30\mathrm{\_}15$	88.47%	93.74%	95.13%	95.51%	95.21%	95.49%	94.54%	94.38%	94.87%	94.15%
$MP15\mathrm{\_}45\mathrm{\_}5$	89.19%	92.14%	95.50%	92.03%	96.23%	95.56%	95.50%	94.13%	94.25%	93.84%
$MP15\mathrm{\_}45\mathrm{\_}7$	88.05%	91.11%	95.30%	93.81%	94.89%	95.90%	94.06%	93.41%	95.32%	93.54%
$MP15\mathrm{\_}45\mathrm{\_}10$	89.44%	91.72%	96.07%	95.63%	93.39%	96.40%	95.34%	94.63%	94.64%	94.14%
$MP15\mathrm{\_}45\mathrm{\_}15$	87.50%	93.65%	94.64%	92.60%	93.83%	93.72%	93.92%	93.86%	94.16%	93.10%
$MP15\mathrm{\_}60\mathrm{\_}5$	89.50%	90.51%	94.85%	93.38%	93.20%	94.58%	94.26%	93.22%	95.81%	93.26%
$MP15\mathrm{\_}60\mathrm{\_}7$	89.59%	90.61%	93.04%	92.69%	94.35%	92.80%	93.64%	94.91%	93.18%	92.76%
$MP15\mathrm{\_}60\mathrm{\_}10$	88.60%	89.54%	94.58%	91.13%	94.17%	93.19%	92.09%	93.98%	93.55%	92.31%
$MP15\mathrm{\_}60\mathrm{\_}15$	87.54%	88.52%	92.37%	91.87%	94.30%	91.29%	92.10%	94.64%	93.54%	91.80%
$MP15\mathrm{\_}75\mathrm{\_}5$	88.44%	90.95%	91.96%	91.99%	91.80%	93.60%	91.03%	92.27%	92.99%	91.67%
$MP15\mathrm{\_}75\mathrm{\_}7$	87.40%	87.28%	91.41%	90.64%	92.84%	90.82%	93.62%	92.30%	92.22%	90.95%
$MP15\mathrm{\_}75\mathrm{\_}10$	88.60%	89.42%	93.19%	91.68%	91.66%	93.58%	92.84%	92.82%	91.52%	91.70%
$MP15\mathrm{\_}75\mathrm{\_}15$	87.21%	89.62%	92.43%	92.30%	93.00%	91.41%	91.29%	92.02%	91.30%	91.18%
$MP15\mathrm{\_}90\mathrm{\_}5$	86.90%	87.30%	91.65%	91.51%	91.72%	90.32%	90.35%	91.63%	92.39%	90.42%
$MP15\mathrm{\_}90\mathrm{\_}7$	84.96%	86.45%	92.98%	91.70%	89.88%	92.93%	92.53%	88.88%	91.27%	90.18%
$MP15\mathrm{\_}90\mathrm{\_}10$	84.37%	87.42%	91.33%	90.47%	90.01%	90.60%	90.09%	91.16%	90.81%	89.58%
$MP15\mathrm{\_}90\mathrm{\_}15$	82.28%	84.64%	90.39%	91.23%	89.63%	91.07%	91.44%	90.94%	91.64%	89.25%

Table A5. Detailed results obtained by different approaches for instances with m = 20.

$\alpha \times \gamma$	$0.6\times 0.4$	$0.6\times 0.6$	$0.6\times 0.8$	$0.8\times 0.4$	$0.8\times 0.6$	$0.8\times 0.8$	$1.0\times 0.4$	$1.0\times 0.6$	$1.0\times 0.8$	Average
$m\mathrm{\_}n\mathrm{\_}{n}_c$	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW	RSW
$MP20\mathrm{\_}40\mathrm{\_}5$	89.32%	91.77%	92.35%	92.75%	91.48%	93.23%	92.93%	93.67%	93.90%	92.38%
$MP20\mathrm{\_}40\mathrm{\_}7$	90.01%	90.33%	93.25%	92.89%	92.14%	93.51%	92.64%	91.70%	91.42%	91.99%
$MP20\mathrm{\_}40\mathrm{\_}10$	88.19%	90.83%	92.10%	90.55%	90.37%	92.64%	91.36%	90.92%	91.28%	90.92%
$MP20\mathrm{\_}40\mathrm{\_}15$	88.45%	89.69%	90.18%	90.98%	91.35%	92.22%	92.91%	91.09%	86.14%	90.33%
$MP20\mathrm{\_}60\mathrm{\_}5$	87.34%	88.79%	92.03%	89.41%	90.19%	90.13%	91.50%	90.09%	89.59%	89.90%
$MP20\mathrm{\_}60\mathrm{\_}7$	86.87%	88.14%	91.87%	90.18%	90.25%	90.33%	91.17%	89.13%	90.79%	89.86%
$MP20\mathrm{\_}60\mathrm{\_}10$	86.08%	89.01%	90.64%	90.49%	89.71%	87.75%	90.66%	91.04%	90.72%	89.57%
$MP20\mathrm{\_}60\mathrm{\_}15$	86.12%	88.36%	89.39%	88.82%	89.64%	89.31%	90.21%	91.68%	88.42%	89.11%
$MP20\mathrm{\_}80\mathrm{\_}5$	83.28%	85.29%	91.15%	87.99%	89.80%	89.88%	88.61%	90.67%	88.04%	88.30%
$MP20\mathrm{\_}80\mathrm{\_}7$	82.14%	86.86%	88.42%	88.72%	87.98%	86.28%	87.56%	88.18%	87.65%	87.09%
$MP20\mathrm{\_}80\mathrm{\_}10$	83.64%	83.54%	88.79%	88.48%	85.07%	86.07%	86.23%	87.29%	88.01%	86.35%
$MP20\mathrm{\_}80\mathrm{\_}15$	82.56%	82.07%	86.60%	87.76%	84.18%	85.46%	87.67%	88.55%	96.21%	86.78%
$MP20\mathrm{\_}100\mathrm{\_}5$	78.71%	80.78%	83.19%	84.43%	82.59%	84.10%	83.06%	83.44%	84.69%	82.78%
$MP20\mathrm{\_}100\mathrm{\_}7$	78.36%	82.01%	83.40%	82.18%	83.76%	81.88%	82.42%	83.04%	83.44%	82.28%
$MP20\mathrm{\_}100\mathrm{\_}10$	80.53%	81.34%	82.64%	79.52%	83.46%	83.16%	81.81%	83.05%	82.48%	82.00%
$MP20\mathrm{\_}100\mathrm{\_}15$	77.10%	78.71%	83.16%	81.98%	82.19%	82.22%	80.45%	82.41%	93.93%	82.46%
$MP20\mathrm{\_}120\mathrm{\_}5$	72.01%	77.13%	80.84%	78.62%	77.03%	80.35%	79.27%	79.68%	80.27%	78.36%
$MP20\mathrm{\_}120\mathrm{\_}7$	70.83%	79.85%	78.03%	76.93%	78.27%	76.60%	79.65%	76.89%	77.97%	77.22%
$MP20\mathrm{\_}120\mathrm{\_}10$	71.68%	76.86%	76.19%	76.97%	77.24%	77.44%	76.55%	77.35%	79.55%	76.65%
$MP20\mathrm{\_}120\mathrm{\_}15$	69.04%	75.17%	76.38%	75.53%	76.73%	76.34%	76.50%	77.16%	74.53%	75.26%