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.
Yaqiong Liu, Shudong Sun, Gaopan Shen, Xi Vincent Wang, Magnus Wiktorsson, Lihui Wang.
An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival.
Engineering, 2024, 35 (4) : 32-45 DOI:10.1016/j.eng.2023.09.024
Scheduling plays a significant role in manufacturing systems [1], [2] and changes as production models constantly evolve. In the mass production model, traditional scheduling studies are mostly aimed at increasing the machine utilization of manufacturers or reducing their manufacturing costs [3]. However, under the current customer-driven production model, manufacturers must accommodate the unique demands of various individual consumers. This has shifted the goal of scheduling toward the efficient allocation of machine resources and meeting diverse requirements, resulting in a complex multi-agent scheduling problem that has become a research mainstream [4]. The multi-agent scheduling problem refers to how jobs belonging to different consumers can be scheduled on the given machine resources [5], where parallel machines are common and vital in machine environments [6]. The multi-agent parallel machines scheduling problem has gained a certain level of research interest [7], [8], [9]. It pervades a wide range of real-world situations, such as intuitive scenarios in which jobs are arranged on machines in manufacturing [10]; allocating multiple virtual machine resources to many users in a cloud computing system [11]; several electric vehicles sharing charging stations in a power system [12]; scheduling surgery in multiple operating theatres [13]; and arranging aircraft landings on a given set of runways [14]. Furthermore, most of the above scheduling environments are uncertain and dynamic—characteristics that are commonly manifested by the fact that the jobs, electric vehicles, or surgeries do not arrive or occur all at once but do so dynamically over time. Within this context, this paper focuses on the multi-agent uniform parallel machines scheduling problem with dynamic jobs arrival (MUPMSP-D), in which the uniform parallel machines are heterogeneous machines with different processing speeds.
In a multi-agent scheduling model, the allocation of machine resources involves different agents, each of which has its own jobs to be processed and individual objectives. As a result of the limited machine resources, the competition for resources among agents is exceptionally fierce. Centralized scheduling methods are a traditional means of solving such problems, mainly by constructing multi-objective optimization models and generating Pareto solution sets [15]. However, selecting a solution that is acceptable to all consumers from the Pareto solution set is a complex and challenging task. In addition, since the agents have their own objectives and preferences, strategic and economic rationality should be considered when making decisions [16]. The self-interested and rational agents may not be willing to disclose their private information because a complete revelation increases the possibility of being scheduled undesirable resources [17]. These characteristics lead to the infeasibility of the centralized scheduling approach in which decisions are made by a central authority that requires complete information. Compared with the centralized approach, the decentralized decision-making approach addresses resource-allocation issues by utilizing autonomous agents that make decisions collectively, without relying on a fully informed central authority [18], [19]. Therefore, a decentralized approach becomes crucial in solving a multi-agent scheduling problem in which asymmetric information exists. The involvement of agents in decision-making processes with private information can lead to more consensus-driven and high-quality scheduling outcomes. Moreover, the decentralized approach is more scalable and fault tolerant when addressing dynamic scheduling challenges [20]. In summary, for the targeted MUPMSP-D, a decentralized group decision-making process that accounts for the strategic behavior of self-interested agents and the limited availability of information is required.
Because the individual requirements of self-interested agents in the multi-agent problem are considered, the objective of scheduling is redefined. Rather than finding “optimal” solutions, the goal of the decentralized scheduling approach is to generate a stable and acceptable resource-allocation plan that reflects the goals of all agents, while keeping social welfare at the forefront. Social welfare is used to evaluate the multi-agent system, considering the objective of each agent [21]. To achieve this purpose, market-based mechanisms are popularly implemented in decentralized architecture when solving scheduling problems. More specifically, agents learn and imitate the behavior of customers competing for resources in the marketplace from economic theories when engaging in decision-making, with auction theory being particularly widespread. The auction theory can be applied to generate better solutions in various situations because of its natural autonomy and distribution [22], [23], [24]. Up to this point, only Liu et al. [7] has used auction theory to address multi-agent parallel machines scheduling problems, proposing an iterative combination auction-based approach for achieving good social welfare solutions. However, their work considered a relatively simple scenario in which all jobs arrive statically and are processed on identical parallel machines. This approach is inapplicable to the target problem of dynamic jobs being processed on uniform parallel machines. Therefore, it is necessary to develop an auction-based decentralized approach to tackle the targeted challenge. Furthermore, in terms of the auction-based approach, bid determination and winner determination are the main ways in which agents participate in the decision-making and are the two key stages that affect the performance of the overall method. Price is often adopted to allow agents to express their preferences and communicate with the resource owner, resulting in an agreement during bid determination [25], [26], [27], [28]. However, due to the increasing number of jobs and the heterogeneous machines in the targeted MUPMSP-D, price guidance leads to an exponential increase in the calculated costs of bid determination and winner determination. Hence, a non-price-guided bidding strategy and a corresponding efficient winner determination algorithm need to be developed for the auction-based approach.
This research studies the multi-agent scheduling problem with dynamic jobs arrival, incorporating multiple self-interested consumer agents and a resource agent with uniform parallel machines. Taking the challenges described above into account, a dynamic iterative auction (DIA)-based approach is developed to generate a collaborative solution with high social welfare while simultaneously accommodating the consumer agents’ preferences. The main contributions of this study are summarized as follows:
(1) A dynamic iterative auction-based approach is applied to solve the MUPMSP-D for the first time, where jobs can participate in the auction once they arrive, enabling real-time scheduling for dynamic jobs. The proposed approach’s individual rationality property is theoretically proven, and its effectiveness is validated through extensive computational experiments.
(2) A straightforward and easy-to-implement bidding strategy without price guidance is developed in the proposed DIA approach. Consumer agents submit only target machines without bidding prices, which significantly reduces the computational costs for auctions that involve continuously increasing job participation. The theoretical proof confirms that the myopic bidding strategy is a weakly dominant strategy for consumer agents to submit bids.
(3) A mixed termination condition with an adaptive Hungarian algorithm is developed to address the winner determination problem (WDP). Despite the increasing number of bids and the growing scale of the WDP, full competition between consumer agents is ensured, and high-quality solutions are generated efficiently.
The remainder of this paper is structured as follows: Section 2 is devoted to introducing the related work. In Section 3, the targeted MUPMSP-D is described, and a corresponding centralized model is constructed. The details of the proposed dynamic iteration auction-based approach are given in Section 4. Computational experiments and results are shown in Section 5. Finally, conclusions and future work are highlighted in Section 6.
2. Related Work
Since auction theory was first introduced into a distributed decision structure for job shop scheduling by Kutanoglu and Wu [29], research on the use of auction methods for solving distributed scheduling problems has flourished. Hall and Liu [25] presented an effective ascending auction by dividing single machine resources into flexible time blocks and designing adaptive ask pricing strategies, promoting the application of auction methods in machine scheduling. Afterward, flexible job shop scheduling problems solved by auction-based approaches were studied by Tang et al. [23] and Zeng et al. [30] under different constraints. Zhu and Wang [24] designed an auction mechanism to allocate the production capacity to two parallel machines. However, the problems addressed in these works are basic with relatively simple machine environments; moreover, each bidder only bids on one job, limiting the scalability of the approaches. Then, a more practical and complex job shop problem with parallel batch processing was considered by Zeng et al. [31]. An improved disjunctive graph model was applied to the auction, with flexible jobs acting as auctioneers or bidders, resulting in good outcomes in large-scale instances. This method is universal and cannot be scaled up for parallel machines scheduling. Although Kong et al. [32] designed an auction mechanism for resource scheduling on virtual parallel machines in cloud computing, the flexible divisibility of virtual resources in auctions is not applicable to the problem considered in the present study. Liu et al. [7] studied an iterative auction-based approach for multi-agent parallel machines scheduling problems in which a multi-stage auction framework is proposed, ensuring bidders bid for multiple jobs and significantly extending the scale of the problem to be solved. However, the researchers focus on identical machines and assume that all jobs arrive statically. To the best of our knowledge, no researchers have addressed widespread multi-agent uniform parallel machines scheduling with dynamic jobs arrival. This work studies the considered problem and proposes an auction-based approach for achieving well-performing solutions, which can be extended to an unrelated parallel machines environment.
The application of auctions in dynamic scheduling has drawn considerable attention. Dewan and Joshi [33], [34] first studied auction-based distributed scheduling in a dynamic job shop environment. They established the foundations for the application of auction to dynamic scheduling, but only three jobs belonging to one agent were considered, and they participated in the auction at the same time. A more complex dynamic environment was considered and a corresponding auction-based approach was constructed in Ref. [35], but an auction only started when machines were available, delaying the decision process. The auction mechanism has been broadened for other scheduling fields. For example, Araúzo et al. [36] and Tosselli et al. [37] employed an auction for project portfolios scheduling and multi-project scheduling, respectively. The tasks in project scheduling can often be split into subtasks; however, the jobs in our considered MUPMSP-D scenario are indivisible. Kong et al. [32] worked on virtual machine resource scheduling based on an auction, and Vishalatchi et al. [38] combined a tabu search with an auction mechanism in cloud computing. Mukherjee et al. [39] solved the scheduling problem in the power market by using a market clearing auction with dynamic production offers. These problems all highlight dynamic resources instead of tasks. To summarize, the methods used in the aforementioned literature cannot be implemented in situations in which multiple consumers have multiple and indivisible jobs. In this paper, we develop a dynamic auction procedure, which ensures that jobs participate in the auction as soon as they arrive, thereby reducing the waiting time for jobs to be scheduled.
In a scheduling environment with information asymmetry, a bidding strategy that speaks to the bidders’ individual preferences but withholds private information plays a crucial role in improving the performance of the auction-based approach. Typically, pricing is most frequently used when bidding. Wellman et al. [40] were the first to bring a reserve price into scheduling, with bidders expressing their preferences by raising the prices. These researchers also investigated the existence of equilibrium prices for some general scheduling problems. Inspired by this principle, Hall and Liu [25] designed a flexible adaptive pricing strategy and flexible time blocks, through which bidders can bid for their target time resources. This work was later extended in Refs. [7], [24], [41]. Pricing based on the Lagrange multiplier is another effective way that has been widely adopted [42], [43], [44]. These bidding methods can visually represent the bidders’ preferences, and sealed bids protect privacy. However, bidders have to calculate their prices on all potential target resources for each job or task. As a result, there will be an exponential increase in the bidders’ calculation costs when using the pricing strategy in our problem, because of three strong constraints: multiple bidders, multiple heterogeneous machines, and an increasing number of jobs. Some studies have proposed bidding mechanisms without pricing in the auction. Wang et al. [45] presented a non-price bidding strategy in which bidders submitted their preferred time intervals. Liu et al. [46] proposed another non-price bidding mechanism by assigning a value to each time bundle in surgical scheduling. Without pricing, Merz et al. [47] selected the machine with the maximum processing time in the scheduling of human-machine teams. It should be noted that the resources considered in these problems are single-attribute resources with time or processing speed, precluding the use of these non-price bidding strategies in a multi-attribute machine environment. Hence, a bidding strategy without price that works for the considered MUPMSP-D should be developed. In this work, a straightforward and flexible bidding strategy without price guidance is developed, in which bidders submit one or more target machines based on their objectives. This approach greatly reduces the computational cost of the agents while protecting their privacy.
3. Problem description
In this section, the considered MUPMSP-D is described. Then, a corresponding centralized model with complete information is built, whose solutions will be benchmarks for comparison in Section 5.
3.1. MUPMSP-D description
The problem can be described as follows. There are N self-interested consumer agents , and each has dynamic arrival jobs that need to be processed on m uniform parallel machines belonging to a resource agent, denoted as RA. The total number of jobs is . Each job is characterized by a tuple of four elements, , representing a processing requirement, a due date, a revenue loss resulting from unit-time tardiness, and a revenue that CAi can receive when is processed, respectively.
In this study, three machine states corresponding to three costs are considered based on Ref. [48]. These are defined as the setup state, processing state, and idle state, as illustrated by an example in Fig. 1. When a machine starts processing a job, a machine-dependent setup time is needed [49]. A machine working on the job is then in the processing state. Due to the dynamic arrival of jobs, a machine enters into an idle state if the current job has been completed and no new jobs have arrived. The idle time refers to the period during which a machine waits for a new job. In this case, the machine still consumes energy and incurs costs [50]. These three machine states correspond to three costs. Thus, each machine has six relevant characteristics: ➀ a processing speed , which determines the actual processing times of jobs; ➁ a setup time , which is sequence-independent and machine-dependent [51]; ➂ a unit operating cost , which calculates the costs incurred when a machine is in the operating state; ➃ a unit setupcost , referring to the costs incurred when a machine is in the setup state; ➄ a unit idle cost , corresponding to the costs incurred when a machine is idle; and ➅ a unit profit , which determines the unit profit a machine gains from processing a job.
All agents are self-interested. The consumer agent CAi wants to process its jobs with the objective of maximizing its revenue:, where denotes the completion time of and represents the total revenue loss of job caused by its tardiness. The resource agent aims to maximize its profit by allocating the machine resources—that is, to maximize the total profit generated from processing jobs minus the total costs. The total costs consist of three components: machine operating costs, setup costs, and idle costs.
A schedule is a mapping , indicating the start time and assigned machine for the job . The schedule is generated based on the following constraints and assumptions:
(1) All machines are available at the beginning of the planning horizon and have no breakdowns.
(2) Each job can be processed on any machine but it can only be processed on one machine at a time.
(3) Each job can only be processed once it has arrived and cannot be interrupted once it is being processed.
(4) The revenue loss of job resulting from its tardiness cannot exceed its revenue .
(5) The machine processing speed and the setup time are public information—that is, all parties are aware of them—while the three types of costs are just known to the resource agent.
(6) The processing load of job is semi-public information known to the job owner and the resource agent RA, whereas the other four parameters of the job hold private information only known to .
Since the introduced scheduling problem is solved by means of a decentralized decision-making approach, without losing generality, social welfare is applied to evaluate the system value of a schedule F [52]. Here, social welfare refers to the sum of the total revenue of N consumer agents and the profit of the resource agent, given by .
3.2. Centralized model
In this section, all the agents’ information is assumed to be public. A solution generated in a centralized model is used as a benchmark to evaluate the performance of the proposed decentralized auction-based approach. A central authority determines the schedule by solving the integer programming formulation as follows:
s.t.
The proposed model is based on Refs. [53], [48]. The objective function of Eq. (1) consists of two parts: the total revenue of the consumer agents and the profit of the resource agent. Eq. (2) constraint implies that each position on any machine can process a maximum of one job. Constraint (3) ensures that job can only be processed by one machine. Constraints (4) and (5) compute the starting time of job at each position on a machine, and constraint (5) ensures the job is processed after it arrives. Constraint (6) quantifies the completion time of job at each position on the machine. Constraints (7) and (8) specify the tardiness of job , where M is a sufficiently large positive number. Furthermore, constraint (9) ensures that the revenue loss of a job cannot exceed its revenue. Constraint (10) calculates the idle time of the tth position on machine .
4. Research methodology: The proposed approach
In this section, an auction-based framework is proposed to deal with the considered MUPMSP-D. The resource agent and consumer agents act as an auctioneer and bidders, respectively. The auctioneer regards the machine resource as auction goods, and the bidders bid for their target machine resources. Owing to the intense competition for limited machine resources between multiple self-interested consumer agents and the dynamic arrival of jobs, the framework has been developed as a dynamic iterative auction procedure. Four major components are contained in this framework: a dynamic iterative auction procedure, a bid determination model for the bidders, a winner determination model for the auctioneer, and bid update strategies for bidders. These are elaborated in the following sections.
4.1. The dynamic iterative auction procedure
In this section, a dynamic iterative auction procedure is presented that enables the consumer agents and the resource agent to generate a consensus scheduling plan. It is depicted as a flowchart in Fig. 2. Any disclosure of private information—other than the defined public and semi-public information—is forbidden.
Upon the arrival of any job from any bidder, the bidders post their processing requirements to the auctioneer; then, the auction starts. The auctioneer confirms the available machine resources and provides information about them to bidders for bidding. After receiving the auction information, the bidders conduct bid determination for the arrived jobs and send bids to the auctioneer. These bids are consolidated into a pool of bids, which serves as the input to the winner determination model solved by the auctioneer. If the termination conditions (described in Section 4.3) are satisfied, a schedule for the arrived jobs is generated. Otherwise, the available machine resources are updated based on provisional solutions obtained from the winner determination model. As auction items are renewed, bidders update their bids for the submitted jobs and perform bid determination for the newly arrived jobs. Bidders choose to leave the auction when no new jobs arrive. This ensures that jobs enter the auction as soon as they arrive, which means that a real-time scheduling approach for the dynamic scheduling problem is achieved. It is notable that the increasing number of jobs in each auction round also poses a challenge to the WDP. The DIA procedure facilitates dynamic and effective interactions between the consumer agents and the resource agent, allowing them to negotiate a consensus scheduling solution. Furthermore, it reduces the information revelation of buyers and sellers and provides the ability to accommodate dynamic changes in the auction process.
4.2. Bid determination model
In this section, a bid determination model is constructed based on which consumer agents generate their bids. In general, in auctions, price is typically used by auctioneers and bidders in their bids to express individual preferences [54]. However, in our study, the auctioneer sells multiple uniform parallel machines resources, and each bidder would bid for multiple jobs in a round of auction. Using the bidding price to express bidders’ preferences for different machines would introduce two challenges. First, the auctioneer must set numerous asking prices for each timeslot of each machine. Second, each bidder must calculate an exponential amount of the bidding price. These complex calculations do not result in a better solution but make the whole auction system inefficient. Moreover, in a practical manufacturing environment, both consumers and manufacturers prefer simple decision-making methods. Therefore, a novel and straightforward non-price bidding strategy is developed, and the bid determination model is built accordingly.
At the beginning of the auction, the auctioneer just informs the bidders of the available start time for each machine. Accordingly, the bidders express their preferences by submitting requirement-based bids, which can be represented as a 2-tuple , where identifies the bidding job and specifies the target machine. For the bidders, only submitting the target machine without a bidding price reduces the computational costs and allows individual requirements to be represented directly and effectively. Moreover, this approach does not require rational and self-interested consumer agents to reveal any information about their profits, thereby preserving their privacy. Another notation, , is defined that indicates the number of times bidder has bid for job . This is used to sort the multiple jobs that a bidder simultaneously bids for in a single auction; that is, the greater is, the higher the calculated priority of job will be. Although the calculation order does not affect the scheduling solutions, a reasonable rule facilitates the smooth implementation of the proposed approach. Finally, the straightforward way of generating bids without machine features makes it workable in the unrelated parallel machine environment.
Since each bidder has no information about other bidders and is motivated by self-interest, it is a natural choice for the bidders to bid with a myopic bidding strategy [25], which was proven to be a weakly dominant strategy for consumer agents in Section 4.5. Thus, each bidder will choose the machine with the highest profit as the target machine for the in each round of the auction. It should be noted that only machines with positive profits are likely to be chosen, since no consumer agent is willing to process jobs with negative returns. If a job gets the same non-negative revenue on multiple machines, then all the machines are selected. This improves the bidders’ odds of winning and makes it easier for the auctioneer to allocate machine resources. On the other hand, if a job does not yield on any machine, it will be withdrawn from the auction. Accordingly, the bid is an atomic bid. If a bidder chooses multiple machines, its bid is represented as , which represents multiple bids , , and connected by the logical connector XOR [55]. For example, indicates that the bidder is willing to process job on machine or machine . After receiving the available start time of each machine from the auctioneer, the bidders can generate bids through Algorithm 1.
Let U be the max(), representing the maximum number of jobs owned by different consumer agents. The time complexity of Algorithm 1 is O(NUm), where N is the number of consumer agents and m is the number of machines.
4.3. Winner determination model
After receiving bids from the bidders, the auctioneer works on the WDP. The WDP involves maximizing the auctioneer’s profit by choosing an allocation of machine resources from the given bids and generating a consensus production plan or schedule. In the iterative auction procedure, the auctioneer must solve the WDP and generate a provisional plan in each auction round until the auction termination condition is satisfied. Usually, at the end of each round, the bidders who temporarily win their bids are classified as provisional winners. Conversely, the bidders who do not win their bids are referred to as losing bidders [56]. However, in the targeted problem, the bidders bid for multiple jobs simultaneously in a round of the auction. Furthermore, it is inaccurate and confusing to categorize them based on whether a job is won or not. As a result, the unique jobs are defined as provisional winning jobs grouping a set PWJ and provisional losing jobs grouping a set PLJ. When the termination condition is met, the provisional winning jobs become the final winning jobs grouping a set FWJ and obtaining the target machine resource.
In general, iterative combination auctions terminate in two situations: When no resource-allocation conflict exists among bidders—that is, their requirements are met—or when the auctions reach a preset round [57]. In our study, the dynamic arrival of jobs results in an increasing number of jobs participating in the auction. If a fixed auction round is set, some late-arriving jobs may not be able to compete adequately. Therefore, the termination condition that all jobs’ requirements are met is adopted when solving the WDP. Keeping jobs in the auction to express individual needs until they are met may increase the duration of the auction, but it will eliminate the negative effects of late arrivals. Consequently, the first termination condition will be used as the basis for determining when the auction ends. Furthermore, a supplement in which the jobs that become the provisional winning jobs three times in a row are regarded as the final winning jobs—analogous to the lot knocking down after three calls in many real-world auctions—is embedded with the termination condition. Such a design can reduce repeated bids and make iterative auctions more efficient.
The WDP in the proposed DIA approach is modeled as follows. Given a set of bids, where the number of bids dynamically changes with the dynamic arrival of jobs and updated bids, the auctioneer computes a provisional schedule aiming at maximizing its profit. Since the 2-tuple bid or does not include any price, the WDP can be transformed into an assignment problem, in which jobs need to be assigned to machines under the constraints given in Section 3.1. A combinatorial optimization algorithm named the Hungarian algorithm is commonly used to solve the assignment problem in a polynomial time of [58]. Based on this and dynamic bidding, an adaptive Hungarian algorithm is developed to solve the WDP with the following pseudo-code, as shown in Algorithm 2.
Let be the number of bids received in the rth round of auction, and let be the number of jobs in set PWJ, where Algorithm 2 is composed of three main parts: ① Generate the revenue matrix with a time complexity of ; ② obtain the optimal solution using the adaptive Hungarian algorithm with a time complexity of , where J is the total number of jobs; and ③ update the available start time of the machines according to , whose time complexity is . Therefore, the overall time complexity of Algorithm 2 is .
4.4. Bid update strategies
In the iterative bidding procedure, each bidder should update bids for its jobs in each auction round before obtaining the desired machine resource or withdrawing from the auction. After the WDP is solved by the auctioneer in round r(r≥1), the bidders are informed whether their jobs are provisional winning jobs, provisional losing jobs, or final winning jobs. To increase the probability of a job winning when bidders do the bid determination in round (r + 1), the rational bidders adopt different bidding strategies for jobs in different sets.
Provisional winning jobs are expected to keep winning in round (r + 1). Since the myopic strategy is a weakly dominant strategy and the machine resources for the auction remain unchanged, the bids submitted at round r still maximize the revenue of bidders; then, the same bids are submitted in round r + 1. For the provisional losing jobs, bidders are more desperate to win, and the myopic strategy encourages them to submit more bids, providing more options to auctioneers. Specifically, both bids with the largest revenue submitted in round r and additional bids with the second largest revenue are submitted in round (r + 1). In addition, if these jobs still lose in round (r + 1), bids with the third revenue will be stacked with the bids in round (r + 1) and submitted in round (r + 2). This increase will continue until the jobs win or all valid bids are added. Final winning jobs have obtained the required machine resources and therefore withdraw from the auction. The bid update strategy is summarized in Algorithm 3.
4.5. Properties of the proposed approach
For an auction-based approach, the properties theoretically reflect the reasonableness of the approach. In this section, two critical properties of the proposed DIA framework are described and proven [46]: The proposed framework is individually rational, and the myopic bidding strategy is a weakly dominant strategy for consumer agents to submit bids.
Property 1: The proposed DIA framework is individually rational.
Proof: An auction framework is individually rational if the bidders can always achieve as much utility from participation as from no participation, regardless of other bidders’ behaviors. Alternatively, when the expected utility yield from participation is non-negative, individual rationality holds.
In our problem, each consumer agent generates bids only with non-negative revenue for its job . When such bids cannot be generated, the job yields negative utility on all machines and withdraws from the auction. Obviously, job that becomes the final winning job in the auction brings non-negative revenue () to its consumer agent , resulting in non-negative total revenue of : . Since the proposed auction framework ensures that all consumer agents have non-negative revenue from participation, it is individually rational.
Property 2: The myopic bidding strategy is a weakly dominant strategy for consumer agents to submit bids in the proposed approach.
Proof: Because the self-interested and rational bidders have no knowledge of any other competitors, at the beginning of the auction, all consumer agents follow the myopic bidding strategy and naturally submit bids with maximum revenue for jobs participating in the auction. After solving the WDP in the rth round of the auction, some jobs temporarily win their target machines and become provisional winning jobs. Others fail to compete for their target machines, being classified as provisional losing jobs. When bids are submitted in the (r + 1)th round of the auction, the myopic bidding strategy is still the weakly dominant strategy, which is proven by cases.
Case 1: For the provisional winning jobs, the best and natural option for bidders is to keep following the myopic strategy by submitting the same bids in the rth round. The reason is that the current bids are the most profitable, and it makes no sense for bidders to submit other bids that would reduce their revenues and disclose more private information.
Case 2: For the provisional losing jobs, the myopic bidding strategy incentivizes bidders to submit additional bids with revenue that is second only to bids in the rth round. Then, an alternative strategy is constructed to serve as a comparison, where the agent additionally submits bids with revenues inferior to and . Two cases are shown to prove that the myopic bidding strategy is a weakly dominant strategy over the alternative strategy for bidders to submit bids for the provisional losing jobs:
Case 2-1: When the provisional losing jobs win in the (r + 1)th round by submitting additional bids , the two results of the alternative strategy are considered. First, these jobs lose with bids in the (r + 1)th round; then, there is no doubt that submitting bids is optimal. Second, these jobs win in the (r + 1)th round with bids as well, but it is clear that bids b^ki are more profitable for bidders.
Case 2-2: If the provisional losing jobs fail again in the (r + 1)th round after additional bids are submitted, the same two scenarios are discussed. First, jobs fail with bids in the (r + 1)th round; then, there is no difference between submitting bids and . Second, jobs win by submitting bids . Although bids do not win in the (r + 1)th round, the myopic bidding strategy ensures that bidders submit bids and in the (r + 2)th round, which means that the provisional losing jobs can still win in the (r + 2)th round.
In summary, the proposed iterative auction approach is individually rational, and for both the provisional winning jobs and the provisional losing jobs, the myopic bidding strategy is a weakly dominant strategy for bidders to generate and submit bids.
5. Computational experiment
In this section, extensive computational experiments are conducted to verify the performance of the proposed DIA approach by comparing it with centralized scheduling approaches and decentralized approaches, respectively. Then, the required iteration round for the proposed approach is validated in various cases. Finally, we test the scalability of the proposed approach. All the approaches are coded in MATLAB 2016b (The MathWorks Inc., USA) and Python 3.9, and all experiments are carried out on a personal computer with a 3.6 GHz core, Intel i7CPU, and 8 GB RAM.
5.1. Experimental design and setup
It is necessary to have a wide range of various problem instances for evaluating the proposed approach, and a reasonable evaluation metric is essential to evaluate the performance of an approach. Therefore, this section describes the manner in which problem instances are generated and the evaluation metrics for performance measurement.
5.1.1. Generation of the problem instance
For m uniform parallel machines, each machine has six parameters, and the parameter values are set as follows: m={3,5,10,15} is assumed. The processing speed and setup time are randomly drawn from two uniform distributions: U[10,20] and U[1,5] [59]. The operating cost , setup cost , and idle cost are also randomly obtained, with U[11,15], U[6,10], and U[1,5], respectively. A downward cost trend is observed in the three machine states. The unit profit that a machine gains from processing a job is given by , which is an integer generated by rounding.
Without losing generality, based on the number of machines, the number of consumer agents N={3,5,7,9,11,13,15} is considered to construct problem instances with different levels of competition. When the number of machines is given, the more consumer agents, the more intense the competition for resources among the consumer agents. Afterward, since there is no impact of the number of jobs per consumer agent ni on the performance of the proposed approach, it is assumed that each consumer agent has the same , where . Then, for the five elements of job , the parameters are generated as follows: jobs arrive continuously, and the arrival rate is subject to the Poisson distribution with a mean of λ [60]: , λ=4. The processing requirement and the revenue loss resulting from unit-time tardiness are randomly generated from U[100,300] and U[1,10], respectively. The due date is then calculated using , where α has the values {1.2, 1.4, 1.6, 1.8} [49]. The parameter α represents the due date tightness, and smaller α values indicate tighter due date constraints. Finally, the revenue is generated by using the uniform distribution from the interval .
According to the various parameters, a total of 4 × 7 × 4 × 4 = 448 combinations are included. For each combination, five problem instances are created, resulting in 5 × 448 = 2240 random problem instances in total. Each problem instance is run five times, and the average value is taken as the final solution for comparison.
5.1.2. Performance measurement
To evaluate the effectiveness of the proposed DIA approach, we compare it with several centralized approaches and decentralized approaches. First, regarding dynamic scheduling, four typical centralized approaches are considered: ① five basic dispatching rules (DR) [61], [33], including the well-known first-come-first-served (FCFS), the earliest due date (EDD), the shortest processing time (SPT), the longest processing time (LPT), and the minimum slack (MS); ② complex DR (CDR) combined by these basic rules according to Ref. [62]; ③ deep reinforcement learning (DRL) [63]; and ④ a modified genetic algorithm (MGA) [64]. Second, the five DR and the CDR are implemented in a decentralized environment to act as comparison methods, named DR implemented in a decentralized environment (DR_D) and CDR implemented in a decentralized environment (CDR_D), respectively. The reason is that the proposed DIA approach is developed under the constraint of dynamic multi-agent parallel machines scheduling with incomplete information. We acknowledge that decentralized approaches with the same constraint cannot be found in the literature; therefore, to ensure fairness and comparability, DR are applied to the decentralized environment, following the idea of the methodological comparison in Ref. [33].
The ratio of social welfare is used to evaluate the proposed approach’s performance and is calculated as follows:
where is the social welfare obtained by the proposed DIA approach, is the social welfare generated by each of the six comparison methods described above, and x represents the specific comparison method being used. It is important to note that the maximum welfare of the five DR is and when compared with DR and DR_D. The larger this ratio is, the better the performance of the proposed approach will be.
5.2. Experimental results and analysis
In this section, the results of four computational experiments are presented.
5.2.1. Experiment 1: Comparison with centralized approaches
In the first experiment, the proposed DIA approach is compared with the four centralized approaches. The detailed results for the ratio of social welfare (RSW) of each problem instance are listed in Tables S1-S4 (Appendix A), where PI_N_ represents a problem instance (PI) with N consumer agents and jobs per consumer agent. Table 1 summarizes the average RSW compared with DR, CDR, DRL, and MGA on different numbers of machines, along with the total average values. It should be noted that the maximum number of parallel machines for DRL in the flexibility test was four, as indicated in Ref. [63]. Probably because the DRL model was not trained on many parallel machines, its efficiency decreases significantly when tested on 10 and 15 machines in our study. Consequently, the comparative results between the proposed approach and DRL on 10 and 15 machines are not presented, as they would be of little practical significance.
From Table 1, it can be observed that, on average, the social welfare attained by the DIA reaches 103.5% of that achieved by simple DR, 92.1% of that obtained by CDR, 84.1% of that achieved by DRL, and 78.4% of that achieved by MGA, respectively. This demonstrates that, under the strong constraints of dynamic multi-agent scheduling with incomplete information, the proposed DIA approach can generate scheduling solutions with high social welfare compared with centralized approaches. It can even outperform the basic DR with complete information. Moreover, Table 1 reveals that, as the number of machines increases, the average RSW value increases, indicating that our proposed approach performs better on large-scale machine problem instances. For example, when the number of machines is 15, the social welfare of the DIA is as high as 93.8% of the CDR and 88.2% of the MGA.
As MGA exhibits the best performance among these four centralized approaches, directly comparing the particular RSW (defined in Section 5.1.2) obtained by the MGA and DIA directly is sufficient to illustrate the performance of our DIA approach. In the following section, this RSW is used to analyze the variation in performance of the proposed DIA over different parameters. First, we take α=1.4 as an example to illustrate the impact of the number of jobs per consumer agent, ni, and consumer agents N on the performance of DIA. The results are presented in Fig. 3. Despite the increasing number of jobs and consumer agents, the RSW does not exhibit a statistically significant reduction. This observation suggests that the efficiency of our approach remained stable, without evidence of deterioration in response to the growth in problem scale. Another possible causal factor is that the reliabilities of these two methods are strong, and the current values of and N are insufficient to make their performance fluctuate significantly and regularly. Further experiments are conducted to investigate the effects of larger parameters on the solution, as described in experiment 4 (Section 5.2.4).
Second, regarding the same RSW, Fig. 4 shows how the performance of DIA changes with parameter α. The bars represent the average RSW for the given machine number and α. As can be seen from the four bars and a line corresponding to one machine, with a fixed number of machines, a slight increasing trend is displayed as the parameter α increases. For example, when m = 10, the corresponding RSW values for α = 1.2, 1.4, 1.6 and 1.8 are found to be 81.2%, 83.8%, 84.9%, and 85.3%, respectively. Upon observation, it is also noticed that a slight decline in the RSW occurred when m = 3 and α=1.4. This can be attributed to the superior performance of MGA on these random examples, resulting in a relatively lower RSW. Nonetheless, this does not impede the overall ascending tendency. In addition, the bars with the same color indicate that the RSW increases as the number of machines grows for a given α. This trend aligns with the outcomes presented in Table 1. Notably, when m = 15 and α=1.8, the RSW value reaches its maximum level of 89.2%. These results demonstrate the performance of our approach, exhibiting superior and stable outcomes in cases with looser due date constraints and more machines. The reason may lie in the decreased level of resource competition by consumer agents and increased bidding options for them.
5.2.2. Experiment 2: Comparison with decentralized approaches
The second experiment further verifies the effectiveness of the proposed approach by comparing it with the decentralized approaches. The detailed results compared with basic DR and CDR implemented in a distributed environment are presented in Tables S5-S6 (Appendix A). Table 2 presents a summary of the average changes in the RSW compared with DR_D and CDR_D on various machines, as well as the average RSW. For the basic and CDR, the social welfare of the solutions generated by our approach increases on average to 155.9% and 134.9% for all scenarios, respectively. This indicates that the proposed DIA approach generates solutions with high social welfare and outperforms the rules in a decentralized environment. Furthermore, our approach demonstrates superior performance on a larger scale of machines. More specifically, when the number of machines is increased to 15, the performance of the DIA improved by 85.1% and 54.0%, respectively. Similarly, since complex rules outperform basic rules, it is sufficient to compare DIA with CDR_D in order to demonstrate its superiority. Hence, in the subsequent analysis, we will investigate the variations in the DIA’s performance on different parameters based on the RSW compared with CDR_D.
Regarding the RSW compared with CDR_D, Fig. 5 depicts how the average value of RSW varies with parameters. As shown in Fig. 5, from the four-fold lines, it can be observed that the total average values of RSW become greater as the number of machines increase at any value of α. The observed variation follows the same trend as the mean values presented in Table 2. This further illustrates that the proposed DIA approach can obtain higher quality solutions when solving problems with more machines. The bars show that our approach also performs better as the number of jobs per consumer agent increases within a fixed α. Likewise, keeping the number of jobs and machines m constant, the superiority of our approach becomes more obvious as α increases, except when =5. Subsequently, the average RSW is greatest in cases with α=1.8, =15, and m = 15. In some cases, the CDR may generate high-quality solutions, making the corresponding RSW relatively small. However, the proposed approach has higher RSW in other cases, which compensates for the gap, causing the average RSW to exhibit strong regularity and further demonstrating its superiority over the CDR.
5.2.3. Experiment 3: Iteration rounds
In the third experiment, the iteration rounds needed in the proposed DIA approach for solving different problem instances are summarized and analyzed. The average iteration rounds for each problem instance are adopted. These are calculated according to the following rules: For each problem instance, the number of machines m, consumer agents N, and jobs per consumer agent are fixed; then, the arithmetic average of the required rounds under all α is calculated. Fig. 6 shows the results.
As shown in the four subplots, when the number of machines remains constant, the more jobs there are, the more auction rounds are required. Furthermore, within a fixed ni in each subplot, more iteration rounds are needed in the proposed approach to generate high-quality solutions for a problem with more consumer agents. Comparing lines with the same color in the subplots separately reveals that the growing number of machines make the consumer agents require more auction rounds to reach consensus. Within the context, the required iteration rounds increase more rapidly when becomes greater. Notably, as shown by the four orange lines, when =15, the increment of auction rounds is the greatest, and the rounds peak in the cases with =15, N = 15, and m = 15. Increasing the available machine resources can alleviate competition among the consumer agents to some extent. However, both the bid determination and the WDP become more complex due to the different processing capabilities of the machines. Therefore, more auction rounds are needed to obtain a solution. In addition, the difficulty of solving these problems is compounded by the growing number of jobs entering the auction. This also explains why the orange lines change dramatically.
5.2.4. Experiment 4: Scalability of proposed approach
In the fourth experiment, we analyze the scalability of the proposed approach in terms of the number of consumer agents N and the jobs per consumer agent ni. Following the criteria for selecting metrics used in the experimental analysis described earlier, only MGA and CDR_D are chosen as benchmarks for comparison with the centralized and decentralized methods, respectively.
Fig. 7 shows the changes in the DIA’s performance under different numbers of consumer agents in terms of the RSW compared with the MGA and CDR_D, respectively. In this experiment, =15 is maintained, and the number of customer agents is increased from 18 to 42, corresponding to 270-630 jobs in total. Overall, regardless of the comparison with the MGA or CDR_D, the proposed approach exhibits a similar trend. To be specific, when the number of machines is small (m = 3, represented by the blue line), the RSW decreases, indicating that the performance of the proposed approach decreases slightly as the number of consumer agents grows. However, when there are more machines, the RSW increases; in particular, when compared with CDR_D, the increasing trend is more pronounced. This is because the simultaneous increase in consumer agents and machines complicates the problem exponentially. In such a situation, the deterioration of these two comparison methods, especially CDR_D, far exceeds that of the DIA. This proves in turn that the proposed approach can still maintain a certain level of stability for complex problems.
Fig. 8 reveals the effects of an increase in the number of jobs per consumer agent . Keep N = 15 and increase the jobs per consumer agent from 20 to 60, corresponding to 300-900 jobs in total. Prior to increasing to 30, the RSW values—whether compared with the MGA or CDR—show a downward trend. However, as continues to increase, the RSW increases. Combining these two figures, we can conclude that the social welfare obtained by the proposed approach decreases as the number of consumer agents and jobs per consumer agent (i.e., the total number of jobs) slightly increase. Nevertheless, the growing RSW indicates that our approach has better stability. Especially for problems with more than 500 jobs, our approach deteriorates much less than the comparison approaches. Furthermore, increasing the number of jobs per consumer agent has a smaller impact on the proposed approach than increasing the number of consumer agents.
6. Conclusions and future work
This research studied the multi-agent uniform parallel machines scheduling problem, considering the agents’ individual preferences and private availability information. The dynamic arrival of jobs was also addressed. We have developed a dynamic iterative auction-based approach as a decentralized decision-making procedure to solve the considered problem, with the aim of generating a stable and consensus-based solution with beneficial outcomes. The proposed auction-based approach includes a dynamic auction procedure, bid determination, winner determination, and bid updating, with information privacy protected in each. The dynamic auction procedure ensures that jobs are available for auction immediately after arrival. A straightforward and easy-to-implement bidding strategy without price guidance is applied for the bid determination and updating, overcoming the challenge of bidding for increasing jobs and significantly reducing the calculation costs. In the winner determination, an adaptive Hungarian algorithm is applied to effectively generate solutions. Two theoretical analysis properties of the developed approach are proven, including individual rationality and the fact that the myopic bidding strategy is a weakly dominant strategy for consumer agents. Finally, four types of computational experiments with 2240 problem instances are carried out. The results indicate that our developed approach is capable of achieving high-quality solutions; in particular, it shows good stability for large-scale problems. Additional iteration auction rounds are required in order to generate solutions with high social welfare for problems with greater numbers of consumer agents and jobs.
In addition to the abovementioned advantages of the proposed DIA approach, this approach has limitations that must be taken into account. In terms of this approach, the time complexity of Algorithm 2 for solving the WDP is . As a result, the proposed approach may become time-consuming when the total number of jobs J is sufficiently large. Moreover, the implementation and practicality of the proposed DIA have not been addressed in this work. Further validation may be necessary in real-world manufacturing industries, which often involve lengthy processes and significant time commitments.
In the future, our work will increasingly rely on the auction theory and involve more in-depth research into practical multi-agent scheduling problems. One such challenge is coordination between consumers and multiple resource agents, which often occurs in real-life scenarios. To address this challenge, a many-to-many negotiation process based on the double-auction theory that involves multiple consumer agents and resources will be developed. We will also consider the distance and logistics costs associated with multiple resource agents, which will significantly increase the complexity of bid determination and winner determination. As a result, we need to optimize the bid determination algorithm and winner determination algorithm while reducing their time complexity.
Nomenclature
N Number of consumer agents
i Index of consumer agents
The ith consumer agent
Number of jobs owned by
k Index of jobs
The kth job of
J Total number of jobs
m Number of machines
j Index of machines
The jth machine
t Index of position on a machine
Arrival time of job
Processing load of job
Due date of job
Revenue loss resulting from unit-time tardiness of job
Revenue of job if processed
Processing speed of machine
Setup time of machine
Unit operating cost of machine
Unit setup cost of machine
Unit idle cost of machine
Unit profit that machine gains from processing a job
Completion time of job
Tardiness of job
1, if job is assigned to the tth position on machine ; otherwise 0
Starting time of job assigned to the tth position on machine
Completion time of job assigned to the tth position on machine
Idle time of the tth position on machine
Acknowledgments
This work was supported by the National Natural Science Foundation of China (51975482) and the China Scholarship Council.
Compliance with ethics guidelines
Yaqiong Liu, Shudong Sun, Gaopan Shen, Xi Vincent Wang, Magnus Wiktorsson and Lihui Wang declare that they have no conflict of interest or financial conflicts to disclose.
B.Wang, F.Tao, X.Fang, C.Liu, Y.Liu, T.Freiheit. Smart manufacturing and intelligent manufacturing: a comparative review. Engineering, 7 (6) (2021), pp. 738-757.
[2]
T.Yang, X.Yi, S.Lu, K.H.Johansson, T.Chai. Intelligent manufacturing for the process industry driven by industrial artificial intelligence. Engineering, 7 (9) (2021), pp. 1224-1230.
[3]
E.B.Edis, C.Oguz, I.Ozkarahan. Parallel machine scheduling with additional resources: notation, classification, models and solution methods. Eur J Oper Res, 230 (3) (2013), pp. 449-463.
[4]
D.Wang, Y.Yu, Y.Yin, T.C.E.Cheng. Multi-agent scheduling problems under multitasking. Int J Prod Res, 59 (12) (2021), pp. 3633-3663.
[5]
A.Agnetis, D.Pacciarelli, A.Pacifici. CCombinatorial models for multi-agent scheduling problems. E. Levner (Ed.), Multiprocessor scheduling: theory and applications, IntechOpen, London (2007), pp. 21-46.
[6]
M.L.Pinedo. Scheduling: theory, algorithms and systems. (4th ed.), Springer, New York (2012).
[7]
Y.Liu, S.Sun, X.V.Wang, L.Wang. An iterative combinatorial auction mechanism for multi-agent parallel machine scheduling. Int J Prod Res, 60 (1) (2022), pp. 361-380.
[8]
J.Pei, J.Wei, B.Liao, X.Liu, P.M.Pardalos. Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent. Ann Oper Res, 294 (2020), pp. 191-223.
[9]
F.Yu, P.Wen, S.Yi. A multi-agent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan. Adv Mech Eng, 10 (2) (2018), pp. 1-14.
[10]
L.Mönch, L.Shen. Parallel machine scheduling with the total weighted delivery time performance measure in distributed manufacturing. Comput Oper Res, 127 (2021), 105126.
[11]
Abdel-JabbarMAH, KacemI, MartinS. 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.
[12]
Y.Zhou, R.Kumar, S.Tang. Incentive-based distributed scheduling of electric vehicle charging under uncertainty. IEEE Trans Power Syst, 34 (1) (2019), pp. 3-11.
[13]
N.N.Alimin, N.A.A.Rahmin, G.Ibragimov, M.A.Nazihah. Multi-start local search for online scheduling in parallel operating theatre. Adv Math Sci J, 9 (12) (2020), pp. 10915-10927.
[14]
A.Lieder, R.Stolletz. Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways. Transp Res Part E, 88 (2016), pp. 167-188.
[15]
J.Yuan, C.T.Ng, T.Cheng. Scheduling with release dates and preemption to minimize multiple max-form objective functions. Eur J Oper Res, 280 (3) (2020), pp. 860-875.
[16]
T.Kugler, E.E.Kausel, M.G.Kocher. Are groups more rational than individuals? A review of interactive decision making in groups. WIREs Cogn Sci, 3 (4) (2012), pp. 471-482.
[17]
M.Klein, P.Faratin, H.Sayama, Y.Bar-Yam. Negotiating complex contracts. Group Decis Negot, 12 (2) (2003), pp. 111-125.
[18]
C.Schneeweiss. Distributed decision making. Springer, Berlin (2003).
[19]
Y.Lu, L.Yang, K.Yang, Z.Gao, H.Zhou, F.Meng, et al. A distributionally robust optimization method for passenger flow control strategy and train scheduling on an urban rail transit line. Engineering, 12 (2022), pp. 202-220.
[20]
P.Renna. Multi-agent based scheduling in manufacturing cells in a dynamic environment. Int J Prod Res, 49 (5) (2011), pp. 1285-1301.
[21]
ArrowKJ, SenA, SuzumuraK. Handbook of social choice and welfare. Volume 2. London:Elsevier; 2011.
[22]
G.Deconinck, K. DeCraemer, B.Claessens. Combining market-based control with distribution grid constraints when coordinating electric vehicle charging. Engineering, 1 (4) (2015), pp. 453-465.
[23]
J.Tang, C.Zeng, Z.Pan. Auction-based cooperation mechanism to parts scheduling for flexible job shop with inter-cells. Appl Soft Comput, 49 (2016), pp. 590-602.
[24]
Q.Zhu, X.Wang. Auction-based capacity allocation in two parallel machines with inclusive processing set restrictions. Math Probl Eng, 2022 (2022), pp. 1-11.
[25]
N.G.Hall, Z.Liu. Market good flexibility in capacity auctions. Prod Oper Manag, 22 (2) (2013), pp. 459-472.
[26]
W.Song, D.Kang, J.Zhang, H.Xi. A multi-unit combinatorial auction based approach for decentralized multi-project scheduling. Auton Agent Multi-Agent Syst, 31 (6) (2017), pp. 1548-1577.
[27]
A.Daoud, F.Balbo, P.Gianessi, G.Picard. ORNInA: a decentralized, auction-based multi-agent coordination in ODT systems. AI Commun, 34 (1) (2021), pp. 37-53.
[28]
M.Zade, S.D.Lumpp, P.Tzscheutschler, U.Wagner. Satisfying user preferences in community-based local energy markets—auction-based clearing approaches. Appl Energy, 306 (2022), 118004.
[29]
E.Kutanoglu, S.D.Wu. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Trans, 31 (9) (1999), pp. 813-826.
[30]
C.Zeng, J.Tang, Z.Fan, C.Yan. Auction-based approach for a flexible job-shop scheduling problem with multiple process plans. Eng Optim, 51 (11) (2019), pp. 1902-1919.
[31]
C.Zeng, G.Qi, Z.Liu, J.Tang, Z.P.Fan, C.Yan. Auction-based approach with improved disjunctive graph model for job shop scheduling problem with parallel batch processing. Eng Appl Artif Intell, 110 (2022), 104735.
[32]
W.Kong, Y.Lei, J.Ma. Virtual machine resource scheduling algorithm for cloud computing based on auction mechanism. Optik, 127 (12) (2016), pp. 5099-5104.
[33]
P.Dewan, S.Joshi. Auction-based distributed scheduling in a dynamic job shop environment. Int J Prod Res, 40 (5) (2002), pp. 1173-1191.
[34]
P.Dewan, S.Joshi. Implementation of an auction-based distributed scheduling model for a dynamic job shop environment. Int J Comput Integr Manuf, 14 (5) (2001), pp. 446-456.
[35]
M.Masin, M.O.Pasaogullari, S.Joshi. Dynamic scheduling of production-assembly networks in a distributed environment. IIE Trans, 39 (4) (2007), pp. 395-409.
[36]
J.A.Araúzo, J.Pajares, A.Lopez-Paredes. Simulating the dynamic scheduling of project portfolios. Simul Model Pract Theory, 18 (10) (2010), pp. 1428-1441.
[37]
L.Tosselli, V.Bogado, E.Martínez. A repeated-negotiation game approach to distributed (re)scheduling of multiple projects using decoupled learning. Simul Model Pract Theory, 98 (2020), 101980.
[38]
VishalatchiM, KrishnamoorthyN, SangeethaS. 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.
[39]
MukherjeeP, GoswamiS, PaulB, ChandaCK. 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.
[40]
M.P.Wellman, W.E.Walsh, P.R.Wurman, J.K.MacKie-Mason. Auction protocols for decentralized scheduling. Games Econ Behav, 35 (1-2) (2001), pp. 271-303.
[41]
PanH, GaoH, MaW, LiuJ. 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.
[42]
F.S.Hsieh. Combinatorial reverse auction based on revelation of Lagrangian multipliers. Decis Support Syst, 48 (2) (2010), pp. 323-330.
[43]
B.Mansouri, E.Hassini. A Lagrangian approach to the winner determination problem in iterative combinatorial reverse auctions. Eur J Oper Res, 244 (2) (2015), pp. 565-575.
[44]
T.Pennanen. Efficient allocations in double auction markets. Math Oper Res, 47 (2) (2022), pp. 1648-1663.
[45]
C.Wang, F.Dargahi, M.F.H.Bhuiyan. On the tradeoff between privacy and efficiency: a bidding mechanism for scheduling non-commercial services. Comput Ind, 63 (6) (2012), pp. 610-618.
[46]
L.Liu, C.Wang, J.Wang. A combinatorial auction mechanism for surgical scheduling considering surgeon’s private availability information. J Comb Optim, 37 (1) (2019), pp. 405-417.
[47]
MerzF, SchwindtC, WestphalS, ZimmermannJ. 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. Piscataway: IEEE; 2021. p. 863-8.
[48]
A.Ebrahimi, H.W.Jeon, S.Lee, C.Wang. 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, 141 (2020), 106295.
[49]
Y.F.Hung, J.S.Bao, Y.E.Cheng. Minimizing earliness and tardiness costs in scheduling jobs with time windows. Comput Ind Eng, 113 (2017), pp. 871-890.
[50]
Y.He, Y.Li, T.Wu, J.W.Sutherland. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops. J Clean Prod, 87 (2015), pp. 245-254.
N.T.Nguyen, T.T.Nguyen, M.Roos, J.Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Auton Agent Multi-Agent Syst, 28 (2) (2014), pp. 256-289.
[53]
K.T.Fang, B.M.T.Lin. Parallel-machine scheduling to minimize tardiness penalty and power cost. Comput Ind Eng, 64 (1) (2013), pp. 224-234.
[54]
F.M.Menezes, P.K.Monteiro. An introduction to auction theory. Oxford University Press, Oxford (2004).
[55]
N.Nisan. Bidding languages for combinatorial auctions. P. Cramton, Y. Shoham, R. Steinberg (Eds.), Combinatorial auctions, MIT Press Scholarship Online, Cambridge (2005), pp. 215-232.
[56]
L.M.Ausubel, P.Milgrom. Ascending proxy auctions. P. Cramton, Y. Shoham, R. Steinberg (Eds.), Combinatorial auctions, MIT Press Scholarship Online, Cambridg (2005), pp. 79-98.
[57]
PikovskyA. Pricing and bidding strategies in iterative combinatorial auctions. Munich: Technische Universität München; 2008.
[58]
Z.Wang, Z.Feng, P.Zhang. An iterative Hungarian algorithm based coordinated spectrum sensing strategy. IEEE Commun Lett, 15 (1) (2011), pp. 49-51.
[59]
G.Rabadi, R.J.Moraga, A.Al-Salem. Heuristics for the unrelated parallel machine scheduling problem with setup times. J Intell Manuf, 17 (1) (2006), pp. 85-97.
[60]
Y.Liu, L.Wang, Y.Wang, X.V.Wang, L.Zhang. Multi-agent-based scheduling in cloud manufacturing with dynamic task arrivals. Procedia CIRP, 72 (2018), pp. 953-960.
[61]
M.Ðurasević, D.Jakobović. A survey of dispatching rules for the dynamic unrelated machines environment. Expert Syst Appl, 113 (2018), pp. 555-569.
[62]
J.H.Lee, Y.Kim, Y.B.Kim, B.H.Kim, G.H.Jung, H.J.Kim. A sequential search method of dispatching rules for scheduling of LCD manufacturing systems. IEEE Trans Semicond Manuf, 33 (4) (2020), pp. 496-503.
[63]
R.Liu, R.Piplani, C.Toro. Deep reinforcement learning for dynamic scheduling of a flexible job shop. Int J Prod Res, 60 (13) (2022), pp. 4049-4069.
[64]
C.Y.Cheng, L.W.Huang. Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. J Manuf Syst, 42 (2017), pp. 1-10.
PDF
(2174KB)
