# Auction-Based Capacity Allocation in Two Parallel Machines with Inclusive Processing Set Restrictions

Authors: Qianqian Zhu; Xiuli Wang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

We consider the scarce capacity allocation problem in two parallel machines with inclusive processing set restrictions. Our focus is to design an auction mechanism to allocate the production capacity among several selfish customers effectively and efficiently. In our iterative ascending auction mechanism, we need to design jointly two things: who wins what and who pays what. First, we propose an adaptive ascending pricing policy to ensure that bidding by truthful processing requirements and keeping on bidding until the ask prices reach his real revenue is a dominant strategy for each customer. Second, we establish a facility owner’s profit maximization model to determine the capacity allocation in two parallel machines with inclusive processing set restrictions; it is an NP hard problem; we also develop a heuristic based on the Lagrangian relaxation technology to obtain the suboptimal solutions. Our computational analysis shows that the auction mechanism can achieve more than 87% of the global system value.


---

## Body

## 1. Introduction

In current customer-oriented market, the decentralized operating mode has become very popular in the manufacturing industries. This mode can provide services such as product design, manufacturing, and testing for small and medium-sized enterprises by the establishment of a service platform, which is a good solution to the problem of the insufficient funds and talents for small- and medium-sized enterprises, such as the United Microelectronics Corporation (UMC) which uses the online customer information portal MyUMC to provide transparent processing pricing, processing policies, and real-time processing capacity information to customers and allows the selfish customers to make decentralized decisions on booking processing capacity. However, due to the customers’ selfish behaviours, the efficiency of the overall system would be reduced to some extent. Therefore, it is important to design an appropriate mechanism to guide individual competition results towards global optimization for the scarce capacity allocation problem in the decentralized operating mode.To the best of our knowledge, the auction-based method was a suitable approach to solve the production capacity allocation problem, and it has been applied in a single machine and job shop environment [1, 2]. In practice, there existed a scenario that the facility owner possesses parallel machines and they may have the same speed but differ in their functionality, which could be called inclusive processing set (IPS) restrictions. Our study is focused on this case.There are many applications for capacity allocation problem with IPS restriction. A classical application is assigning several cloud computing tasks with different memory requirements to processors with the same speed but different memory capacities. Each task can be processed by a processor with a memory capacity no less than its memory requirement. Another application exists in testing enterprises. Assuming there are several customers, each with a set of workpieces that needs to be tested, the testing enterprise has two pieces of equipment with the same speed but they differ in test accuracy. High precision testing equipment can provide high and low precision testing services, but low precision testing equipment can only provide low precision testing services. Here, the testing organization can be described as the “facility owner,” the testing equipment can be described as the “machine,” the set of workpieces can be described as the “order,” and the problem that the facility owner needs to do is allocating the parallel machine capacity to several competing customers, so as to optimize one or more objectives.In this study, we propose an iterative ascending auction mechanism to solve the capacity allocation problem in two parallel machines with IPS restrictions. The main research work is as follows. First, we design the auction mechanism that the selfish customers can use private information to make effective decisions without knowing the information and strategies of other customers. The pricing policy can make the customers bid by their truthful processing requirements and keep on bidding until the ask prices reach their real revenue. In this way, the customers’ local decisions can prompt the facility owner to make decisions that promote the achievement of the collective goal. Second, the winner determination problem is a bid selecting and scheduling problem in two parallel machines with IPS restrictions, and it is NP hard; we develop a heuristic using the Lagrangian relaxation technique to obtain approximate optimal solutions for the large-sized instances in a reasonable time.The remaining part of the paper is structured as follows. Section2 reviews the related work. Then, in Section 3, a detailed description of our problem setting is described. In Section 4, a global optimization problem is studied for mainly benchmarking purposes. In Section 5, an auction mechanism is proposed for the capacity allocation in two parallel machines with IPS restrictions. The pricing and winner determination problems, as the main components of our auction mechanism, are discussed in Sections 5.2 and 5.3, respectively. In Section 6, a computational analysis of the performance for the auction mechanism is presented. Finally, Section 7 provides concluding remarks.


## 2. Literature Review

In this section, we provide a brief review of the relevant literature in the fields of decentralized scheduling, auctions for resource allocation problems, and parallel machine scheduling with IPS restrictions.


### 2.1. Decentralized Scheduling

In a decentralized scheduling problem, the facility owner and several customers make decisions rationally for their own interest, and their selfish behaviours result in a situation that can be characterized as system equilibrium. However, such a system equilibrium may lead to suboptimal system performance from a global perspective. The literature on this subject mainly has the following two perspectives: (a) assuming all information is public, characterize and analyse the quality of the resulting system equilibria from the perspective of the global system performance, which can be quantitatively characterized by the price of anarchy (POA) [3–8]; (b) assuming the private information is not public, design and analyse mechanisms to guide individual competition results towards global optimization. Our study is belonging to the second case.When the private information is not public, it is necessary to provide a mechanism that all customers commit their truthful information, because the facility owner requires the customers’ private information for a global optimal decision. This research field is known as mechanism design, which began with the work of Leonid Hurwicz [9]. The mechanism design problem can be regarded as the process of solving the optimization problem of incomplete expression. In this case, the designer should first induce this expression and then solve the optimization problem [10]. There are two methods to induce the truthful information from agents: one class of mechanisms called direct revelation mechanisms (DRMs), which directly obtain truthful information by letting agents report their true types; the second called indirect mechanisms, the basic idea is to provide each agent with a choice of action and then assign a result to each action group; the strategy chosen by each agent will indirectly reflect their true type. Auctions are common examples of indirect mechanisms, and they provide several advantages over DRMs for the machine capacity allocation problems, such as the universal and anonymous auctions [11]. In the following subsection, we will specifically introduce the application of the auction mechanisms.


### 2.2. Auctions for Resource Allocation Problems

Auctions are market-based methods with an explicit set of rules determining prices and allocation of resource according to bids from the market participants [12]. The common auction formats include the Dutch auction, the English auction, the first price sealed bid auction, and the second price sealed bid auction (or Groves-Clarke-Vickery mechanism). These auction formats have been used to sell a wide range of objects, assets, and commodities [13]. With the development of auction theory, many new auctions formats have been designed for resource allocation problems in field of telecommunication system, traffic system, electric system, and so on. In telecommunication system, Cramton [14] presented a new combinatorial clock auction for governments to assign and price licenses for wireless communications. Cramton and Ockenfels [15] analysed and discussed the simultaneous ascending multiband auction for spectrum. In electric markets, Tang and Jain [16] designed auction mechanisms for the aggregators to procure stochastic resources. In traffic systems, Rassenti et al. [17] proposed a combinatorial auction mechanism for the allocation of airport time slots. Yang et al. [18] proposed an auction-based unified approach for prebooking urban logistics facilities.A few papers also propose auction mechanisms for machine capacity allocation problems. For example, Kutanoglu and Wu [19] proposed a general auction mechanism for the job shop scheduling problem which uses the notion of multi-item combinatorial auction. They also concluded that there are strong links between Lagrangian-based decomposition and combinatorial auction. Wellman et al. [1] first developed a broad framework for using markets to solve decentralized scheduling problems. They presented an ascending auction mechanism for capacity allocation problem in a single machine environment with multiple customers each having an order. They also proved that the equilibrium prices may not exist when using time slots as market goods. Dewan and Joshi [2] considered the distributed scheduling problem with the objective of minimizing earliness-tardiness penalties in a job shop environment. They presented an auction mechanism to schedule orders and proposed the iterative price adjustment method to reduce resource contention for the job. Hall and Liu [11] designed an auction mechanism to allocate the limited single machine production capacity among several competing customers, each having an order. Their market goods were time blocks and then proved that the equilibrium solution always exists but is not unique. Karabat and Yalcn [20] considered the pricing and production capacity allocation problem in the single machine environment and proposed an auction mechanism that uses the finished products as market goods for the private information case. They also developed alternative pricing strategies and conducted research towards the impact of the proposed auction mechanism on allocation efficiency. From the above, we see that all these studies present auction mechanisms for the capacity allocation problems in a single machine or job shop environment. In this paper, we aim to design an auction mechanism for the capacity allocation problem in two parallel machines with IPS restrictions.


### 2.3. Parallel Machine Scheduling with IPS Restrictions

There are many studies in the literature on parallel machine scheduling with IPS restrictions. Most of those focus on the development of the approximation algorithm (Polynomial Time Approximation Scheme, PTAS). For example, Kafura and Shen [21] considered a computing system model with several independent but identical processors, each with a limited amount of private memory. They proposed a largest memory time first (LMTF) algorithm to minimize the total completion time. Hwang et al. [22] considered the parallel machines scheduling problem in which the process service requests from various customers who are entitled to many different grades of service levels. They proposed a lowest grade and longest processing time (LG-LPT) algorithm for the problem. Ou et al. [23] developed a polynomial time approximation algorithm based on the LG-LPT algorithm. Li and Wang [24] extended the research problem of Kafura and Shen [21]; they studied the parallel machine scheduling problem with both release time and IPS constraints and developed a polynomial time approximation algorithm; Li et al. [25] considered parallel machine scheduling problems with batch processing and IPS restrictions and developed the polynomial time approximation algorithms for the same and different release times, respectively.In this study, the winner determination problem has the following differences from the above researches. First, our winner determination problem features two concepts, the bid selection and two parallel machines’ scheduling with IPS restrictions. Second, our winner determination problem aims to maximize the profit, whereas the above studies all adopt the traditional objective functions. In addition, the efficiency of the auction mechanism is very important, so we develop a fast heuristic to solve the winner determination problem in reasonable time.


## 2.1. Decentralized Scheduling

In a decentralized scheduling problem, the facility owner and several customers make decisions rationally for their own interest, and their selfish behaviours result in a situation that can be characterized as system equilibrium. However, such a system equilibrium may lead to suboptimal system performance from a global perspective. The literature on this subject mainly has the following two perspectives: (a) assuming all information is public, characterize and analyse the quality of the resulting system equilibria from the perspective of the global system performance, which can be quantitatively characterized by the price of anarchy (POA) [3–8]; (b) assuming the private information is not public, design and analyse mechanisms to guide individual competition results towards global optimization. Our study is belonging to the second case.When the private information is not public, it is necessary to provide a mechanism that all customers commit their truthful information, because the facility owner requires the customers’ private information for a global optimal decision. This research field is known as mechanism design, which began with the work of Leonid Hurwicz [9]. The mechanism design problem can be regarded as the process of solving the optimization problem of incomplete expression. In this case, the designer should first induce this expression and then solve the optimization problem [10]. There are two methods to induce the truthful information from agents: one class of mechanisms called direct revelation mechanisms (DRMs), which directly obtain truthful information by letting agents report their true types; the second called indirect mechanisms, the basic idea is to provide each agent with a choice of action and then assign a result to each action group; the strategy chosen by each agent will indirectly reflect their true type. Auctions are common examples of indirect mechanisms, and they provide several advantages over DRMs for the machine capacity allocation problems, such as the universal and anonymous auctions [11]. In the following subsection, we will specifically introduce the application of the auction mechanisms.


## 2.2. Auctions for Resource Allocation Problems

Auctions are market-based methods with an explicit set of rules determining prices and allocation of resource according to bids from the market participants [12]. The common auction formats include the Dutch auction, the English auction, the first price sealed bid auction, and the second price sealed bid auction (or Groves-Clarke-Vickery mechanism). These auction formats have been used to sell a wide range of objects, assets, and commodities [13]. With the development of auction theory, many new auctions formats have been designed for resource allocation problems in field of telecommunication system, traffic system, electric system, and so on. In telecommunication system, Cramton [14] presented a new combinatorial clock auction for governments to assign and price licenses for wireless communications. Cramton and Ockenfels [15] analysed and discussed the simultaneous ascending multiband auction for spectrum. In electric markets, Tang and Jain [16] designed auction mechanisms for the aggregators to procure stochastic resources. In traffic systems, Rassenti et al. [17] proposed a combinatorial auction mechanism for the allocation of airport time slots. Yang et al. [18] proposed an auction-based unified approach for prebooking urban logistics facilities.A few papers also propose auction mechanisms for machine capacity allocation problems. For example, Kutanoglu and Wu [19] proposed a general auction mechanism for the job shop scheduling problem which uses the notion of multi-item combinatorial auction. They also concluded that there are strong links between Lagrangian-based decomposition and combinatorial auction. Wellman et al. [1] first developed a broad framework for using markets to solve decentralized scheduling problems. They presented an ascending auction mechanism for capacity allocation problem in a single machine environment with multiple customers each having an order. They also proved that the equilibrium prices may not exist when using time slots as market goods. Dewan and Joshi [2] considered the distributed scheduling problem with the objective of minimizing earliness-tardiness penalties in a job shop environment. They presented an auction mechanism to schedule orders and proposed the iterative price adjustment method to reduce resource contention for the job. Hall and Liu [11] designed an auction mechanism to allocate the limited single machine production capacity among several competing customers, each having an order. Their market goods were time blocks and then proved that the equilibrium solution always exists but is not unique. Karabat and Yalcn [20] considered the pricing and production capacity allocation problem in the single machine environment and proposed an auction mechanism that uses the finished products as market goods for the private information case. They also developed alternative pricing strategies and conducted research towards the impact of the proposed auction mechanism on allocation efficiency. From the above, we see that all these studies present auction mechanisms for the capacity allocation problems in a single machine or job shop environment. In this paper, we aim to design an auction mechanism for the capacity allocation problem in two parallel machines with IPS restrictions.


## 2.3. Parallel Machine Scheduling with IPS Restrictions

There are many studies in the literature on parallel machine scheduling with IPS restrictions. Most of those focus on the development of the approximation algorithm (Polynomial Time Approximation Scheme, PTAS). For example, Kafura and Shen [21] considered a computing system model with several independent but identical processors, each with a limited amount of private memory. They proposed a largest memory time first (LMTF) algorithm to minimize the total completion time. Hwang et al. [22] considered the parallel machines scheduling problem in which the process service requests from various customers who are entitled to many different grades of service levels. They proposed a lowest grade and longest processing time (LG-LPT) algorithm for the problem. Ou et al. [23] developed a polynomial time approximation algorithm based on the LG-LPT algorithm. Li and Wang [24] extended the research problem of Kafura and Shen [21]; they studied the parallel machine scheduling problem with both release time and IPS constraints and developed a polynomial time approximation algorithm; Li et al. [25] considered parallel machine scheduling problems with batch processing and IPS restrictions and developed the polynomial time approximation algorithms for the same and different release times, respectively.In this study, the winner determination problem has the following differences from the above researches. First, our winner determination problem features two concepts, the bid selection and two parallel machines’ scheduling with IPS restrictions. Second, our winner determination problem aims to maximize the profit, whereas the above studies all adopt the traditional objective functions. In addition, the efficiency of the auction mechanism is very important, so we develop a fast heuristic to solve the winner determination problem in reasonable time.


## 3. Preliminaries

We formally describe the problem under study as follows: We have a setN of n competing customer orders interested in using the facility owner’s production capacity. The facility owner possesses two parallel machines M1 and M2 which differ in their functionality but not in their processing speeds. We assume that M2 can process all those orders that M1 can process. The planning horizon spans a time period t=1,2,…,T, and the facility owner sets per unit reserve values v1 and v2 for machines M1 and M2, respectively.Associated with each customer orderi is a processing time pi, a deadline di, a revenue ui, and a machine index ai=1 or 2. We assume that pi, di, and ui are integer valued. Let N1=i|ai=1,i∈N, and N2=N/N1. Thus, M1 can process those customer orders in N1, and M2 can process those customer orders in N.In the decentralized decision-making environment, both the facility owner and the customers hold information privately. The facility owner’s objective is to maximize its profit from selling the capacity to customers and holding any unallocated capacity at their reserve values; each customer’s objective is to maximize its profit from getting its revenue through purchasing the facility owner production capacity to produce order.


## 4. Global Optimization Problem

In this section, we assume the information of the customer orders’ processing requirements and revenues is public. First, we model the global optimization problem. Then we identify some properties of the optimal solution that can help us to develop heuristics for the winner determination problem.The objective of the global optimization problem is to maximize the system profit. Without loss of generality, we assume that the customer orders are numbered in nondecreasing sequence of the deadlines, and the shortest processing times break the ties. Set three binary decision variablesxit1, xit2, and yit, where xit1=1 denotes that customer order i∈N1 is accepted and completed at time t on machine M1; otherwise xit1=0; xit2=1 denotes that customer order i∈N1 is accepted and completed at time t on machine M2; otherwise xit2=0; yit=1 denotes that customer order i∈N2 is accepted and completed at time t on machine M2; otherwise yit=0. We formulate the global optimization problem as the following integer linear programming model:(1)GOPmax∑i∈N1∑t=piTui−v1pixit1+∑i∈N1∑t=piTui−v2pixit2+∑j∈N2∑t=pjTuj−v2pjyjt+v1+v2T(2)s.t.∑t=piTxit1+∑t=piTxit2≤1,∀i∈N1,(3)∑t′=pjTyjt′≤1,∀j∈N2,(4)∑i∈N1∑s=maxpi,tmint+pi−1,Txit2+∑j∈N2∑s′=maxpj,tmint+pj−1,Tyjs′≤1,1≤t≤T,(5)∑i∈N1∑s=maxpi,tmint+pi−1,Txit1≤1,1≤t≤T,(6)∑t=1Ttxit1≤di,∀i∈N1,(7)∑t=1Ttxit2≤di,∀i∈N1,(8)∑t=1Ttyjt≤dj,∀j∈N2.In the above model GOP, Constraints (2) and (3) state that the accepted customer orders should be processed exactly once. Constraints (4) and (5) state that, in each time slot, at most one customer order can be processed on machines M1 and M2, respectively. Constraints (6), (7), and (8) make sure that the accepted customer orders are completed before their deadlines.Now, we present some optimal properties of the solution for the global optimization problem.Lemma 1.
For the global optimization problem, there is an optimal schedule in which the accepted customer orders are processed in the earliest due date (EDD) order on both machines.Proof.
Assuming thatπ∗ is an optimal solution for the global optimization problem, in π∗, there are two adjacent customer orders i and j, and j is processed after i, and di>dj. Let t be the start time of i. Perform a neighbor-pair exchange on order i and order j, and get a new solution π′.
Inπ∗, the completion times of i and j are t+pi≤di and t+pi+pj≤dj, respectively. In π′, the completion times of i and j are t+pi+pj and t+pj, respectively. As we know, di>dj, so t+pi+pj≤dj<di, t+pj<dj. Customer orders i and j can also be completed before their deadlines; the new solution π′ is also an optimal solution. Therefore, we reach the conclusion.Lemma 1.
It tells us that no matter which set the accepted customer orders come from, they should be scheduled according to the EDD rule on each machine.Lemma 2.
For the global optimization problem, there is an optimal schedule in which if at least one order ofSi is processed on one of the machines, then customer order i is also accepted for processing, where Si=k|pk>pi,dk≤di,uk≤uiandak≥ai, i∈N.Proof.
Assume thatπ∗ is an optimal solution for the global optimization problem, and customer order i is not in π∗, but customer order k in the set Si is accepted and completed at time t in π∗, where Si=k|pk>pi,dk≤di,uk≤uiandak≥ai, i∈N and t≤dk. Knowing that ak≥ai, the machine that can process k can also process i, so we can replace k by i. Denote the new solution as π′.
In the new solutionπ′, the completion time of i is t, we see that dk≤di, so t≤di, and customer order i can also be processed by its deadline in π′. As known pk>pi and uk≤ui, so the profit of π′ is larger than that of π∗, a contradiction arises. Therefore, we reach the conclusion.Lemma 2.
It is implied that if a solution only includes customer orderk but not i, then it is not optimal.


## 5. Private Information Problem

In this section, we consider the capacity allocation problem, in which the customers keep all the information private, except for the processing times and deadlines. We propose an iterative ascending auction mechanism to solve the private information case. In the following, we will elaborate our auction mechanism from auction protocol, pricing problem, and winner determination problem.


### 5.1. Auction Protocol

In our iterative ascending auction mechanism, the auctioneer is the facility owner who owns two parallel machines that have the same processing speed but differ in their functionality. The bidders are the customers; each of them has an order to process. The market goods are time blocks; each customer can bid for one single time block at once.In the first round, the facility owner sets the initial ask priceαi for customers, and (a) each customer sends a bid for processing order so as to maximize his own profit; the bids of the customers are defined as Bi=pi,di,ai,αi, where pi and di are the order’s processing time and deadline. Once the processing time and deadlines of the customer orders are confirmed in the first round, it cannot be changed. (b) Then the facility owner collects all bids and determines which bids to accept in order to maximize his own profit and updates the ask price αi for each customer.Step (a) and (b) will be iterated; as the ask prices continue to rise gradually, customers gradually withdraw from competition. Once any customer withdraws from the competition, he shall not return to participate in the auction again. If none of the customers submits a new bid, then the auction is terminated.The design of an optimal auction mechanism (i.e., pricing policy and winner determination algorithm) should fulfil the following properties:(1)
Individual rationality means that if a customer participates in the auction mechanism, his profit is at least as high as the profit that he is not participating.(2)
Incentive compatibility means that bidding by the truthful order information is a dominant strategy for each customer.(3)
Global optimization means the winner determination problem should be a global optimization problem when all the customers bid by their true values.(4)
Computational efficiency means the auction should reach closure in reasonable time and at reasonable computational expense.Nisan et al. [26] analyse that the second price sealed auction satisfies the above properties (1) and (2) in combinatorial auctions. However, a sealed auction is less efficient and profitable than an ascending auction in production scheduling problems (Hall and Liu 2015). What is more, in the private value model, an ascending auction is equivalent to a second price sealed auction. That is because, when the value of market goods for each customer is independent of the others, each customer’s dominant strategy is to keep in bidding until the ask price reaches his value, regardless of whether he can observe the process of the auction. At last, the winner will be the one who has the highest value. So the ascending auction mechanism can also be designed to satisfy properties (1) and (2) in our production capacity allocation problem.In our problem, the winner determination problem is NP hard, so the above properties (3) and (4) are incompatible. When the problem size is small, the optimal solution can be obtained in a limited time. However, when the problem size is large, the optimal solution cannot be obtained in a reasonable time. Therefore, we use approximate optimal solution in exchange for high computational efficiency.For our auction mechanism, the purpose of the pricing problem is to encourage all the customers to reveal truthful processing requirements, such as machine indexes, processing times, and deadlines, and make the customers’ profits nonnegative; the winner determination problem is NP hard; we aim to develop a fast heuristic to ensure that the auction reaches closure in reasonable time and at reasonable computational expense.


### 5.2. Pricing Problem

We define the ask price in roundk−1 for each customer ii∈N as αik. It consists of two parts: (a) current price βik−1, which reflects the current capacity scarcity under the generated schedule in round k−1, and (b) price increment γik , which reflects the expected impact on capacity scarcity caused by potential bids.First, we define the current priceβik in round k for customer i, based on the generated schedule in round k−1:(1)
If no time slots beforedi are allocated in round k−1 on both machines, the βik=v1+v2/2.(2)
If the time slots beforedi are allocated to orders 1,2,…,ni with prices α1k−1,α2k−1,…,αnik−1 in round k−1 on both machines, then βik is equal to the weighted average of the bid prices of all allocated time slots and the total reserved value of all unallocated time slots. It is clear that the last orders on both machines may be partially processed in 0,di. To simplify the expression of βik, let p¯jk−1 be the length of the time slots within 0,di that were allocated to order j on machine ai in round k−1. If order j is the last order on one of the machines before di, then, p¯jk−1=pj−max0,Cjk−1−dj; else p¯jk−1=pj, where Cjk−1 is the completion time of the order j. Let Iik−1 be the idle times before di on the two machines at round k−1. Then βik is equal to a weighted average price:(9)βik=2∑h=1niαhk−1p¯hk−1+Iik−1v1+v22di.Then, we define the price incrementγik in round k for customer i; it is based on (a) the flexibility of order processing related to its deadline and machine index, if the flexibility of order processing impact on resource scarcity is greater and, consequently, the price increment increases; (b) the number of bids received by this time block that contains each individual time slot. The definition is as follows:(1)
If no time slots beforedi are allocated in round k−1, then (10)γik=ρpiaidi.(2)
If the time slots beforedi are allocated in round k−1, then(11)γik=ρpiaidi+∑t=1diDtk−1Ndi.ρ are predetermined constants, called price adjustment factors; ai, pi, and di are order i′ s machine index, processing time, and deadline; Dtk−1 is the number of bids that contain time slot t in round k−1.The purpose of the pricing problem is to encourage the customers to reveal truthful machine indexes, processing times, and deadlines. We assume that the customer would not pretend that he has a smaller machine index and processing time and a greater deadline. See, for example, a customerj having an order with a machine index aj=2, a processing time pj=5, and a deadline dj=10. It is obvious that he would not pretend pj<5, or dj>10. If he pretends aj=1, his order may be assigned to machine M1 or M2; however, machine M1 cannot process a high index order, so it is impossible for him to bid by a false smaller machine index. So, in our pricing problem, we only need to ensure that the customer would not bid by a false larger machine index and processing time and a shorter deadline. From the above definition of price, we can see that the initial ask price for customer ii∈N is αi=v1+v2/2+ρpiai/di; it is positively correlated with machine index and processing time and negatively correlated with deadline, so each customer will not bid by a larger machine index and processing time or a shorter deadline.


### 5.3. Winner Determination Problem

In this section, we formulate our winner determination problem as the facility owner’s profit maximization problem by selecting the customer bids and scheduling the accepted bids to the two machines synchronously. This subsection is structured as follows: first, we formulate the winner determination problem, and the Lagrangian relaxation method is used to determine the subset of the accepted bids; then we use a heuristic to construct a feasible schedule with these accepted bids.


#### 5.3.1. Lagrangian Relaxation of the Winner Determination Problem

The integer linear programming model of the winner determination problem is described as follows:(12)WDPmax∑i∈N1∑t=piTαi−v1pixit1+∑i∈N1∑t=piTαi−v2pixit2+∑j∈N2∑t=pjTαj−v2pjyjt+v1+v2Ts.t.1,2,3,4,5,6,7.Relax the constraints (3) and (4), setλ=λ11λ21λ12λ22……λ1Tλ2T to be a vector of corresponding nonpositive multipliers, and get the following Lagrangian problem (LR):(13)LRLλ=max∑i∈N1∑t=piTαi−v1pixit+∑i∈N1∑t=piTαi−v2piyit+∑j∈N2∑t′=pjTαj−v2pjzjt+v1+v2T+∑t=1Tλ1t∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs−1+∑t=1Tλ2t∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1s.t1,2,5,6and7.LR can be rewritten as(14)LRLλ=max∑i∈N1∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+∑i∈N1∑t=piTαi−v2pi+∑s=max1,t−pi+1tλ2syit+∑j∈N2∑t=pjTαj−v2pj+∑s=max1,t−pj+1tλ1szjt+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2ts.t1,2,5,6and7.Note thatLλ can be decomposed into(15)Lλ=∑i∈N1Li1λ+∑i∈N2Li2λ+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2t.Here,(16)Li1λ=max∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+αi−v2pi+∑s=max1,t−pi+1tλ2syit,s.t∑t=piTxit+∑t=piTyit≤1,∑t=1Ttxit≤di,∑t=1Ttyit≤di,Li2λ=max∑t′=piTαi−v2pi+∑s=max1,t−pi+1tλ1szit′,s.t∑t′=piTzit′≤1,∑t=1Ttzit≤di.Li1λ and Li2λ are two subproblems of bid i; it is easy to see that(17)Li1λ=max0,maxpi≤t≤diαi−v1pi+∑s=max1,t−pi+1tλ1s,αi−v2pi+∑s=max1,t−pi+1tλ2s,Li2λ=max0,maxpi≤t≤diαi−v2pi+∑s=max1,t−pi+1tλ1s.The Lagrangian dual of (LR) is defined as follows:(18)DLD=minλ≤0Lλ.Then, the subgradient method is used to determineλ so as to find optimal or near-optimal solutions for LD. The subgradient method is presented as follows.(1) Subgradient Algorithm. Step 1: setK and σ. Let k=0; set λ0 and μ0.Step 2: calculate the original problem’s feasible solution, and record its objective value asZ¯.Step 3: calculate the Lagrangian problemLkλk, and record its solution xk, yk, and zk.Step 4: letλ1k+1=λ1k+β1kG1xk,yk,zk/G1xk,yk,zk, where G1xk,yk,zk is the subgradient at point xk,yk,zk and(19)G1xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs′−1.Setμ1k=σμ1k−1, and β1k is the step size, β1k=μ1kZ¯−Lkuk/G1xk,yk,zk.Letλ2k+1=λ2k+β2kG2xk,yk,zk/G2xk,yk,zk, where G2xk,yk,zk is the subgradient at point xk,yk,zk and(20)G2xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1.Setμ2k=σμ2k−1 and β2k=μ2kZ¯−Lkuk/G2xk,yk,zk.Step 5: ifk<K, let k←k+1; go to Step 3; otherwise, stop.Li and Sun [27] demonstrated that, when using the above expression to calculate the step size, the subgradient algorithm will be convergent and it can converge to an optimal solution for the dual problem with suitable parameters. In the subgradient algorithm, the parameters need to be predetermined experimentally. The iterations K should ensure sufficient convergence of the algorithm; the step adjustment factors μ1k and μ2k character the relationship between the quality of solutions and the step size of iterations; if the values are too large, convergence oscillation will occur; if the values are too small, convergence speed will decrease. Set the initial parameter μ0=1,1, λ0=−1,−1,…,−1−1,−1,…,−1T. By the algorithm, we can obtain an upper bound LKλK for the winner determination problem, while vectors xK, yK, and zK indicate which bids are accepted for processing. Using the upper bound LKλK, we can evaluate the performance of the following heuristic.


#### 5.3.2. Heuristic of the Winner Determination Problem

From the subgradient algorithm, we get a preliminary result of bids acceptance; however, the result may not be a festival solution for the winner determination problem, so we design a heuristic to construct a feasible schedule. The heuristic is mainly based on the Lagrangian relaxation technique, and it is described as follows.(1) Heuristic.Step 1: letN′ denote the subset of accepted bids in N by the subgradient algorithm; let N″=N/N′. Index the bids of N′ in nondecreasing order of their due dates and break ties according to the shortest processing time.Step 2: for bidj=1,2,…,N′, perform Steps 2-1 to 2-2.2-1: ifaj=1, perform Steps 2-1-1 to 2-1-2.2-1-1: if bidj can be completed before its deadline on M1, then assign it to M1, next j.2-1-2: if bidj cannot be completed before its deadline on M1, then discard bid j and let N″=N″∪j, next j.2-2: ifaj=2, perform Steps 2-2-1 to 2-2-3.2-2-1: if bidj can be completed before its deadline on M1 and M2, then assign it to one machine on which bid j is finished as close to its due date as possible, next j.2-2-2: if bidj can be completed before its deadline on M1 or M2, then assign it to the machine on which bid j is finished on time, next j.2-2-3: if bidj cannot be completed before its deadline on M1 or M2, then discard bid j and let N″=N″∪j, next j.Step 3: select successively one bidl with bl/pl=maxbk/pk|k∈N″. Calculate Sl=k|pk>pl,dk≤dl,uk≤ulandak≥al,k∈N′; if Sl≠∅, then perform Steps 3-1 to 3-2; else let N″=N″/l.3-1: insert bidl in all the positions on M1 and record their objective values. Let N″=N″/l and if the maximum objective value among the generated schedules is larger than the current schedule, then take the generated schedule as the current schedule.3-2: insert bidl in all the positions on M1 or M2; refer to Step 3-1.Step 4: ifN″≠∅, go to Step 3; else, stop the heuristic.In the heuristic of the winner determination problem, we construct a feasible solution in Step 2. In order to make the solution converge to an optimal solution for the winner determination problem, we continuously improve the solution by applying greedily some searching techniques: First, we use Lemma2 to check whether the bids are likely to be inserted into the machines. Then we add the unaccepted bids to the parallel machines greedily. The computing cost of the winner determination problem is dominated by the solution of the Lagrangian dual problem, so the running time of this problem is OnT.


## 5.1. Auction Protocol

In our iterative ascending auction mechanism, the auctioneer is the facility owner who owns two parallel machines that have the same processing speed but differ in their functionality. The bidders are the customers; each of them has an order to process. The market goods are time blocks; each customer can bid for one single time block at once.In the first round, the facility owner sets the initial ask priceαi for customers, and (a) each customer sends a bid for processing order so as to maximize his own profit; the bids of the customers are defined as Bi=pi,di,ai,αi, where pi and di are the order’s processing time and deadline. Once the processing time and deadlines of the customer orders are confirmed in the first round, it cannot be changed. (b) Then the facility owner collects all bids and determines which bids to accept in order to maximize his own profit and updates the ask price αi for each customer.Step (a) and (b) will be iterated; as the ask prices continue to rise gradually, customers gradually withdraw from competition. Once any customer withdraws from the competition, he shall not return to participate in the auction again. If none of the customers submits a new bid, then the auction is terminated.The design of an optimal auction mechanism (i.e., pricing policy and winner determination algorithm) should fulfil the following properties:(1)
Individual rationality means that if a customer participates in the auction mechanism, his profit is at least as high as the profit that he is not participating.(2)
Incentive compatibility means that bidding by the truthful order information is a dominant strategy for each customer.(3)
Global optimization means the winner determination problem should be a global optimization problem when all the customers bid by their true values.(4)
Computational efficiency means the auction should reach closure in reasonable time and at reasonable computational expense.Nisan et al. [26] analyse that the second price sealed auction satisfies the above properties (1) and (2) in combinatorial auctions. However, a sealed auction is less efficient and profitable than an ascending auction in production scheduling problems (Hall and Liu 2015). What is more, in the private value model, an ascending auction is equivalent to a second price sealed auction. That is because, when the value of market goods for each customer is independent of the others, each customer’s dominant strategy is to keep in bidding until the ask price reaches his value, regardless of whether he can observe the process of the auction. At last, the winner will be the one who has the highest value. So the ascending auction mechanism can also be designed to satisfy properties (1) and (2) in our production capacity allocation problem.In our problem, the winner determination problem is NP hard, so the above properties (3) and (4) are incompatible. When the problem size is small, the optimal solution can be obtained in a limited time. However, when the problem size is large, the optimal solution cannot be obtained in a reasonable time. Therefore, we use approximate optimal solution in exchange for high computational efficiency.For our auction mechanism, the purpose of the pricing problem is to encourage all the customers to reveal truthful processing requirements, such as machine indexes, processing times, and deadlines, and make the customers’ profits nonnegative; the winner determination problem is NP hard; we aim to develop a fast heuristic to ensure that the auction reaches closure in reasonable time and at reasonable computational expense.


## 5.2. Pricing Problem

We define the ask price in roundk−1 for each customer ii∈N as αik. It consists of two parts: (a) current price βik−1, which reflects the current capacity scarcity under the generated schedule in round k−1, and (b) price increment γik , which reflects the expected impact on capacity scarcity caused by potential bids.First, we define the current priceβik in round k for customer i, based on the generated schedule in round k−1:(1)
If no time slots beforedi are allocated in round k−1 on both machines, the βik=v1+v2/2.(2)
If the time slots beforedi are allocated to orders 1,2,…,ni with prices α1k−1,α2k−1,…,αnik−1 in round k−1 on both machines, then βik is equal to the weighted average of the bid prices of all allocated time slots and the total reserved value of all unallocated time slots. It is clear that the last orders on both machines may be partially processed in 0,di. To simplify the expression of βik, let p¯jk−1 be the length of the time slots within 0,di that were allocated to order j on machine ai in round k−1. If order j is the last order on one of the machines before di, then, p¯jk−1=pj−max0,Cjk−1−dj; else p¯jk−1=pj, where Cjk−1 is the completion time of the order j. Let Iik−1 be the idle times before di on the two machines at round k−1. Then βik is equal to a weighted average price:(9)βik=2∑h=1niαhk−1p¯hk−1+Iik−1v1+v22di.Then, we define the price incrementγik in round k for customer i; it is based on (a) the flexibility of order processing related to its deadline and machine index, if the flexibility of order processing impact on resource scarcity is greater and, consequently, the price increment increases; (b) the number of bids received by this time block that contains each individual time slot. The definition is as follows:(1)
If no time slots beforedi are allocated in round k−1, then (10)γik=ρpiaidi.(2)
If the time slots beforedi are allocated in round k−1, then(11)γik=ρpiaidi+∑t=1diDtk−1Ndi.ρ are predetermined constants, called price adjustment factors; ai, pi, and di are order i′ s machine index, processing time, and deadline; Dtk−1 is the number of bids that contain time slot t in round k−1.The purpose of the pricing problem is to encourage the customers to reveal truthful machine indexes, processing times, and deadlines. We assume that the customer would not pretend that he has a smaller machine index and processing time and a greater deadline. See, for example, a customerj having an order with a machine index aj=2, a processing time pj=5, and a deadline dj=10. It is obvious that he would not pretend pj<5, or dj>10. If he pretends aj=1, his order may be assigned to machine M1 or M2; however, machine M1 cannot process a high index order, so it is impossible for him to bid by a false smaller machine index. So, in our pricing problem, we only need to ensure that the customer would not bid by a false larger machine index and processing time and a shorter deadline. From the above definition of price, we can see that the initial ask price for customer ii∈N is αi=v1+v2/2+ρpiai/di; it is positively correlated with machine index and processing time and negatively correlated with deadline, so each customer will not bid by a larger machine index and processing time or a shorter deadline.


## 5.3. Winner Determination Problem

In this section, we formulate our winner determination problem as the facility owner’s profit maximization problem by selecting the customer bids and scheduling the accepted bids to the two machines synchronously. This subsection is structured as follows: first, we formulate the winner determination problem, and the Lagrangian relaxation method is used to determine the subset of the accepted bids; then we use a heuristic to construct a feasible schedule with these accepted bids.


### 5.3.1. Lagrangian Relaxation of the Winner Determination Problem

The integer linear programming model of the winner determination problem is described as follows:(12)WDPmax∑i∈N1∑t=piTαi−v1pixit1+∑i∈N1∑t=piTαi−v2pixit2+∑j∈N2∑t=pjTαj−v2pjyjt+v1+v2Ts.t.1,2,3,4,5,6,7.Relax the constraints (3) and (4), setλ=λ11λ21λ12λ22……λ1Tλ2T to be a vector of corresponding nonpositive multipliers, and get the following Lagrangian problem (LR):(13)LRLλ=max∑i∈N1∑t=piTαi−v1pixit+∑i∈N1∑t=piTαi−v2piyit+∑j∈N2∑t′=pjTαj−v2pjzjt+v1+v2T+∑t=1Tλ1t∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs−1+∑t=1Tλ2t∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1s.t1,2,5,6and7.LR can be rewritten as(14)LRLλ=max∑i∈N1∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+∑i∈N1∑t=piTαi−v2pi+∑s=max1,t−pi+1tλ2syit+∑j∈N2∑t=pjTαj−v2pj+∑s=max1,t−pj+1tλ1szjt+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2ts.t1,2,5,6and7.Note thatLλ can be decomposed into(15)Lλ=∑i∈N1Li1λ+∑i∈N2Li2λ+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2t.Here,(16)Li1λ=max∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+αi−v2pi+∑s=max1,t−pi+1tλ2syit,s.t∑t=piTxit+∑t=piTyit≤1,∑t=1Ttxit≤di,∑t=1Ttyit≤di,Li2λ=max∑t′=piTαi−v2pi+∑s=max1,t−pi+1tλ1szit′,s.t∑t′=piTzit′≤1,∑t=1Ttzit≤di.Li1λ and Li2λ are two subproblems of bid i; it is easy to see that(17)Li1λ=max0,maxpi≤t≤diαi−v1pi+∑s=max1,t−pi+1tλ1s,αi−v2pi+∑s=max1,t−pi+1tλ2s,Li2λ=max0,maxpi≤t≤diαi−v2pi+∑s=max1,t−pi+1tλ1s.The Lagrangian dual of (LR) is defined as follows:(18)DLD=minλ≤0Lλ.Then, the subgradient method is used to determineλ so as to find optimal or near-optimal solutions for LD. The subgradient method is presented as follows.(1) Subgradient Algorithm. Step 1: setK and σ. Let k=0; set λ0 and μ0.Step 2: calculate the original problem’s feasible solution, and record its objective value asZ¯.Step 3: calculate the Lagrangian problemLkλk, and record its solution xk, yk, and zk.Step 4: letλ1k+1=λ1k+β1kG1xk,yk,zk/G1xk,yk,zk, where G1xk,yk,zk is the subgradient at point xk,yk,zk and(19)G1xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs′−1.Setμ1k=σμ1k−1, and β1k is the step size, β1k=μ1kZ¯−Lkuk/G1xk,yk,zk.Letλ2k+1=λ2k+β2kG2xk,yk,zk/G2xk,yk,zk, where G2xk,yk,zk is the subgradient at point xk,yk,zk and(20)G2xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1.Setμ2k=σμ2k−1 and β2k=μ2kZ¯−Lkuk/G2xk,yk,zk.Step 5: ifk<K, let k←k+1; go to Step 3; otherwise, stop.Li and Sun [27] demonstrated that, when using the above expression to calculate the step size, the subgradient algorithm will be convergent and it can converge to an optimal solution for the dual problem with suitable parameters. In the subgradient algorithm, the parameters need to be predetermined experimentally. The iterations K should ensure sufficient convergence of the algorithm; the step adjustment factors μ1k and μ2k character the relationship between the quality of solutions and the step size of iterations; if the values are too large, convergence oscillation will occur; if the values are too small, convergence speed will decrease. Set the initial parameter μ0=1,1, λ0=−1,−1,…,−1−1,−1,…,−1T. By the algorithm, we can obtain an upper bound LKλK for the winner determination problem, while vectors xK, yK, and zK indicate which bids are accepted for processing. Using the upper bound LKλK, we can evaluate the performance of the following heuristic.


### 5.3.2. Heuristic of the Winner Determination Problem

From the subgradient algorithm, we get a preliminary result of bids acceptance; however, the result may not be a festival solution for the winner determination problem, so we design a heuristic to construct a feasible schedule. The heuristic is mainly based on the Lagrangian relaxation technique, and it is described as follows.(1) Heuristic.Step 1: letN′ denote the subset of accepted bids in N by the subgradient algorithm; let N″=N/N′. Index the bids of N′ in nondecreasing order of their due dates and break ties according to the shortest processing time.Step 2: for bidj=1,2,…,N′, perform Steps 2-1 to 2-2.2-1: ifaj=1, perform Steps 2-1-1 to 2-1-2.2-1-1: if bidj can be completed before its deadline on M1, then assign it to M1, next j.2-1-2: if bidj cannot be completed before its deadline on M1, then discard bid j and let N″=N″∪j, next j.2-2: ifaj=2, perform Steps 2-2-1 to 2-2-3.2-2-1: if bidj can be completed before its deadline on M1 and M2, then assign it to one machine on which bid j is finished as close to its due date as possible, next j.2-2-2: if bidj can be completed before its deadline on M1 or M2, then assign it to the machine on which bid j is finished on time, next j.2-2-3: if bidj cannot be completed before its deadline on M1 or M2, then discard bid j and let N″=N″∪j, next j.Step 3: select successively one bidl with bl/pl=maxbk/pk|k∈N″. Calculate Sl=k|pk>pl,dk≤dl,uk≤ulandak≥al,k∈N′; if Sl≠∅, then perform Steps 3-1 to 3-2; else let N″=N″/l.3-1: insert bidl in all the positions on M1 and record their objective values. Let N″=N″/l and if the maximum objective value among the generated schedules is larger than the current schedule, then take the generated schedule as the current schedule.3-2: insert bidl in all the positions on M1 or M2; refer to Step 3-1.Step 4: ifN″≠∅, go to Step 3; else, stop the heuristic.In the heuristic of the winner determination problem, we construct a feasible solution in Step 2. In order to make the solution converge to an optimal solution for the winner determination problem, we continuously improve the solution by applying greedily some searching techniques: First, we use Lemma2 to check whether the bids are likely to be inserted into the machines. Then we add the unaccepted bids to the parallel machines greedily. The computing cost of the winner determination problem is dominated by the solution of the Lagrangian dual problem, so the running time of this problem is OnT.


## 5.3.1. Lagrangian Relaxation of the Winner Determination Problem

The integer linear programming model of the winner determination problem is described as follows:(12)WDPmax∑i∈N1∑t=piTαi−v1pixit1+∑i∈N1∑t=piTαi−v2pixit2+∑j∈N2∑t=pjTαj−v2pjyjt+v1+v2Ts.t.1,2,3,4,5,6,7.Relax the constraints (3) and (4), setλ=λ11λ21λ12λ22……λ1Tλ2T to be a vector of corresponding nonpositive multipliers, and get the following Lagrangian problem (LR):(13)LRLλ=max∑i∈N1∑t=piTαi−v1pixit+∑i∈N1∑t=piTαi−v2piyit+∑j∈N2∑t′=pjTαj−v2pjzjt+v1+v2T+∑t=1Tλ1t∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs−1+∑t=1Tλ2t∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1s.t1,2,5,6and7.LR can be rewritten as(14)LRLλ=max∑i∈N1∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+∑i∈N1∑t=piTαi−v2pi+∑s=max1,t−pi+1tλ2syit+∑j∈N2∑t=pjTαj−v2pj+∑s=max1,t−pj+1tλ1szjt+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2ts.t1,2,5,6and7.Note thatLλ can be decomposed into(15)Lλ=∑i∈N1Li1λ+∑i∈N2Li2λ+v1+v2T−∑t=1Tλ1t−∑t=1Tλ2t.Here,(16)Li1λ=max∑t=piTαi−v1pi+∑s=max1,t−pi+1tλ1sxit+αi−v2pi+∑s=max1,t−pi+1tλ2syit,s.t∑t=piTxit+∑t=piTyit≤1,∑t=1Ttxit≤di,∑t=1Ttyit≤di,Li2λ=max∑t′=piTαi−v2pi+∑s=max1,t−pi+1tλ1szit′,s.t∑t′=piTzit′≤1,∑t=1Ttzit≤di.Li1λ and Li2λ are two subproblems of bid i; it is easy to see that(17)Li1λ=max0,maxpi≤t≤diαi−v1pi+∑s=max1,t−pi+1tλ1s,αi−v2pi+∑s=max1,t−pi+1tλ2s,Li2λ=max0,maxpi≤t≤diαi−v2pi+∑s=max1,t−pi+1tλ1s.The Lagrangian dual of (LR) is defined as follows:(18)DLD=minλ≤0Lλ.Then, the subgradient method is used to determineλ so as to find optimal or near-optimal solutions for LD. The subgradient method is presented as follows.(1) Subgradient Algorithm. Step 1: setK and σ. Let k=0; set λ0 and μ0.Step 2: calculate the original problem’s feasible solution, and record its objective value asZ¯.Step 3: calculate the Lagrangian problemLkλk, and record its solution xk, yk, and zk.Step 4: letλ1k+1=λ1k+β1kG1xk,yk,zk/G1xk,yk,zk, where G1xk,yk,zk is the subgradient at point xk,yk,zk and(19)G1xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Txis+∑j∈N2∑s′=maxpj,tmint+pj−1,Tzjs′−1.Setμ1k=σμ1k−1, and β1k is the step size, β1k=μ1kZ¯−Lkuk/G1xk,yk,zk.Letλ2k+1=λ2k+β2kG2xk,yk,zk/G2xk,yk,zk, where G2xk,yk,zk is the subgradient at point xk,yk,zk and(20)G2xk,yk,zk=∑i∈N1∑s=maxpi,tmint+pi−1,Tyis−1.Setμ2k=σμ2k−1 and β2k=μ2kZ¯−Lkuk/G2xk,yk,zk.Step 5: ifk<K, let k←k+1; go to Step 3; otherwise, stop.Li and Sun [27] demonstrated that, when using the above expression to calculate the step size, the subgradient algorithm will be convergent and it can converge to an optimal solution for the dual problem with suitable parameters. In the subgradient algorithm, the parameters need to be predetermined experimentally. The iterations K should ensure sufficient convergence of the algorithm; the step adjustment factors μ1k and μ2k character the relationship between the quality of solutions and the step size of iterations; if the values are too large, convergence oscillation will occur; if the values are too small, convergence speed will decrease. Set the initial parameter μ0=1,1, λ0=−1,−1,…,−1−1,−1,…,−1T. By the algorithm, we can obtain an upper bound LKλK for the winner determination problem, while vectors xK, yK, and zK indicate which bids are accepted for processing. Using the upper bound LKλK, we can evaluate the performance of the following heuristic.


## 5.3.2. Heuristic of the Winner Determination Problem

From the subgradient algorithm, we get a preliminary result of bids acceptance; however, the result may not be a festival solution for the winner determination problem, so we design a heuristic to construct a feasible schedule. The heuristic is mainly based on the Lagrangian relaxation technique, and it is described as follows.(1) Heuristic.Step 1: letN′ denote the subset of accepted bids in N by the subgradient algorithm; let N″=N/N′. Index the bids of N′ in nondecreasing order of their due dates and break ties according to the shortest processing time.Step 2: for bidj=1,2,…,N′, perform Steps 2-1 to 2-2.2-1: ifaj=1, perform Steps 2-1-1 to 2-1-2.2-1-1: if bidj can be completed before its deadline on M1, then assign it to M1, next j.2-1-2: if bidj cannot be completed before its deadline on M1, then discard bid j and let N″=N″∪j, next j.2-2: ifaj=2, perform Steps 2-2-1 to 2-2-3.2-2-1: if bidj can be completed before its deadline on M1 and M2, then assign it to one machine on which bid j is finished as close to its due date as possible, next j.2-2-2: if bidj can be completed before its deadline on M1 or M2, then assign it to the machine on which bid j is finished on time, next j.2-2-3: if bidj cannot be completed before its deadline on M1 or M2, then discard bid j and let N″=N″∪j, next j.Step 3: select successively one bidl with bl/pl=maxbk/pk|k∈N″. Calculate Sl=k|pk>pl,dk≤dl,uk≤ulandak≥al,k∈N′; if Sl≠∅, then perform Steps 3-1 to 3-2; else let N″=N″/l.3-1: insert bidl in all the positions on M1 and record their objective values. Let N″=N″/l and if the maximum objective value among the generated schedules is larger than the current schedule, then take the generated schedule as the current schedule.3-2: insert bidl in all the positions on M1 or M2; refer to Step 3-1.Step 4: ifN″≠∅, go to Step 3; else, stop the heuristic.In the heuristic of the winner determination problem, we construct a feasible solution in Step 2. In order to make the solution converge to an optimal solution for the winner determination problem, we continuously improve the solution by applying greedily some searching techniques: First, we use Lemma2 to check whether the bids are likely to be inserted into the machines. Then we add the unaccepted bids to the parallel machines greedily. The computing cost of the winner determination problem is dominated by the solution of the Lagrangian dual problem, so the running time of this problem is OnT.


## 6. Computational Experiments

In this section, we conducted computational experiments to analyse the computational efficiency and effectiveness of the ascending auction mechanism. All experiments were run on an Intel 2.9 GHz octa-core processor with 32G RAM. In the following, we present the experimental schemes and the discussion of the results.


### 6.1. Data Generation

To test the performance of the auction mechanism extensively, we randomly generate instances of the problem by varying the problem size and parameters that may affect the analysis of the auction mechanism. First, we selectn∈25,50,100 and randomly generate the processing time pii∈N from the integer uniform distribution in the interval 1,100. Let the total processing time P=∑i∈Npi, for each instance with P, the facility owner’s capacity T=⌊ηP/2⌋, where η∈0.5,0.7,0.9, and the reserve values v1 and v2 are randomly generated from the integer uniform distribution in the interval 1,10, respectively. For each customer order i, we randomly generate its deadline di from the integer uniform distribution in the interval maxpi,ωT,T, where ω∈0.2,0.5,0.8, revenue ui from the integer uniform distribution in the interval pimaxv1,v2,1000, and machine index ai from 1,2. Then, for the pricing problem in Subsection 5.2, we define the price adjustment factors ρ∈0.5,1.0,2.0. For each 3×3×3×3=81 possible combinations of parameters, we randomly generate 10 problem instances, for a total of 810.


### 6.2. Analysis of Heuristic of the Winner Determination Problem

To ensure the auction reach closure in reasonable time and at reasonable computational expense, we use a heuristic solving the winner determination problem in exchange for high computational efficiency. In this subsection, we evaluate the performance of this heuristic. First, we use the Lagrangian relaxation technique (Subsection5.3.1) to establish an upper bound on the facility owner’s maximum profit, which is denoted as UBf. Let OPTf and Hf denote the optimal solution value and the heuristic solution, respectively. For the small-sized instances with n=25, we compare the heuristic solution value to the optimal solution value, where R=Hf/OPTf; for the large-sized instances with n=50,100, we compare the heuristic solution value to the upper bound, where R=Hf/UBf.The computational results are summarized in Table1. First, the overall mean values of R for the cases n=25,50, and 100 are 96.00%, 91.65%, and 89.06%, respectively. The heuristic of the winner determination problem performs well across different problem sizes and parameters. Second, we notice that the mean value of R for the large-sized problem is significantly smaller than that of the small-sized problem. This is because the value of R for the large-sized problems is underestimated due to the gaps between the optimal solutions and the upper bounds. Third, when the value of the facility owner’s capacity parameter η is bigger, different values of the customer order’s deadline parameter ω will have a more significant impact on the performance of the heuristic. This may indicate that the performance of the heuristic is mainly determined by the scarcity of resource. From the above, we can conclude that the heuristic of the winner determination problem is effective in finding good solutions rapidly.Table 1
The performance of heuristic of the winner determination problem.
ηωR (%)n = 25n = 50n = 1000.50.297.4894.4690.120.595.5892.2989.530.896.5391.7387.380.70.295.3489.6787.690.596.5392.4889.730.894.8290.5390.450.90.293.9188.4290.100.596.1293.5889.240.897.7391.6787.30Average96.0091.6589.06


### 6.3. Analysis of the Auction Mechanism

To evaluate the performance of the auction mechanism, we define the POA in our study as the percentage deviation of the system value of the auction outcome from that of the global system optimum. For the large-sized instances, it is impossible to get the global optimal solution in a reasonable time with CPLEX, so we use an upper bound instead of the global optimal solution.The computational results with different parameters are summarized in Table2. First, the mean values of POA for the case where n=25,50, and 100 are 93.82%, 86.24%, and 83.2%, respectively. As the number of customers decreases, the auction performs better. Second, as η increases from 0.5 to 0.9, ω decreases from 0.8 to 0.2, and the auction mechanism performs better. This shows that the fewer the conflicts in resource requirements are, the better the auction performs. Third, the mean number of rounds for the auction to reach closure is 25.7. When the number of customers is larger, and the price adjustment factor ρ is smaller, the auction needs more rounds to reach closure. However, the auction does not perform better when the number of rounds is increased. This may result from the combinatorial optimization characteristics of the machine capacity’s allocation problem.Table 2
The performance of the auction mechanism withn=25,50.
ηωρPOA (%)Roundn = 25n = 50n = 100n = 25n = 50n = 1000.50.20.594.0989.4085.1315.024.545.71.093.0387.1485.9212.020.228.32.093.0285.1883.5910.319.624.90.50.591.6887.6083.6314.021.639.91.092.1888.0884.5112.019.326.82.090.7886.2881.2911.319.421.90.80.585.4685.1084.3317.630.741.31.092.4984.3583.5818.326.432.62.093.2282.7080.4910.019.828.50.70.20.592.9489.3682.6015.720.535.91.094.8690.0583.7813.320.227.52.093.8587.1182.7911.719.025.40.50.590.5886.1983.5518.830.139.31.093.6287.2183.6916.726.430.52.093.2484.6282.2214.624.031.60.80.593.4583.2279.8823.031.144.61.093.3485.5881.3621.731.839.52.096.3588.3184.9115.324.430.60.90.20.594.7691.1486.2818.733.942.71.096.5286.4785.8115.024.837.82.098.7985.1983.3614.725.029.10.50.596.6187.0685.6718.330.838.41.097.6783.5982.0215.723.432.32.098.4789.0480.0716.725.428.20.80.592.9683.1782.5534.740.348.51.093.2682.3281.8428.035.639.92.095.8985.0881.6722.731.837.5Average93.8286.2483.2016.925.934.4


## 6.1. Data Generation

To test the performance of the auction mechanism extensively, we randomly generate instances of the problem by varying the problem size and parameters that may affect the analysis of the auction mechanism. First, we selectn∈25,50,100 and randomly generate the processing time pii∈N from the integer uniform distribution in the interval 1,100. Let the total processing time P=∑i∈Npi, for each instance with P, the facility owner’s capacity T=⌊ηP/2⌋, where η∈0.5,0.7,0.9, and the reserve values v1 and v2 are randomly generated from the integer uniform distribution in the interval 1,10, respectively. For each customer order i, we randomly generate its deadline di from the integer uniform distribution in the interval maxpi,ωT,T, where ω∈0.2,0.5,0.8, revenue ui from the integer uniform distribution in the interval pimaxv1,v2,1000, and machine index ai from 1,2. Then, for the pricing problem in Subsection 5.2, we define the price adjustment factors ρ∈0.5,1.0,2.0. For each 3×3×3×3=81 possible combinations of parameters, we randomly generate 10 problem instances, for a total of 810.


## 6.2. Analysis of Heuristic of the Winner Determination Problem

To ensure the auction reach closure in reasonable time and at reasonable computational expense, we use a heuristic solving the winner determination problem in exchange for high computational efficiency. In this subsection, we evaluate the performance of this heuristic. First, we use the Lagrangian relaxation technique (Subsection5.3.1) to establish an upper bound on the facility owner’s maximum profit, which is denoted as UBf. Let OPTf and Hf denote the optimal solution value and the heuristic solution, respectively. For the small-sized instances with n=25, we compare the heuristic solution value to the optimal solution value, where R=Hf/OPTf; for the large-sized instances with n=50,100, we compare the heuristic solution value to the upper bound, where R=Hf/UBf.The computational results are summarized in Table1. First, the overall mean values of R for the cases n=25,50, and 100 are 96.00%, 91.65%, and 89.06%, respectively. The heuristic of the winner determination problem performs well across different problem sizes and parameters. Second, we notice that the mean value of R for the large-sized problem is significantly smaller than that of the small-sized problem. This is because the value of R for the large-sized problems is underestimated due to the gaps between the optimal solutions and the upper bounds. Third, when the value of the facility owner’s capacity parameter η is bigger, different values of the customer order’s deadline parameter ω will have a more significant impact on the performance of the heuristic. This may indicate that the performance of the heuristic is mainly determined by the scarcity of resource. From the above, we can conclude that the heuristic of the winner determination problem is effective in finding good solutions rapidly.Table 1
The performance of heuristic of the winner determination problem.
ηωR (%)n = 25n = 50n = 1000.50.297.4894.4690.120.595.5892.2989.530.896.5391.7387.380.70.295.3489.6787.690.596.5392.4889.730.894.8290.5390.450.90.293.9188.4290.100.596.1293.5889.240.897.7391.6787.30Average96.0091.6589.06


## 6.3. Analysis of the Auction Mechanism

To evaluate the performance of the auction mechanism, we define the POA in our study as the percentage deviation of the system value of the auction outcome from that of the global system optimum. For the large-sized instances, it is impossible to get the global optimal solution in a reasonable time with CPLEX, so we use an upper bound instead of the global optimal solution.The computational results with different parameters are summarized in Table2. First, the mean values of POA for the case where n=25,50, and 100 are 93.82%, 86.24%, and 83.2%, respectively. As the number of customers decreases, the auction performs better. Second, as η increases from 0.5 to 0.9, ω decreases from 0.8 to 0.2, and the auction mechanism performs better. This shows that the fewer the conflicts in resource requirements are, the better the auction performs. Third, the mean number of rounds for the auction to reach closure is 25.7. When the number of customers is larger, and the price adjustment factor ρ is smaller, the auction needs more rounds to reach closure. However, the auction does not perform better when the number of rounds is increased. This may result from the combinatorial optimization characteristics of the machine capacity’s allocation problem.Table 2
The performance of the auction mechanism withn=25,50.
ηωρPOA (%)Roundn = 25n = 50n = 100n = 25n = 50n = 1000.50.20.594.0989.4085.1315.024.545.71.093.0387.1485.9212.020.228.32.093.0285.1883.5910.319.624.90.50.591.6887.6083.6314.021.639.91.092.1888.0884.5112.019.326.82.090.7886.2881.2911.319.421.90.80.585.4685.1084.3317.630.741.31.092.4984.3583.5818.326.432.62.093.2282.7080.4910.019.828.50.70.20.592.9489.3682.6015.720.535.91.094.8690.0583.7813.320.227.52.093.8587.1182.7911.719.025.40.50.590.5886.1983.5518.830.139.31.093.6287.2183.6916.726.430.52.093.2484.6282.2214.624.031.60.80.593.4583.2279.8823.031.144.61.093.3485.5881.3621.731.839.52.096.3588.3184.9115.324.430.60.90.20.594.7691.1486.2818.733.942.71.096.5286.4785.8115.024.837.82.098.7985.1983.3614.725.029.10.50.596.6187.0685.6718.330.838.41.097.6783.5982.0215.723.432.32.098.4789.0480.0716.725.428.20.80.592.9683.1782.5534.740.348.51.093.2682.3281.8428.035.639.92.095.8985.0881.6722.731.837.5Average93.8286.2483.2016.925.934.4


## 7. Conclusion

In this study, we present an iterative ascending auction mechanism for the scare production capacity allocation problem in two parallel machines with IPS restrictions. In our auction, the customers do not have to make decisions with all the information; they only need to decide whether to bid or not. The ask prices are updated adaptively by the facility owner which can make the customers bid by truthful processing requirements and keep on bidding until the ask price reaches their real revenues. The winner determination problem integrates the capacity allocation and scheduling decisions in two parallel machines with IPS restrictions. The proposed heuristic of winner determination problem is efficient in finding good solutions. This ensures our auction reaches closure in a reasonable time. Overall, our auction mechanism is an effective method to allocation the capacity in two parallel machines with IPS restrictions.



---

*Source: 2045630-2022-01-28.xml*